Database Reference
In-Depth Information
Expressive power of D ATALOG C( =) programs
With respect to the expressive power of D ATALOG C( =) programs, it is possible to prove
that they are capable of subsuming, in terms of certain answers, the class of unions of
conjunctive queries with at most one negated atom per disjunct (in the absence of target
dependencies).
Theorem 7.8
Σ st ) be a mapping and let Q be a union of conjunctive
queries with at most one inequality or negated relational atom per disjunct. Then there ex-
ists a D ATALOG C( =) program
Let
M
=(R s , R t ,
Π Q such that for every source instance S, certain M ( Q , S )=
certain M (
Π Q , S ) .
It immediately follows that computing certain answers for this class of queries is
tractable:
Corollary 7.9
Σ st ) be a relational mapping and let Q be a union of
conjunctive queries with at most one inequality or negated relational atom per disjunct.
Then CERTAIN M ( Q ) can be solved in P TIME .
Let
M
=(R s , R t ,
The proof of Theorem 7.8 , although not too difficult, is quite technical. For our purposes
it will be sufficient to illustrate the basic ideas behind this proof with an example.
Example 7.10 Let
Σ st ) be a L AV mapping such that R s consists of a unary
relation A and binary relations B and C ,andR t consists of a unary relation U and a binary
relation V .Let
M
=(R s , R t ,
Σ st consist of the following st-tgds:
A ( x )
U ( x )
B ( x , y )
V ( x , y )
C ( x , y )
→∃
z ( V ( x , z )
V ( z , y )
U ( z )) .
Let Q be the following Boolean conjunctive query with one inequality:
x
y
z ( V ( x , z )
V ( z , y )
U ( x )
U ( y )
x
= y ) .
a D ATALOG C( =)
We
construct
program
Π Q
such that
certain M ( Q , S )=
Π Q , S ), for every source instance S . The set of intensional predicates of
the D ATALOG C( =) program
certain M (
Π Q consists of the unary predicate U , the binary predicate V ,
the unary predicate D OM , and the distinguished 0-ary predicate A NSWER . The program
Π Q over R t is defined as follows.
First, the program collects in D OM ( x ) all the elements that belong to the domain of the
instance of R t where
Π Q is evaluated:
D OM ( x )
V ( x , y )
(7.5)
D OM ( x )
V ( y , x )
(7.6)
D OM ( x )
U ( x ) .
(7.7)
Search WWH ::




Custom Search