Database Reference
In-Depth Information
•
Second, the program
Π
Q
includes the following rules that formalize the idea that
E
QUAL
(
x
,
y
) holds if
x
and
y
are the same elements:
E
QUAL
(
x
,
x
)
←
D
OM
(
x
)
(7.8)
E
QUAL
(
x
,
y
)
←
E
QUAL
(
y
,
x
)
(7.9)
E
QUAL
(
x
,
y
)
←
E
QUAL
(
x
,
z
)
,
E
QUAL
(
z
,
y
)
.
(7.10)
Notice that we cannot simply use the rule E
QUAL
(
x
,
x
)
to say that E
QUAL
is reflexive,
as D
ATALOG
C(
=)
programs are
safe
, i.e., every variable that appears in the head of a rule
also has to appear in its body.
←
•
Third,
Π
Q
includes the rules:
U
(
x
)
←
U
(
x
)
(7.11)
V
(
x
,
y
)
←
V
(
x
,
y
)
(7.12)
U
(
x
)
U
(
u
)
,
E
QUAL
(
u
,
x
)
←
(7.13)
V
(
x
,
y
)
V
(
u
,
v
)
,
E
QUAL
(
u
,
x
)
,
E
QUAL
(
v
,
y
)
.
←
(7.14)
Intuitively, the first two rules create in
U
and
V
acopyof
U
and
V
, respectively. This
allows us to work with copies of
U
and
V
as intensional predicates. The last two rules
replace equal elements in the interpretation of
U
and
V
.
•
Fourth,
Π
Q
includes the following rule representing the query
Q
:
←
V
(
x
,
z
)
∧
V
(
z
,
y
)
∧
U
(
x
)
∧
U
(
y
)
.
E
QUAL
(
x
,
y
)
(7.15)
Intuitively, this rule says that if the certain answer of
Q
is
false
, then for every tuple
(
a
,
b
,
c
) of elements such that the pairs (
a
,
b
) and (
b
,
c
) belong to the interpretation of
V
, and the elements
a
and
c
belong to the interpretation of
U
, it must be the case that
a
=
c
.
•
Finally,
Π
Q
includes one rule for collecting the answer to
Q
:
A
NSWER
←
E
QUAL
(
x
,
y
)
,
C(
x
)
,
C(
y
)
,
x
=
y
.
(7.16)
Intuitively, rule
(7.16)
says that if in the process of evaluating
Π
Q
, two distinct constants
a
and
b
are declared to be equal (E
QUAL
(
a
,
b
) holds), then the certain answer to
Q
is
true
. Notice that this rule makes use of constant-inequalities.
We
show the
application of
the
program with
an
example. Let
S
=
{
be a source instance. It is not hard to see that
the canonical universal solution
T
for
S
is of the form
A
(
a
)
,
A
(
b
)
,
B
(
a
,
c
)
,
B
(
d
,
b
)
,
C
(
c
,
d
)
}
{
U
(
a
)
,
U
(
b
)
,
U
(
⊥
)
,
V
(
a
,
c
)
,
V
(
c
,
⊥
)
,
V
(
⊥
,
d
)
,
V
(
d
,
b
)
}
,
where
⊥
is a null. Recall that
certain
M
(
Π
Q
,
S
)=
Π
Q
(
T
), and hence it is sufficient for us
to study the evaluation of
Π
Q
over
T
.
First, by applying rules
(7.11)
and
(7.12)
we can conclude that
U
(
a
),
U
(
b
),
U
(
⊥
),
V
(
a
,
c
),
V
(
c
,
),
V
(
,
d
) and
V
(
d
,
b
) hold in
T
. Therefore, we obtain by using rule
⊥
⊥