Database Reference
In-Depth Information
This problem, which is known as
empty-answer
problem, happens when the user submits a very
restrictive query. A simple way to remedy this problem is to retry a particular query repeatedly with
alternative values of certain conditions until obtaining satisfactory answers from a database. This solu-
tion, however, can be applied only if the user is aware of the close alternatives, otherwise it is infeasible
(especially for users who lack knowledge about the contents of the database they wish to access). Many
techniques are proposed to overcome this problem, namely query relaxation (Section 2.1.1) and similar-
ity based search (Section 2.1.2).
2.1.1 Query Relaxation
Query relaxation aims to modify the failed query to provide the user with some alternative answers or
at least to identify the cause of the failure, rather than just to report the empty result. A database sys-
tem with such capability is also known as a cooperative information system (Gaasterland, Godfrey &
Minker, 1994).
Consider a database EmpDB with information on employees, including their Name, Age, Gender,
Salary, Job and Department, and a query '
get all employees who make less than 15K€ and work in the
R&D department
'. Note that this query may fail for two different reasons (Motro, 1986): either no em-
ployee in R&D department makes less than 15K€ or the company does not have an R&D department.
The former is a genuine null answer (i.e., the null answer is appropriate since query fails to match any
data), while the latter is a fake null answer (i.e., it is due to the erroneous presupposition that the com-
pany has an R&D department).
The first system (CO-OPi)
i
) with such human behavior was developed by Kaplan (Kaplan, 1983) and
was designed for natural language interaction. The main idea of CO-OP is to follow up a query that
failed with several more general queries (i.e., the query with some of its conditions relaxed). If even
these general queries fail, then the conclusion is that some of the presuppositions of the user who com-
posed the original query are erroneous. If all these general queries succeed, a query that fails produces
a genuine null. Furthermore, assume
q′
and
q′′
are both relaxations of the failed query
q
, but
q′′
is more
general than
q′
. If both succeed, then the partial answer returned by
q′
is better (i.e., the best the system
could do to satisfy the initial query
q
). If both fail, then the erroneous presupposition indicated by
q′′
is stronger. This leads to the conclusion that only Minimal Generalizations that Succeed (MGSs) and
maXimal Generalizations that Fail (XGFs) are significant. Indeed, XGFs provide explanation for the
failure and some assistance for relaxing the query into a non-failing query, whereas MGSs produce
alternative answers to the failing query.
Since then, several systems that adapt CO-OP's techniques to relational databases have been pro-
posed, including SEAVE (Motro, 1986), CoBase (Chu, Yang, Chiang, Minock, Chow & Larson, 1996)
and Godfrey's system (Godfrey, 1997). These systems differ only in the way they perform generaliza-
tions. SEAVE considers all possible generalizations of the query. CoBase uses prior knowledge of the
domain to guide the generalization process. Godfrey's system generalizes the query by only removing
some of its conditions.
SEAVE
Given a query that fails, SEAVEii
ii
(Motro, 1986) constructs a lattice of its generalized queries and uses
it to find all MGSs/XGFs. The query generalizations are obtained by relaxing to a degree some of the
