Databases Reference
In-Depth Information
Miklau and Suciu's guarantee of perfect privacy considers a subclass of at-
tackers described by independent-tuple distributions, with the benefit of fea-
turing better decision complexity. Recursive (
c, l
)-diversity requires l-pruning
distributions, which are a subclass of the distributions of [8]. L-pruning distri-
butions are also particular cases of independent-tuple distributions. Finally,
the uniform distribution
u
implicitly used to model attackers in k-anonymity
is a particular case of l-pruning distributions (for
l
= 1). Figure 2 summarizes
the relationship between the various classes of attackers.
Note that the classes
P
a
,
P
S
,
P
it
were introduced for view-based privacy,
while
P
u
for generalization-based privacy. There is no reason why the
various classes of attackers should not be considered uniformly, across both
publishing paradigms.
LP
and
6 Privacy in Open-World Integration
So far we have only considered publishing settings in which
is a function.
However, this modeling leaves out an important publishing paradigm, namely
open-world integration [11, 13].
In open-world integration, a collection
L
of data sources (also known as
local databases) is registered into an integrated database
G
(also known as
the global database). Each data source is registered by stating the inclusion of
a publishable data subset into
G
. The publishable subset is typically specified
by a query against the local database, and the global dataset containing it is
specified by a query against the global database. This allows for instance a
Toyota car dealer to register the classified deals in her database as a subset of
the Toyota deals from the global database of a portal covering many dealer-
ships. If the portal offers several brands, specifying its Toyota deals requires
a selection query.
Such inclusion statements do not uniquely determine the global database,
since whenever a global database
G
satisfies them, so does any other database
strictly containing the tuples in
G
. Consequently, the relation
V
V
between local
(proprietary) and global (public) database is not functional:
associates any
extent of local databases
L
to an infinite family of global databases. Towards
a well-defined semantics of answering application queries
Q
against the global
schema, the notion of
certain answers
was introduced [11, 13]. Given a set
L
of local databases, the certain answer of
Q
against the global schema is the
set of all tuples appearing in the answer of
Q
on all global databases
G
related
to
L
:
cert
Q
(
L
)=
V
∩
(
L,G
)
∈V
Q
(
G
)
.
Clients (and therefore attackers) can interact with the integration system
only by posing queries against the global schema and receiving their certain
answer. In such a setting, it still makes sense to allow the owner of an indi-
vidual local database to specify the sensitive data using a query
against
the local database. Privacy of the secret can still be defined in terms of no
S
