Database Reference
In-Depth Information
c:
no decision can be made (i.e.,
∧
A
∧
X,z.A
-
Q
A
≠
φ
). There is one attribute
A
for which
z
exhibits one
or many linguistic labels besides those strictly required (i.e., those in
Q
A
). The presence of required
features in each attribute of
z
suggests, but does not guarantee, that results may be found in the
subtree rooted by
z
. Exploration of the subtree is necessary to retrieve possible results: for each
branch, it will end up in situations categorized by case
a
or case
b
. Thus, at worst at leaf level, an
exploration leads to accepting or rejecting summaries; the indecision is always solved.
The situations stated above reflect a global view of the matching of a summary
z
with a query
Q
.
3.2.3 Search Algorithm
The Explore-Select Algorithm (
ESA
) applies the matching procedure from the previous section over
the whole set of summaries, organized in a hierarchy, to select relevant summaries. Since the selection
should take into account all summaries that correspond to the query, the exploration of the hierarchy is
complete. Algorithm 1 (shown on the next page) describes
ESA
with the following assumptions:
•
the function returns a list of summaries;
•
function Corr symbolizes the matching test reported in Section 3.2.2;
•
operator '+' performs a list concatenation of its arguments;
•
function Add is the classical constructor for lists, it adds an element to a list of the suitable type;
•
Lres is a local variable.
The
ESA
algorithm (see Algorithm 1) is based on a depth-first search and relies on a property of the
hierarchy: the generalization step in the SAINTETIQ model guarantees that any label that exists in a
node of the tree also exists in each parent node. Inversely, a label is absent from a summary's intent if
and only if it is absent from all subnodes of this summary. This property of the hierarchy permits branch
cutting as soon as it is known that no result will be found. Depending on the query, only a part of the
hierarchy is explored.
Thus, results of Q
1
(Example 3.1), when querying the hierarchy shown in Figure 17, look like Table 9.
In this case, the
ESA
algorithm first confronts
z
(root) with
Q
1
. Since no decision can be made,
Q
1
is
respectively confronted to
z
0
and
z
1
, the children of
z
. The subtree rooted by
z
0
is then ignored because
there is no correspondence between
Q
1
and
z
0
. Finally
z
1
is returned because it exactly matches
Q
1
. Thus,
the process tests only 30% of the whole hierarchy.
Note that, the set of records
R
z
summarized by z
1
can be returned if the user requests it (SHOW-
TUPLES option). This is done by simply transforming the
intent
of z
1
into a query
q
z
1
and sending it as
a usual query to the database system. The WHERE clause of
q
z
1
is generated by transforming the lin-
guistic labels (fuzzy sets) contained in the intent of z
1
into crisp ones. In other words, each linguistic
label
l
on an attribute
A
is replaced by its support, i.e., the set of all values in the domain of
A
(
D
A
) that
belong to
l
with non-zero membership. Then, the obtained crisp criteria on each summary's attribute are
connected with OR operator and summary's attributes are connected with AND operator to generate the
WHERE clause. Thus, performing a SHOWTUPLES operation takes advantage of the optimization
mechanisms that exist in the database system. Furthermore, tuples covered by z
1
can also be sorted,
thanks to their satisfaction degrees to the user's query, using an overall satisfaction degree. We assign
