Databases Reference
In-Depth Information
Extent-Independent Guarantees.
The privacy guarantees we've con-
sidered so far depend on the extent of the actual database
D
. The owner is thus
faced with the following dilemma. Checking the guarantee on a given extent
D
avoids being overly conservative and rejecting those publishing functions that
preserve privacy on the actual database but breach it on some other database
extent
D
. On the other hand, this means re-checking the privacy guarantees
upon each update to
D
. Alternatively, we consider strengthening the above
guarantees to hold over all database extents. We obtain the following list of
extent-independent privacy guarantees:
D
NDE
D
(
NDE(
V
):=
∀
V
)
D
NSE
D
S
NSE
S
(
V
):=
∀
(
V
)
D
NBR
D
P,S
NBR
P,S
(
V
):=
∀
(
V
)
D
NFBR
D
P,S
NFBR
P,S
(
N
,
V
):=
∀
(
N
,
V
)
D
BBR
D
P,S
BBR
P,S
(
V
,
):=
∀
(
V
,
)
D
BFBR
D
P,S
BFBR
P,S
(
N
,
V
,
):=
∀
(
N
,
V
,
)
As before, it makes sense to carefully consider the trade-off between
strength of the guarantee and utility of the publishing functions it allows.
In many situations, the proprietary database is known to satisfy a set of in-
tegrity constraints
. By imposing the unrestricted extent-independent guar-
antees above, the owner risks excluding a perfectly safe publishing function
because it breaks the guarantees on some database that will never occur in
practice since it violates the constraints. Clearly, the owner does not need the
privacy guarantees to hold on all imaginable databases, but only on a subclass
thereof: all databases
D
satisfying the constraints in
C
). This
natural relaxation yields guarantees that are extent-independent as long as
the extents satisfy the constraints:
C
(denoted
D
|
=
C
NDE
C
(
)NDE
D
(
V
):=
∀
(
D
|
=
C
V
)
NSE
S
)NSE
D
S
(
V
):=
∀
(
D
|
=
C
(
V
)
NBR
P,S
)NBR
D
P
(
V
):=
∀
(
D
|
=
C
(
V
)
,
S
NFBR
P,S
(
)NFBR
D
P,S
N
,
V
):=
∀
(
D
|
=
C
(
N
,
V
)
BBR
P,S
(
) BBR
D
P,S
V
,
):=
∀
(
D
|
=
C
(
V
,
)
BFBR
P,S
(
)BFBR
D
P,S
N
,
V
,
):=
∀
(
D
|
=
C
(
N
,
V
,
)
A Similar Privacy Model.
[5, 6] propose a similar privacy model for re-
lational databases, based on Bayesian belief revision. However the authors do
not address the equivalent of the NFBR
P,S
, BBR
P,S
, and BFBR
P,S
guaran-
tees, nor do they consider guarantees parameterized by classes of probability
distributions, or integrity constraints.
