Practical Approaches to the Many-Answer Problem - Advanced Database Query Systems - page 67

Algorithm 1.

Function Explore-Select(z,Q)
L res ←
if Corr(z,Q) = indecisive then
for all child node z child of z do
L res ← L res + Explore-Select(z child ,Q)
end for
else
if Corr(z,Q) = exact then
Add(z, L res )
end if
end if
return L res

to each tuple the degree to which it satisfies the fuzzy criteria of the query. Usually, the minimum and
maximum functions stand for the conjunctive and disjunctive connectives. There are many propositions
in the literature for defining aggregation connectives (Klement, Mesiar & Pap, 2000).
The ESA algorithm is particularly efficient. In the worst case (exploration of the hierarchy is com-
plete), its time complexity is given by:

L
d

−
−

1
1

T

ESA =

e ∈ O L

where L is the number of leaves (cells) of the queried summary hierarchy, d its average width and coef-
ficient ε corresponds to the time required for matching one summary in the hierarchy against the query.
In the above formula, L
d

-
-

1
1

gives an estimation of the number of nodes in the summary hierarchy.

In the following subsection, we discuss how ESA 's answers help facing the many-answers problem.

3.3 Multi-Scale Summarized Answers

Given a query Q , the ESA algorithm produces a set of clusters (summaries) from a SAINTETIQ hierarchy
instead of a list of tuples tset(Q) . Each answer item z describes a subset of the query result set tset(Q) .
Hence, the user can unambiguously determine whether R z contains relevant tuples only by looking at
the intentional description of z and particularly on unspecified attributes ( Y ) because all answer tuples
satisfy the specified conditions related to attributes in X . Three cases might occur:

1: summary z doesn't fit the user's need. It means that for at least one unspecified attribute AY , all
linguistic labels (the set z.A ) are irrelevant to the user. For instance, consider the Q 1 results (Table
9). z 1 doesn't contain any relevant tuple if the user is actually looking for very cheap houses because
very cheapz 1 .Price. In other words, none of the records in R z 1 is mapped to very cheap on attribute