Transcript Evaluation of Queries

9. Evaluation of Queries
Query evaluation –
1
9.1 Quantifier Elimination and Satisfiability
Example:
Logical Level:
r 
 y1,…yn

r’
Constraint level:
S 
eliminate x

S’
Infinite relation r(x, y1,…yn) equivalent to constraint relation S.
Infinite relation r’(y1,…yn) equivalent to constraint relation S’.
Quantifier elimination – S’ = x S – S’ is equivalent to
eliminating x from S
Closed quantifier elimination – when S’ and S have the
same type of constraints.
2
QE is closed for conjunctions of:
•
•
•
•
•
•
•
•
•
•
Infinite domain equality and inequality
Rational
order
Integer/rational gap-order, lower and upper bound
Integer/rational half-addition, lower and upper bound
Integer/rational gap-order, upper bound, and positive linear
Rational
linear inequality
Real
polynomial inequality
Boolean
equality
Boolean
order
atomless Boolean equality and inequality
3
9.2 Evaluation of Relational Algebra Queries
points(DB) – the logical level infinite relation/database that is
equivalent to the constraint relation/database DB.
For any relational algebra operator/query O on infinite
databases we can always find a finitely evaluable
relational algebra operator/query
databases such that:
ô on constraint
O(points(DB)) = points(ô(DB))
4
Example:
A
X
Y
x
y
B
x–y≥5
X
Y
x
y
x+y<9
C
^
C =A∩ B
X
Y
x
y
x – y ≥ 5, x + y < 9
D
^
D =Aυ B
X
Y
x
y
x–y≥5
X
Y
x+y<9
5
Example:
E
E = A –^ B
X
Y
x
y
x – y ≥ 5, x + y  9
F
^
F = x E = y E
X
Y
x
y
x ≥ 7
6
9.3 Evaluation of SQL queries
Max/Min evaluated by linear programming
if all constraints are linear inequalities.
Example:
SELECT Min(x)
FROM
E
will return 7.
7
9.4 Evaluation of Datalog Queries
Constraint instantiation – substitution of rule body relation
symbols by constraint tuples.
Constraint proof – constraint tuple t0  R0 can be proven in
query Q and database instance I, written t |Q,I R0, if
– t  R0, or
– there is a constraint instantiation
t0(...) :– t1(…), …, tn(…).
where ti |Q,I Ri for 1 ≤ i ≤ n and
t0 = * t1(…), …, tn(…)
where * are variables that appear only in the rule body.
8
Theorem:
The proof-based and the constraint proof-based semantics
are equivalent.
{(a1,…,an):
|Q,I R(a1,….,ak)}
= {points(t):
|Q,I t  R}
9
Datalog evaluation algorithm
Repeat
• do constraint rule instantiation using the
constraint tuples already in the DB
• evaluate the rule, using variable elimination
• add the derived constraint tuple to the DB,
if it is at least partially new
Until any tuple is added to DB
The goal is to prove termination of the above algorithm.
10
Evaluation terminates (in closed-form) for:
•
•
•
•
•
Infinite domain
Rational
Integer/rational
Integer/rational
Boolean
equality and inequality
order
half-addition, lower and upper bound
gap-order, upper bound, positive linear
order
11
Approximate evaluation for integer/rational addition –
Let l be a fixed negative constant. We modify in each
constraint tuple each constraint with bound b < l by:
• changing b to l
to get a lower bound Q(D)l
• deleting the constraint
to get an upper bound Q(D)l
The approximate evaluation terminates and returns
correct upper and lower bounds, that is,
Q(D)l  Q(D)  Q(D)l
also, for any l1 and l2 such that l1 ≤ l2 < 0:
Q(D)l2  Q(D) l1 and Q(D)l1  Q(D)l2
12