Databases Reference
In-Depth Information
The following is an example of a deductive database:
B=
{
m1, m2, ....mn)
R=
{
(i) m1
e
(ii) m3, m4
→
→
f
(iii) m5, m2
→
g
(iv) m6
→
A*m6 (* is the concatenation operation)
(v) m7, e
→
p
(vi) m6, m8
→
b, c
(vii) X
Y where Y is a subset of a set X
(viii) if Y =
→
and if
y1, y2, .... yt
→
z1, z2, . . . zj (1
≤
i
≤
j) is a rule in R, then
X
→
X
∪{
z1,z2, . . . zj
}
isalsoaruleinR
{
y1, y2, . . . yt) is a subset of X =
{
x1, x2, . . . xk
}
Note that the symbol
→
is the “implies” relationship. The symbol
∪
is the
union relationship and the symbol
is the membership relationship. While
we focus on relational databases, the discussion applies for any database.
A deductive database can be regarded to be a semi-thue system. For a
discussion of such systems we refer to [HOPC79]). The set of data that is
deduced from B is not necessarily finite. Furthermore, the set of rules R can
be regarded as a privacy function whose definition is given below.
Privacy Function:
A function f: G
∈
Pw(G) is a privacy function if there
exists recursive functions a and b such that for all x, f(x) = Da(x) and f-1(x)
= Db(x) where De is the eth finite set in some standard enumeration, G is
a countable set of entities (an entity could also be a database), Pw(G) is the
set of all finite subsets of G and
→
f-1(x) =
}
Furthermore, for an X
{
y: x
∈
f(y)
∈
Pw(G)
f(X) =
}
Note that f-1 is the inverse of f.
The symbol
∪
x
∈
X
{
y: y
∈
f(x)
→
takes a function from domain to range.
The set of all privacy functions is denoted by
PF
.
A privacy function is deterministic if f(x) has atmost one member.
Consequences:
Next we define Cnf(x), which is the set of all consequences of
x by a privacy function f. This set consists of all the information that can be
inferred from a set of axioms x by f.
Define y
∈
Cnf(x) if one of the following conditions holds:
(i) y = x
(ii) y
f(x)
(iii) There exists a sequence of numbers y1, y2, . . . yn such that y1 = x,
yn = y and for all i (1
≤
I
≤
n-1), yi+1
∈
Cnf(yi).
∈
