Database Reference
In-Depth Information
Figure 1. Lattice of generalized queries of q (cf. Motro, 1986)
conditions in the query. As an example (cf. Motro, 1986), consider the following query
q
over the Em-
ployees' relation EmpDB:
SELECT *
FROM EmpDB
Q
≡ WHERE Age ≤ 30
AND Gender = F
AND Salary ≥ 40K€.
Figure 1 shows a portion of the lattice of relaxations of
q
generated by SEAVE, where nodes indicate
generalizations (or presuppositions) and arcs indicate generalization relationships. (
x
,
y
,
z
) denotes a
query which returns the employees whose age is under
x
, whose sex is
y
, and whose yearly salary is at
least
z
. The symbol * indicates any value; once it appears in a query, this query cannot be generalized
any further. Assume in this example that
q
fails and all its relaxed queries are successful queries except
those that are marked √ in Figure 1 (i.e.,
q
1
,
q
3
and
q
8
). Thus, the failed relaxed queries
q
1
and
q
3
are
XGFs, whereas the successful relaxed queries
q
2
,
q
4
,
q
6
and
q
15
are MGSs. The queries
q
2
,
q
4
,
q
6
and
q
15
produce alternative answers to the original query
q
: (
q
2
) all employees under 30 who earn at least 40K€;
(
q
4
) all female employees under 32 who earn at least 40K€; (
q
6
) all female employees under 31 who
earn at least 39K€; and (
q
15
) all female employees under 30 who earn at least 37K€. These answers can
be delivered by SEAVE to the user as 'the best it could do' to satisfy the query
q
.
The main drawback of SEAVE is its high computational cost, which comes from computing and
testing a large number of generalizations (i.e., various combinations of the values of attributes) to iden-
tify MGSs/XGFs.
CoBase
The CoBase
iii
(Chu, Yang, Chiang, Minock, Chow & Larson, 1996) system augments the database with
Type Abstraction Hierarchies (TAHs) to control the query generalization process. A TAH represents at-
tribute values at different levels of granularity. The higher levels of the hierarchy provide a more abstract
data representation than the lower levels (or attribute values). Figure 2 shows an example of TAH for
