Database Reference
In-Depth Information
Physical Operators
When applying fuzzy queries, the Fuzzy Query Tree is converted into a fuzzy relational tree, where the
physical operators of Selection, Projection and Join must use the fuzzy relational algebra theory. We
obtain a fuzzy relation as the result of applying a fuzzy physical operator to classical relations that is
why we have to record the membership degree for each resulting row.
Fuzzy Selection
For the classical selection, there are various algorithms denominated file scans because we have to scan
all the records and obtain only rows that accomplish the condition of the query. If the scan algorithm
involves an index, we denominate it index scan. The most frequently used algorithms for implementing
an ordinary condition are: lineal search (naïve), binary search (if file is sorted), using a primary index,
using a cluster index or using a secondary index (B
+
tree) over an equal condition.
In this case we extended the file scan, index scan and bitmap heap scan to calculate the membership
degree of each row when the base table is annotated with a fuzzy term (there is a linguistic label over a
linguistic variable); furthermore these physical operators record the membership degree of each fuzzy
row in order to propagate it bottom-up through the execution plan.
The membership is computed applying the theoretical frame of Fuzzy Sets, when we have a member-
ship function (i.e. trapezoidal) we take the value of the linguistic variable and apply the corresponding
membership function. When we have Boolean connectors in a fuzzy condition we use minimum (AND),
maximum (OR) or complement (NOT) as 1 - μ
x
.
Fuzzy Projection
This operator only has to delete the attributes that are not projected and record the membership degree
of each fuzzy row. When duplicates need to be deleted (Distinct clause) we have to apply a partition
access mechanism for the project attributes, and furthermore, calculate the maximum (t-conorm mostly
used) membership degree when we have equal rows. The membership degree is propagated bottom up
through the execution plan.
Fuzzy Join
We extended this operator when at least one involved relation is fuzzy, that is, it arises from the ap-
plication of a fuzzy access mechanism or from another fuzzy relational operator. If any of the relations
is classical we assumed that the membership degree is one (1), in accordance with the theory of Fuzzy
Sets (each row pertains completely to the Fuzzy Set). With these conditions, we only have to compute
the minimum (t-norm mostly used) for each pair of rows and record it to propagate bottom-up through
the execution plan. So we extended the nested loop join, hash join and merge join.
Optimizer
The fuzzy querying engine optimizer module takes the Fuzzy Query Tree arising from the parser module
and uses the same algorithm to optimize a classical query (i.e. query optimizer from System R). This
