Databases Reference
In-Depth Information
(or bounded) belief revision, which depends on the possible local databases,
analogous to the
GBP
model.
However, the possible local databases now represent precisely those which
are indistinguishable from the actual local database by an arbitrary interaction
with the integration system. That is, they cannot be distinguished by posing
arbitrary-length sequences of arbitrary queries against the global schema and
observing their certain answer.
The problem is that the space of possible interactions between attacker
and integration system is infinite, so this definition does not immediately lead
to an algorithm for identifying the set of possible local databases, which in
turn hinders the development of an algorithm for checking privacy guarantees.
[21] solves the problem in a setting where
is given by containment
statements between a union of conjunctive queries with inequalities (UCQ
=
)
against the local data and a UCQ
=
query against the global data (such state-
ments are also known as GLAV [11, 13] or source-target constraints [10]). The
secret
V
is also given by a UCQ
=
query against the local database. [21] shows
that, instead of considering the infinitely many possible interactions of an at-
tacker with the integration system, it suces to focus on a single, canonically
built interaction. This canonical interaction is optimal in the sense that it
poses a finite set of queries against the integration system, such that no fur-
ther queries an attacker could conceive give additional information. More pre-
cisely, the certain answers of the canonical queries su
ce to reverse-engineer
precisely the set of possible local databases. This in turn enables formulating
and checking all extent-dependent
GBP
privacy guarantees (Section 2).
S
7 Conclusions
In this chapter, we reduced various instantiations of the view-based and
generalization-based publishing to the
GBP
model, also showing how to ap-
ply it to publishing in open-world integration. This reduction offers a unifying
perspective on various seemingly disparate privacy guarantees developed in-
dependently for the various publishing paradigms.
We have applied the
GBP
model to settings in which the publishing trans-
formation is deterministically defined as either a function or a relation. This
assumption leaves out the mature line of research on preserving privacy by
randomizing the data (see for instance [2] and references within).
References
1. Serge Abiteboul, Richard Hull, and Victor Vianu.
Foundations of Databases
.
Addison-Wesley, 1995.
2. Charu C. Aggarwal. On randomization, public information and the curse of
dimensionality. In
International Conference on Data Engineering (ICDE)
, pages
136-145, 2007.
