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
Search WWH ::




Custom Search