Failing queries are database queries returning few o no results. It might be useful reformulating them in order to retrieve results that are close to those intended with original queries. In this paper, we introduce an approach for rewriting failing queries that are in the disjunctive normal form. In particular, the approach prescribes to replace some of the attributes of the failing queries with attributes semantically related to them by means of Relaxed Functional Dependencies (rfds), which can be automatically discovered from data. The semantics of automatically discovered rfds allow us to rank them in a way to provide an application order during the query rewriting process. Experiments show that such application order of rfds yields a ranking of the approximate query answers meeting the expectations of the user.
A common problem in query processing is coping with failing queries, that is,
queries returning few or no answers. To this end, several techniques have been
proposed to relax queries in order to make them return also approximate
answers, so as to broaden the answer set. Manually relaxing failing queries is a
time-consuming task, and if the query is over-relaxed, prohibitive costs are paid
in terms of bandwidth per returned tuple. Thus, researchers have proposed
automated approaches to query relaxation [15, 17{19], but the existing algorithms
have several limitations, mostly due to a poor knowledge about the
characteristics of the database instance under examination. To this end, automatic data
pro ling techniques are becoming available [
In this paper we describe an approach exploiting Relaxed Functional
Dependencies (rfds) [
Make Example 1. Let us consider the car selling database CarDealerDB of Table 1. There are several usage scenarios for this database. For instance, a user might search cars available for sale or examine detailed characteristics of some speci c models.
Suppose the user is looking for a Ford Focus with a price around 8000$. Then s/he might enter the following query:
Q Model like '%Focus%' AND Price >= 7500 AND Price <= 8500 By executing it on the CarDealerDB no tuples will be returned. However, some similar cars might have characteristics close to the requested one. Such similarities cannot be taken into account by the query, since we assume that no function is available for evaluating the similarity of categorical attributes. To this end, the approach we propose in this paper exploits automatically discovered rfds to rewrite queries so as to enable them generate also approximate results. The semantics of rfds enable us to derive ranking techniques that can be used to decide the application order of rfds during the query rewriting process. To this end, we also provide experimental results proving that such application order yields approximating query answers meeting the expectations of the nal user.
The paper is organized as follows. Section 2 discusses the related work, while Section 3 presents background information on rfds. Then, we describe our query rewriting approach in Section 4 and discuss its empirical evaluation in Section 5. Finally, Section 6 concludes the paper. 2
Approximation in query answering has been extensively studied in the recent
years. Most of the early e orts were devoted to reduce response time by
seeking approximate query answers. Some techniques performed data summaries,
statistics or histograms to compute approximate answers [
The AIMQ query relaxation method removes some constraints from the query
based on approximate functional dependencies [
Muslea proposed a method adopting machine learning to learn rules from the
database [
ORange is a system automatically assisting the user in the process of query
re nement, aiming to satisfy a speci c cardinality constraint [
Finally, the framework proposed in [
In this section we will review the de nition of relaxed functional dependency (rfd).
Consider a relational database schema R de ned over a set of attributes attr(R), derived as the union of attributes from the relation schemas composing R. For an instance r of R and a tuple t 2 r, we use t[A] to denote the projection of t onto A; similarly, for a set X of attributes in attr(R), t[X] denotes the projection of t onto X.
De nition 1. Functional Dependency (fd). An fd over R is a statement X ! Y (X implies Y ), with X; Y attr(R), such that, given an instance r of R, X ! Y is satis ed in r if and only if for every pair of tuples (t1, t2) in r, whenever t1[X] = t2[X], then t1[Y ] = t2[Y ].
In the last part of the fd de nition, we notice that the projections of two
tuples over a subset of attributes are compared by means of the equality function.
This is one of the two dimensions that have been modi ed in order to de ne rfds,
by enabling the use of tuple comparisons based on a similarity constraint. The
latter, de ned as , can be expressed in terms of a similarity metric , such
that a b is true if a and b are \close" enough w.r.t. a prede ned threshold ( ).
Examples of similarity metrics are the edit or the Jaro distance [
Another important characteristic of the fd de nition is that it speci es a
property of the database schema that must hold on every instance of it. This
is the second dimension that has been modi ed to derive a general de nition
of rfd, which admits the possibility that the property might hold for a subset
rather than all the tuples. The latter can be formally speci ed by means of a
condition ltering the tuples on which the dependency applies, or by means a
coverage measure. Given a database instance r of R, and two sets of attributes
X; Y attr(R), representing the Left-Hand-Side (LHS) and Right-Hand-Side
(RHS), resp., of an rfd ', a coverage measure on ' quanti es the amount
of tuples in r violating or satisfying '. It can be de ned as a function :
domX domY ! R, where domA is the domain of attribute A. As an example,
the con dence measure evaluates the maximum number of tuples r1 r such
that ' holds in r1 [
In what follows, we provide a formal de nition of rfd.
De nition 2. Relaxed Functional Dependency (rfd). Consider a relational database schema R, and a relation schema R = (A1; : : : ; Ak) of R. An rfd ' on R is denoted by
Dc : X 1 ! Y 2 (1) where { c = (c1; : : : ; ck) is the set of conditions constraining the domain D on which ' applies; { X; Y attr(R) with X \ Y = ;; { 1 ( 2, resp.) is a set of similarity constraints [X] ( [Y ], resp.). { is a coverage measure de ned on Dc. { is a threshold indicating the bound for the result of the coverage measure.
Given r Dc a relation instance on R, r satis es the rfd ', denoted by r j= ', if and only if: 8 t1; t2 2 r, if [X] indicates true for each constraint 2 1, then almost always [Y ] indicates true for each constraint 2 2. Here, almost always means that ( X (r); Y (r)) .
In other words, if t1[X] and t2[X] agree with the constraints speci ed by 1, then t1[Y ] and t2[Y ] agree with the constraints speci ed by 2 with a degree of certainty (measured by ) greater than .
As an example, in a database of scienti c publications it is likely to have the same address and a liation for authors with the same name. Thus, an fd fAuthorg ! fAddress, Affiliationg might hold. However, these attributes might have been stored using di erent abbreviations. Thus, the following rfd might hold:
err(0!) fAddress ; Affiliation g where is a string similarity function, and err(0) corresponds to the expression (X; Y ) = 0, where (X; Y ) measures the number of tuples violating the rfd. However, authors might change a liation during their life, or there might be homonimies, possibly caused by rst name abbreviations. As a consequence, the previous rfd should tolerate possible exceptions. This can be modeled by introducing a di erent coverage measure into the rfd, making it conditional:
(Author;Address;Affiliation) 0:02 ! fAddress ; Affiliation g 4
Let us consider the car selling database (CarDealerDB) shown in Table 1. Among several usage scenarios for this database, let us consider one in which a user might search cars available for sale or examine detailed features for some speci c car models. In particular, suppose the user is looking for a Ford Focus with a price around 8000$. Then s/he might enter the following query:
Q
Model like '%Focus%' AND Price >= 7500 AND Price <= 8500
By executing this query on CarDealerDB no tuples will be returned as result. However, some cars close to the query request might be returned, if we were capable of evaluating the similarity of categorical attributes. To this end, we propose an approach exploiting rfds, in order to rewrite a query so as to enable it generate approximated results. The rewriting process consists in replacing attributes instantiated in the query with those related to them by means of rfds. As an example, let us assume that the rfd
Dtrue : Model t (Model;Length) 0:1 ! Length n holds on CarDealerDB, where t and n are proper text and numerical similarity functions, respectively. The rfd says that in 90% of cases, cars with similar models (categorical attribute) must have similar length (numeric attribute). We can therefore infer that, cars whose Length is similar to the Focus one are more suitable to be returned as result.
More generally, let us suppose that a query Q has a condition X OP x, where OP is a comparison operator, and the following rfd holds on the underlying database:
Dtrue : X f
(X;Y )
! Y g
then we might rewrite Q in Q1 OR : : : OR Qm, where Qi is obtained from Q
by replacing the condition X OP x with a condition Y g yi, where yi is the
value of Y for a tuple in which X OP x. Such process can be better formalized
by using similarity subsets generated by inference algorithms for rfds [
From the example in Table 1 it follows that cars with Model like '%Focus%' satisfy either Length = 4337 or Length = 4342. Thus, Q can be rewritten into Q1 OR Q2, where: Q1 Length 4337 "i AND Length 4337+"i AND Price 7500 AND Price 8500 Q2 Length 4342 "i AND Length 4342+"i AND Price 7500 AND Price 8500
When computing Q1 and Q2 for "i = 250, we get the tuple t2 as result, which corresponds to a Mazda 3, since its Length is similar to the one of Focus, and the Price matches the one of the original query.
It is worth to note that the attribute X of the query Q can also be a portion of the LHS of some rfds, e.g.,
Dtrue : A f1 X f2 B f3 (A;X;B;Y ) ! Y g In this case, supposing that A, B, Y are textual attributes, we relax Q by replacing X OP x with a condition \(Y g y1 AND A f1 a1 AND B f3 b1) OR : : : OR (Y g yn AND A f1 an AND B f3 bn)", where yi is the value of Y for a tuple in which X OP x, A OP ai, and B OP bi. Thus, we do not consider the whole Y g y category, but its subset consisting of the tuples having the values for A and B similar to one of the tuples where X OP x. For instance, since the following dependency
Dtrue : Model f1 Power f2 EngineCC f3 (X;Y ) 0:0!5 Torque g holds on the CarDealearDB, we can relax the condition Model like '%Focus%' with ((Torque 240 AND Torque 280) AND (EngineCC 1530 AND EngineCC 1590) AND (Power 75 AND Power 85)) OR ((Torque 250 AND Torque 290) AND (EngineCC 1530 AND EngineCC 1590) AND (Power 80 AND Power 90)) OR ((Torque 130 AND Torque 170) AND (EngineCC 1566 AND EngineCC 1626) AND (Power 68.8 AND Power 78.8)).
However, in practice the rewriting process of the query might be accomplished
according to di erent rfds. Hence, we need to establish a priority in the
application of the di erent rfds during the relaxation process, so as to meet user
preferences. To this end, we found out that current rfd discovery algorithms
rank the extracted rfds based on the coverage and similarity thresholds [
Lymphography 0.82 0.93
Table 2. Precision and recall obtained for the considered datasets. 5
We evaluated the proposed approach on three di erent datasets. In particular,
we considered the Breast-cancer, the Hepatitis, and the Lymphography datasets
drawn from the UC Irvine Machine Learning repository [
In order to evaluate the performances of the proposed approach, we have de ned 5 failing queries for each considered dataset. Successively, we have requested a domain expert to analyze the datasets and the queries in order to identify the ten tuples most similar to the target result of each query (ground truth). Finally, we have (i) applied the proposed approach to rewrite the ve failing queries, (ii) run them on the considered dataset, and (iii) compared their results to the ground truth.
We measured the e ectiveness of the proposed approach with precision and
recall. Let A be the set of tuples obtained from the queries generated by the
proposed approach and B the ground truth identi ed by the expert. Then, we
computed the precision as jA \ Bj=jAj, while recall as jA \ Bj=jBj [
As we notice, we obtained high values for both measures, especially the recall. We can observe that the number of rfds impacts on the quality of the resulting queries. This is due to the fact that ranking strategies used in current rfd discovery algorithms su er from some noise when the datasets contain many rfds. 6
We have described an approach for rewriting failing queries that are in
disjunctive normal form [
In the future we plan to de ne new ranking strategies for rfds, in order to better re ne their application order, and to further improve the performances of the proposed query rewriting technique. Moreover, we are currently investigating further query rewriting rules exploiting additional semantic properties of rfds.