Database Reference
In-Depth Information
2. DATA AND QUERY MODEL
The second property is that U-databases are closed under Unions of Conjunctive Queries in
a very strong sense.
D 1 ,...,D n
be the worlds represented by D . Then,
for any UCQ query Q, we can compute a UCQ query Q in time polynomial in the size of Q such that the
U-relation Q ( D ) represents
Let D be any U-database and
{
}
Proposition 2.24
Q(D 1 ),...,Q(D n )
{
}
.
In other words, we can push the computation of the representation of the answers to Q inside
the database engine: all we need to do is to evaluate a standard UCQ query Q , using standard
SQL semantics, on the database D , then interpret the answer Q ( D ) as a U-relation. Instead of a
formal proof, we illustrate the proposition with an example: the proof follows by a straightforward
generalization.
Example 2.25 (Continuing Example 2.14 ) Recall that in this example, we have two tuple-
independent tables, R(A)andS(A, B) , and we compute the query:
Q(x, x ) :- R(x), S(x, y), S(x , y), R(x )
Since the tables are tuple-independent, we can represent them using the following two U-relations:
T R (V , A) and T S (V,A,B) : for example, if R ={ a 1 ,a 2 }
, where
X 1 ,X 2 are two arbitrary but distinct identifiers for the two tuples. Our goal is to compute a U-relation
representation of the output to the query Q(x, x ) . As we saw, its lineage consists of conjuncts with
up to four atomic predicates, and therefore we represent its output as T Q (V 1 ,V 2 ,V 3 ,V 4 ,A,A ) . The
query that computes this representation is:
, then T R ={ (X 1 ,a 1 ), (X 2 ,a 2 ) }
Q (v 1 ,v 2 ,v 3 ,v 4 ,x,x ) :- T R (v 1 , x), T S (v 2 ,x,y),T S (v 3 ,x , y), T R (v 4 ,x )
For example, if we execute this query on the instance given in Example 2.9 , then we obtain the same
result as in Example 2.21 , except that the NULL entries for V 3 ,V 4
are replaced with the values
of V 1 ,V 2 : for example, the first row (X 1 ,Y 1 ,
,a 1 ,a 1 ) becomes now (X 1 ,Y 1 ,X 1 ,Y 1 ,a 1 ,a 1 ) .
Clearly, this has the same meaning when interpreted as a propositional formula because by the
idempotence law we have X 1 Y 1 =
,
X 1 Y 1 X 1 Y 1 .
This example can be generalized to a complete proof for Proposition 2.24 . It also illustrates
the appeal of U-databases: they can conveniently represent query answers if the query is restricted
to UCQ. Note that if we allow negations in the query, then Proposition 2.24 no longer holds in
this strong form. While we can always compute a U-relation that represents Q( D ) , its schema may
depend on the database D , and its instance may be exponentially larger than the input D and,
therefore, not a natural representation of the result. The reason is because U-relations are designed
to represent k -DNF formulas, for some fixed k : the negation of such a formula is no longer a k -DNF
and turning it into DNF can require an exponential blowup.
Search WWH ::




Custom Search