Database Reference
In-Depth Information
Table 10.
1
z
00
z
01
z
1000
z
101
z
11
2
z
00
+
z
01
z
1000
+
z
101
z
11
3
z
00
+
z
01
z
1000
+
z
101
+
z
11
4
z
00
+
z
01
+z
1000
+
z
101
+
z
11
Algorithm 2 describes
ESRA
. It is a modified version of
ESA
(Algorithm 1) with the following new
assumptions:
• it returns a summary (
z*
) rather than a list of summaries;
• function AddChild appends a node to caller's children;
• function NumberofChildren returns the number of caller's children;
• function uniqueChild returns the unique child of the caller;
• function BuildIntent builds caller's intent (hyperrectangles) from intents of its children;
•
Z
res
and
Z′
are local variables of type summary.
The
ESRA
cost is only a small constant factor
γ
larger than that of
ESA
. In fact, the rearranging pro-
cess is done at the same time the queried summary hierarchy is being scanned. It means that no post-
processing task (but the query evaluation itself) have to be performed at query time. More precisely, the
time complexity of the
ESRA
Algorithm is in the same order of magnitude (i.e.,
O(L)
) than the
ESA
Algorithm:
L
d
−
−
1
1
T
ESRA
= + ⋅
γ
ε
∈
O L
where the coefficient
γ
is the time cost for the additional operations (addChild, uniqueChild and Build-
Intent).
L
is the number of leaves (cells) of the queried summary hierarchy and
d
its average width.
3.5 Discussion about Extension to any Fuzzy Predicate
A limitation of our proposal relies in the fact that
ESRA
restrains the user to queries using a controlled
vocabulary (i.e., the summary vocabulary). Indeed, consider a user looking for
cheap
houses. What is
meant by
cheap
can vary from one user to another one, or from one kind of users to another one (e.g.,
cheap
does not have the same meaning for house buyers and for apartment tenants). Regarding the
query cost and accuracy, the ideal solution consists in building a summary hierarchy for every user such
that queries and summaries share the same vocabulary. Thus,
ESRA
can be used in its current state. But
maintaining user-specific summaries is hardly conceivable in a system with multiple users. Two alterna-
tives are then envisaged.
The first one is to consider group profiles in order to reduce the number of managed summaries
(e.g., one for buyers and the other for tenants). In this case,
ESRA
can also be used directly since us-
ers formulate queries within the vocabulary of their groups. In this approach, users would subscribe to
