Database Reference
In-Depth Information
Figure 2. TAH defined on the attribute Salary
attribute Salary in which unique salary values are replaced by qualitative ranges of high, medium, or
low. To relax a failing query, CoBase uses some types of TAH-based operators such as generalization
(moving up the TAH) and specialization (moving down the TAH). For example, based on the type ab-
straction hierarchy given in Figure 2, the condition 'Salary = 20K€' could be generalized (i.e., move-up
operator) to 'Salary = medium'.
CoBase considerably reduces the number of generalizations to be tested. Note that how close the
results are to the user's initial expectations depends on the TAHs used.
Godfrey's System
In (Godfrey, 1997), Godfrey proposed to generalize the user failed query by just removing some of its
conditions. Thus, instead of searching all MGSs/XGFs, the proposed system looks for all maXimal Suc-
ceeding and Minimal Failing Sub-queries (XSSs and MFSs, respectively) of the failed query. The author
also proves that this problem is NP-hard. Indeed, the size of the search space grows exponentially with
the number of attributes used in the failed query, i.e., if a query involves m attributes, there exist ( 2 m − 2 )
sub-queries that have to be examined, disregarding the query itself and the empty query . For instance,
the lattice of the possible sub-queries of q is illustrated in Figure 3, using the same notation as in Figure 1.
Hence, recently some heuristics (Muslea, 2004; Muslea & Lee, 2005; Nambiar & Kambhampati,
2004) have been proposed to prune the search space. In (Muslea, 2004) and (Muslea & Lee, 2005),
Muslea et al. respectively used decision tree and Bayesian network learning techniques on a randomly-
chosen subset of the target database to identify potential relaxations (or sub-queries) of the failing
query to be tested. Then, they use nearest-neighbor techniques to find the relaxed query that is the most
similar to the failing query. Nambiar et al. (Nambiar & Kambhampati, 2004) employed approximate
Figure 3. Lattice of possible sub-queries of q
Search WWH ::




Custom Search