Databases Reference
In-Depth Information
privacy constraints during database query, update and design operations. We
have also examined the use of semantic data models for reasoning about pri-
vacy constraints [THUR06]. In our current paper we focus on developing a
theory of the privacy problem based on recursive functions and computabil-
ity theory. A formulation of the privacy problem is given and its recursion
theoretic properties are investigated.
Our ultimate goal is to obtain a complete characterization of the privacy
problem and investigate measures of complexity. Such an investigation could
usefully begin with aspects of recursive function theory. This is because re-
cursive function theory from which the notion of computability is derived
(see [ROGE67]) has provided the basis from which other abstract theories
such as computational complexity (see [BLUM67]) and Kolmograv complex-
ity theory (see [KOLM65]) have evolved (we refer to [BRAI74], [MATC78] and
[CALU88] for a discussion on this evolution). Moreover the work of Rosza Pe-
ters (see [PETE81]) has shown the practical significance of recursive function
theory in computer science and provided the basis for possible exploitation
of such results. Therefore the study of the foundations of the privacy prob-
lem could usefully begin with aspects of recursive function theory. We have
investigated the recursion theoretic properties of the privacy problem associ-
ated with database design. We give a formulation of the privacy problem as a
database design problem and investigate the recursion theoretic properties of
this problem. Our research is influenced by our work on privacy constraints
and privacy enhanced databases (see [THUR05c]) as well as our prior research
on the inference problem (see [THUR91]). For a background on the inference
problem we refer to [MORG87], [THUR87], and [HINK88]. For a discussion
of multilevel secure databases we refer to [AFSB83], [THUR05b].
The organization of this paper is as follows. In Sect. 2, which is the essence
of this paper, we define a set X(L) corresponding to each privacy level L. This
set consists of all databases D that are not privacy enhanced with respect to
privacy level L. The privacy problem with respect to private level L would then
be the membership problem for the set X(L). That is, given a database D, if
it can be effectively decided whether D belongs to X(L), then one can decide
whether the design of the database D is privacy enhanced with respect to
level L. By privacy enhanced at a level L we mean that all information that
should be labeled at privacy level L is correctly labeled at level L. We prove
properties of the set X(L). In Sect. 3 we discuss directions for future work on
the foundations and complexity of the privacy problem.
2 A Theory of the Privacy Problem
2.1 Overview
The theory developed in this section is based on privacy enhanced/non-privacy
enhanced database designs. Given a database and a set of privacy constraints,
if it can be effectively decided that the database is designed in such a way
