The idea of querying relational databases using keywords emerged a decade ago [4] as a way to provide an high-level access to data and free the user from the knowledge of query languages and data organization. The common approach to this problem is as follows: the database is viewed as a graph G in which the nodes represent tuples and the edges represent foreign key references between them, a query is a set of strings Q (the
Let U be a finite set of attributes and R = {R1(X1), . . . , Rn(Xn)} the schema of a relational database such that the union of the Xi’s is U . We say that an instance r of R (globally) satisfies a set of functional dependencies (FDs) F if there is a relation w on U , called a weak instance for r, that satisfies F and contains the relations of r in its projections over the respective relation schemes, that is: πXi (w) ⊇ ri, for 1 ≤ i ≤ n.
Let Tr for r be tableau formed by taking the union of all the relations in r extended
to U by means of unique variables. The representative instance for r, indicated with
RI r, is the tableau obtained by chasing [
Consider for instance a database scheme with relations R1(ED), R2(DF ), R3(EP ) and the functional dependencies E → D, D → F as constraints. Figures 1 shows a database state on this scheme and the corresponding representative instance. It
r1 Emp Dept John CS Bob EE Ann CS Jim EE
r2 Dept Floor CS 1 EE 5 MS 3
r3 Emp Proj John Nana John Trudy Ann Nana Ann Dante Jim Dante
RI r Emp Dept Floor Proj
t1 John CS 1 Nana
t2 John CS 1 Trudy
t3 Bob EE 5 v1
t4 Ann CS 1 Nana
t5 Ann CS 1 Dante
t6 Jim EE 5 Dante
t7 v2 MS 3 v3
has been shown that a database state is consistent if and only if the corresponding
representative instance can be built without encountering contradictions [
We assume that a keyword query Q is simply a finite and non-empty set of constants. Given a tuple t over X ⊆ U , we say that: (i) t covers a set of constants C if, for each c ∈ C, c = t[A] for some A ∈ X , and (ii) t X-belongs to database r if it belongs to the X -total projection of the representative instance of r (that is: t ∈ πX↓(RI r)). Definition 1 (Base result). A base result (also called 1-result) of a keyword query Q on a database r is a set of complete, total tuples R such that, for every tuple t ∈ R: (i) t covers Q and (ii) t X-belongs to r for some X ⊆ U .
For instance, a base result of the keyword query {CS , Nana} over the database r in Figure 1 is composed by the tuples t1 and t4 of RI r.
Let us now now refine this notion by assuming that the keywords in the query can appear in different tuples of the representative instance that are connected through common values on common attributes. We say that a tableau T is connected if for each t ∈ T there is another tuple t′ ∈ T that is joinable with t (that is, they share values on the same attributes) and that a set of total tuples T covers a set of constants C if each c ∈ C appears in some tuple t ∈ T.
Definition 2 (K-result). A k-result of a keyword query Q on a database r is a minimal set of total tuples Rk such that: (i) Rk has size k, is connected, and covers Q, and (ii) every tuple t ∈ Rk x-belongs to r for some X ∈ U .
For instance, the query {Nana, EE } has one 3-result (R3 = {t4, t5, t6}) and no 2 or 1-results. This shows that the parameter k captures the relevance of the result and then provides an effective tool to order (and possibly limit) the tuples to return to the users. 3
In the framework we have defined, the first question focuses on finding, possibly in an efficient way, the top-k results of a keyword query and the computational complexity of this problem. In this section we provide a preliminary result by discussing the Algorithm that follows, which implements a basic, “brute force” technique for solving this problem.
Algorithm 1: Computation of the top-k results of a keyword query
Input : A consistent database state r, a keyword query Q, a limit k > 0
Output: The Ri-results of Q on r (for 1 ≤ i ≤ k)
1 Build the representative instance T of r;
2 foreach tuple t in T do if t covers Q then output t;
3 for (i = 2; i ≤ k; i ++) do
4 foreach tuple t in T that covers some c ∈ Q do
5 search and return the Ri-results including t with a depth-first visit of T from t;
6 remove t from T
The algorithm consists of three main steps: the construction of the representative
instance (line 1), the search for the R1 results (line 2), and the search for the subsequent
Rk results, for k > 1 (lines 3-6). It is known that the first step requires polynomial
time in the size of the database. In step 2 all the tuples of the representative instance are
checked to verify if they (completely) cover the query and so it requires linear time in
the size of RI r, which is proportional to |r|. Finally, step 3 involves, for each tuple of
RI r that covers some keyword in the query, a depth-limited search in a graph G where
the nodes represent the tuples and the edge represent the joinability relationship. In the
worst case, the cost of this task is proportional to the maximum number of k-long paths
in G, which is bounded by |RI r|k. It is then possibile to show the following result.
Theorem 1. Algorithm 1 computes, for some finite k > 0, all the first k-results of a
keyword query Q of size q over a database state r of size n in time O(nq ).
Algorithm 1 can be optimized in several ways. In particular, the representative instance
does not need to be built since, for significant classes of schemas, its total projection on
a set of attributes can be computed efficiently by means of simple SPJ expressions [