Database Reference
In-Depth Information
We consider two cases. Suppose first that there is a pair ( c , d ) of elements in D OM ( T 1 )
such that ( c , d )
G T 1
and for some element e
D OM ( T 1 ) it is the case that both ( c , e )
and ( e , d ) are in G T 1 . Then clearly, T 1 |
=
x
y
z ( G ( x , z )
G ( z , y )
∧¬
G ( x , y )), and, thus,
= Q . Suppose, on the other hand, that this is not the case. Then G T 1 contains its own
transitive closure. Moreover, G T
T 1 |
G T 1 ,since T 1 is a solution for S , and hence from the
previous observation the transitive closure of G T
is also contained in G T 1 . We conclude
G T 1 , and, therefore, T 1
that ( a , b )
= Q ).
Assume, on the other hand, that for every pair ( a , b ) in the transitive closure of G T
|
=
x
y ( P ( x )
R ( y )
G ( x , y )) (and hence T 1
|
it
R T . Consider the target instance T 1 that extends T
by adding to the interpretation of G every tuple in the transitive closure of G T . It is clear
then that T 1 | = Q . Indeed, T 1 | = x y ( P ( x ) R ( y ) G ( x , y )) because G T 1 coincides with
transitive closure of G T and hence there is no pair ( a , b ) in G T 1 such that both a P T 1 and
b R T 1 . Moreover, T 1 |
P T
is the case that either a
or b
∧¬ G ( x , y )) because G T 1 coincides with
its own transitive closure. We conclude that certain M ( Q , S )= false .
Since transitive closure is polynomial-time computable, we have proved the first state-
ment of the theorem. Moreover, it is well known that there is no FO (i.e., relational algebra)
query that expresses the transitive closure of a graph, which shows the second statement of
the theorem.
=
x y z ( G ( x , z )
G ( z , y )
The example used in the above proof also shows that negated relational atoms add ex-
pressive power to the class of unions of conjunctive queries in the context of data exchange,
as they express interesting data exchange properties (e.g., transitive closure) that go way
beyond the ones that can be expressed by means of relational algebra queries.
Tractable query answering beyond relational algebra
To retain good properties of query answering in data exchange beyond relational algebra,
ideally we should start with the language for which naıve evaluation computes certain
answers (i.e., (7.3) holds), and then extend it with a limited form of negation. It is known
that the class of unions of conjunctive queries is not the only language that satisfies (7.3) ;
in fact, queries expressible in D ATALOG , the recursive extension of the class of unions
of conjunctive queries are also such, and they have polynomial time data too. (For the
reader who is not familiar with D ATALOG , we review its syntax and semantics later in this
section). Thus, D ATALOG retains several of the good properties of unions of conjunctive
queries for data exchange purposes. In particular, certain answers to a D ATALOG program
Π
over a source instance S can be computed efficiently by first materializing a canonical
universal solution T for S , and then evaluating
over T .
However, as we proved in Theorem 7.4 , adding an unrestricted form of negation to
D ATALOG (or even to the class of conjunctive queries) easily yields to intractability of the
problem of computing certain answers (even for mappings without target dependencies).
Despite this negative result, it can still be shown that there is a natural way to add negation
to D ATALOG while keeping all of the good properties of this language for data exchange. In
Π
Search WWH ::




Custom Search