Database Reference
In-Depth Information
2. DATA AND QUERY MODEL
of a UCQ query on a tuple-independent or BID database. U-relations are c-tables with several
restrictions that ensure that they can be naturally represented in a standard relational database. First,
for each tuple
t
in a U-relation, its annotation
t
must be a conjunction of
k
atomic events of the
form
X
=
d
, where
k
is fixed by the schema. Second, unlike c-tables, in a U-relation, a tuple
t
may
occur multiple times: if these occurrences are annotated with
t
,
t
,...
, then the annotation of
t
is
taken as
t
∨
t
∨···
Finally, U-relations allow a table to be partitioned vertically, thus allowing
independent attributes to be described separately. A U-database is a collection of U-relations. As
with any pc-database, the probabilities of all atomic events
X
=
d
are stored separately, in a table
W(V,D,P)
called the
world table
; since this is similar to pc-tables, we will not discuss the world
table here.
Definition 2.20
A
U-relation schema
is a relational schema
T(V
1
,D
1
,...,V
k
,D
k
,A
1
,...,A
m
)
,
together with
k
pairs of distinguished attributes,
V
i
,D
i
,
i
=
1
,k
.A
U-database schema
consists of a
set of U-relation schemas.
An instance
D
of the U-relation schema
T
represents the following c-table, denoted
by
c
D
. Its schema,
c(T )
, is obtained by removing all pairs of distinguished attributes,
c(T )
=
R(A
1
,...,A
m
)
, and its instance contains all tuples
t
∈
A
1
,...,A
m
(T )
, and each tuple
t
=
(a
1
,...,a
m
)
is annotated with the formula
t
:
−
t
=
(X
1
=
d
1
)
∧···∧
(X
k
=
d
k
)
(X
1
,d
1
,...,X
k
,d
k
,a
1
,...,a
m
)
∈
T
Similarly, an instance
D
of a U-database schema represents a conditional database
D
c
con-
sisting of all c-tables associated with the U-relations in
D
.
In other words, a row
(X
1
,d
1
,X
2
,d
2
,
···
,a
1
,a
2
,
···
)
in a U-relation represents (a) the
tuple
(a
1
,a
2
,
···
)
and (b) the propositional formula
(X
1
=
d
1
)
∧
(X
2
=
d
2
)
∧···
. We make two
simplifications to U-relations. First, if the discrete variables to be stored in a column
V
i
are Boolean
variables and they occur only positively, then we will drop the corresponding domain attribute
D
i
.
That is, a table
T(V
1
,D
1
,V
2
,D
2
,A)
becomes
T(V
1
,V
2
,A)
: a tuple
(X,Y,a)
in
T
represents
a
,
annotated with the formula
a
=
XY
. Second, if there are fewer than
k
conjuncts in
i
(X
i
=
d
i
)
,
then we can either repeat one of them, or we can fill the extra attributes with NULLs. Continuing
the example above, either tuple
(Z,Z,b)
or
(Z, null,b)
represents
b
, annotated with
b
=
Z
.In
other words, a NULL value represents
true
.
Example 2.21
For a simple illustration of a U-relation, consider the pc-table in
Example 2.14
.
This can be represented by the following U-relation:
