Database Reference
In-Depth Information
M
Algorithm 7.1 C OMPUTE C ERTAIN A NSWERS ( Q ,
)
Require: A source instance S
Ensure: If S OL M ( S )
= 0, then CA is the set of certain answers for Q over S under
M
.
Otherwise, CA = fail
1: let T be the result of a successful chase sequence of S under
M
2: if T = fail then
3: CA := fail
4: else
5: CA := Q naıve ( T )
6: end if
keep us in the realm of the positive while most database query languages are equipped
with negation. What happens if we extend conjunctive queries with a restricted form of
negation? Do we retain the good properties mentioned above? We deal with this problem
in the next section.
7.3 Conjunctive queries with inequalities
In the previous section we raised the following question: What happens in the data ex-
change context if we extend conjunctive queries with a restricted form of negation? We
study this problem for a particular class of queries, namely, conjunctive queries with in-
equalities . This class of queries is of practical importance, and corresponds to a natural and
common subclass of SQL queries, namely those that have conjunctions of equalities and
inequalities in the where clause.
Formally, a conjunctive query with inequalities is an FO-query of the form
ϕ
( x )=
y
ψ
( x , y ),where
ψ
( x , y ) is a conjunction of
atomic relational formulae, and
inequalities of the form z 1
= z 2 , where the variables z 1 and z 2 come from x and y .
We impose a simple safety condition that every variable that appears in an inequality must
also appear in a relational atom. For example,
y ROUTES ( y , x , z )
= y
ROUTES ( y , x , z )
ϕ
( x , z )=
y
y
(7.2)
is a conjunctive query with one inequality that asks for pairs ( a , b ) of cities such that there
is more than one flight from a to b .
Thus, conjunctive queries with inequalities are capable of expressing interesting and
natural properties of data. Now we would like to see how they behave in data exchange. For
instance, is it true that certain answers to a conjunctive query with inequalities Q coincide
with the naıve evaluation of Q over some universal solution? The following simple example
shows that with inequalities, naıve evaluation fails.
Search WWH ::




Custom Search