Databases Reference
In-Depth Information
3 View-Based Publishing
3.1 Independent-Tuple Attackers
The application of the privacy model from [5] to view-based publishing was
pioneered in seminal work by Miklau and Suciu [19, 20].
In the setting of
[19, 20], the publishing function
V
is given by a list
of views. Both
V
and the secret
S
are specified by conjunctive queries with
inequalities.
As in Section 2, an attacker is described by a probability distribution
δ
on
the set of all databases. However, only attackers described by
independent-
tuple
distributions are considered. These distributions treat the occurrences
of any two tuples
t
1
,
t
2
in a given database as independent events. Formally,
given a domain
Dom
, denote the set of all tuples over
Dom
by
tuples(
Dom
)
.
Any
D
tuples
(
Dom
) is a database over domain
Dom
.
δ
is an independent-
tuple distribution on the databases over
Dom
if it is induced by a distribution
p
on
tuples(
Dom
)
. That is, for any database
D
over
Dom
we have (by the
independent-tuple assumption)
δ
(
D
):=
t
⊆
p
(
t
)
×
(1
−
p
(
t
))
.
∈
D
∈
tuples
(
Dom
)
−D
t
The attacker's a priori and a posteriori beliefs about the secret
S
(
R
) are then
induced by
p
via
δ
as in (1), respectively (2).
Perfect privacy.
Given secret
are considered to pre-
serve privacy against an attacker described by distribution
δ
if there is no
change between the attacker's a posteriori belief (after seeing
S
(
D
), the views
V
V
(
R
)) and his a
priori belief (before seeing
V
(
R
)) about secret
s
=
S
(
D
):
P
δ
[
s
]=
P
δ
[
s
|V
(
D
)].
P
Dom
the set of all independent-
tuple distributions on databases over
Dom
induced by distributions over
tuples(
Dom
)
.
Then
Given a domain
Dom
, denote with
)
if for every domain
Dom
, every database
D
over
Dom
, every secret value
s
and every distribution
δ
V
is said to maintain
perfect privacy
for secret
S
, denoted
PerfP
S
(
V
∈P
Dom
, upon observing
V
(
D
) the attacker does not
revise his belief that
s
is the secret:
PerfP
S
(
V
):=
∀
Dom
∀
(
D
⊆
tuples
(
Dom
))
∀
s
∀
(
δ
∈P
Dom
)
P
δ
[
s
]=
P
δ
[
s
|V
(
D
)]
,
or, equivalently in the notation of the
GBP
model (Section 2.2),
tuples
(
Dom
)) NBR
D
P
Dom
,
PerfP
S
(
V
):=
∀
Dom
∀
(
D
⊆
(
V
)
.
(4)
S
Note that perfect privacy is an extent-independent guarantee. Therefore it
need not be re-checked upon every update to the database.
