The Deep Web is constituted by data that are accessible through Web pages, but not indexable by search engines as they are returned in dynamic pages. In this paper we propose a conceptual framework for answering keyword queries on Deep Web sources represented as relational tables with so-called access limitations. We formalize the notion of optimal answer and characterize queries for which an answer can be found.
r1 =
IT John t11 AI Mike t12 r2 =
John P1 t21 Ann P2 t22 Mike P2 t23 r3 =
P1 John DBA t31 P1 Ann Analyst t32 Relation r1 represents a form that, given a department, returns all the employees working in it; relation r2 a form that, given an employee, returns all the projects he/she works on; and relation r3 a form that, given a project, returns the employees working in it along with their role. These access modalities are commonly referred to as access limitations, in that data can only be queried according to given patterns.
Di erent approaches have been proposed in the literature for querying
databases with access limitations: conjunctive queries [
Consider for instance the case in which the user only provides the keywords \DBA" and \IT" for querying the portion of the Deep Web represented by the relations above. Intuitively, he/she is searching for employees with the DBA role in the IT department. Given the access limitations, this query can be concretely answered by rst accessing relation r1 using the keyword IT, which allows us to extract the tuple t11. Then, using the value John in t11, we can extract the tuple t21 from relation r2. Finally, using the value P1 in t21, we can extract the tuples t31 and t32 from relation r3. Now, since t31 contains DBA, it turns out that the set of tuples ft11; t21; t31g is a possible answer to the input query in that the set is connected (every two tuples in it share a constant) and contains the given keywords. However, the tuple t21 is somehow redundant and can be safely eliminated from the solution, since the set ft11; t31g is also connected and contains the keywords. This example shows that, in this context, the keyword query answering problem can be involved and tricky, even in simple situations.
In the rest of this paper, we formally investigate this problem in depth. We rst propose, in Section 2, a precise semantics of (optimal) answer to a keyword query in the Deep Web. We then tackle, in Section 3, the problem of nding an answer to a keyword query by assuming that the domains of the keywords are known in advance. This allows us to perform static analysis to immediately discard irrelevant cases from our consideration. Section 4 ends the paper with some conclusions and future works.
Related work To the best of our knowledge, ours is the rst comprehensive approach to the problem of querying the Deep Web using keywords. Other works addressed keyword search on relational data previously extracted from the Deep Web [?]. This paper reports results previously published in [?], the paper where we illustrate our techniques for keyword search in the Deep Web.
The problem of query processing in the Deep Web has been widely
investigated in the last years, with di erent approaches and under di erent perspectives
including: data crawling [
The idea of querying structured data using keywords emerged more than a
decade ago [
The various approaches to keyword query answering over relational databases
are commonly classi ed into two categories: schema-based and schema-free.
Schema-based approaches [
We model data sources as relations of a relational database and we assume that, albeit autonomous, they have \compatible" attributes. For this, we x a set of abstract domains D = fD1; : : : ; Dmg, which, rather than denoting concrete value types (such as string or integer), represent data types at a higher level of abstraction (for instance, car or country ). Therefore, in an abstract domain an object is uniquely represented by a value. The set of all values is denoted by D = Sn
i=1 Di. For simplicity, we assume that all abstract domains are disjoint. We then say that a (relation) schema r, customarily indicated as r(A1; : : : ; Ak), is a set of attributes fA1; : : : ; Akg, each associated with an abstract domain dom(Ai) 2 D, 1 i k. A database schema S is a set of schemas fr1; : : : ; rng.
As usual, given a schema r, a tuple t over r is a function that associates a value c 2 dom(A) with each attribute A 2 r, and a relation instance rI of r is a set of tuples over r. For simplicity, we also write dom(c) to indicate the domain of c. A (database) instance I of a database schema S = fr1; : : : ; rng is a set of relation instances fr1I ; : : : ; rIng, where riI denotes the relation instance of ri in I.
For the sake of simplicity, in the following we assign the same name to attributes of di erent schemas that are de ned over the same abstract domain. De nition 1 (Access pattern). An access pattern for a schema r(A1; : : : ; Ak) is a mapping : fA1; : : : ; Akg ! M , where M = fi; og is called access mode, and i and o denote input and output, respectively; Ai is correspondingly called an input (resp., output) attribute for r wrt . Henceforth, we denote input attributes with an `i' superscript, e.g., Ai. Moreover, we assume that each relation has exactly one access pattern.
; any tuple b = hc1; : : : ; c`i such that ci 2 dom(A0i) for 1 i ` is called a binding for r wrt .
for a schema r and b is a binding for r wrt . The output of such an access on an instance I is the set T of all tuples in the relation rI 2 I over r that match the binding, i.e., such that T = A1=c1;:::;A`=c` (r): Intuitively, we can only access a relation if we can provide a binding for it, i.e., a value for every input attribute.
a set of access patterns for the relations in S, and a set of values C D, an access path on I (for S, and C) is a sequence !b1r1I T1 !b2r2I !bnrnI Tn, where, for 1 i n, (i) bi is a binding for a relation ri 2 S wrt a pattern i 2 for ri, (ii) Ti is the output of access h i; bii on I, and (iii) each value in bi either occurs in Tj with j < i or is a value in C.
De nition 5 (Reachable portion). A tuple t in I is said to be reachable given C if there exists an access path P (for S, and C) such that t is in the output of some access in P ; the reachable portion reach(I; ; C) of I is the set of all reachable tuples in I given C.
In the following, we will write S
to refer to schema S under access patterns Example 1. Consider the following instance fr1(Ai; B); r2(Bi; A); r3(Ai; B; C)g.
Ai B Then, for instance, ft11g is the output of the access with binding ha1i wrt r1(Ai; B), and h!a1ri1I ft11g h!b1ri2I ft21; t23g, is an access path for S, and C = fa1g, since, given C, we can extract t11 from r1 and, given fb1g from t11, we can extract t21 and t23 from r2. The reachable portion of I, given C, is reach(I; ; C) = ft11; t12; t21; t23; t31; t33g, while ft22; t32g \ reach(I; ; C) = ;. Figure 1a shows the reachable portion I0 of I given C along with the access paths used to extract it, with dotted lines enclosing outputs of accesses. The de nition of answer to a keyword query in our setting requires the preliminary notion of join graph.
De nition 6 (Join graph). Given a set T of tuples, the join graph of T is a node-labeled undirected graph hN; Ei constructed as follows: (i) the nodes N are labeled with tuples of T , with a one-to-one correspondence between tuples of T and nodes of N ; and (ii) there is an arc between two nodes n1 and n2 whenever the tuples labeling n1 and n2 have at least one value in common.
A1
A2
A keyword query (KQ) is a non-empty set of values in D called keywords. De nition 7 (Answer to a KQ). An answer to a KQ q against a database instance I over a schema S is a set of tuples A in reach(I; ; q) such that: (i) each keyword k 2 q occurs in at least one tuple t in A; (ii) the join graph of A is connected; (iii) no proper subset A0 A satis es both Conditions (i) and (ii) above.
It is straightforward to see that there could be several answers to a KQ; below
we give a widely accepted criterion for ranking such answers [
that A1 is better than A2 if jA1j jA2j. The optimal answers are those of minimum size.
Example 3. Consider a KQ q = fa1; c1g over the instance I of Example 1. Figure 1a shows two possible answers: A1 = ft11; t31g and A2 = ft11; t23; t33g. A1 is better than A2 and is the optimal answer to q. 3
For convenience of notation, we sometimes write c : D to denote value c and indicate that dom(c) = D. In addition, in our examples, the name of an attribute will also indicate its abstract domain. 3.1
In order to focus on meaningful queries, we semantically characterize queries for which an answer might be found.
De nition 9 (Compatibility). A KQ q is said to be compatible with a schema
Example 4. The KQ q1 = fa : A; c : Cg is not compatible with schema S1 = fr1(A; B); r2(C; D)g, since no set of tuples from S containing all the keywords in q1 can ever be connected, independently of the access patterns for S1. Conversely, q1 is compatible with S2 = fr1(A; B); r3(B; C)g, as witnessed by a possible answer fr1(a; b); r3(b; c)g and patterns such that S2 = fr1(Ai; B); r3(B; C)g.
Similarly, KQ q2 = fa : A; a0 : Ag is compatible with a schema S3 = fr1(A; B)g, as witnessed by a possible answer fr1(a; b); r1(a0; b)g and patterns such that S3 = fr1(Ai; B)g. However, q2 is not compatible with a schema S4 = fr4(A)g, since a unary relation, alone, can never connect two keywords. Checking compatibility of a KQ with a schema essentially amounts to checking reachability on a graph. The main idea is that in order for an answer to ever be possible, we must nd an instance that exhibits a witness (i.e., a set of tuples) satisfying all the conditions of De nition 7. 3.2
A stricter requirement than compatibility is given by the notion of answerability. De nition 10 (Answerability). A KQ q is answerable against a schema S if there is an instance I over S such that there is an answer to q against I. Example 5. Consider KQ q = fa : A; c : Cg and schema S1 = fr(Ai; B); s(B; C; Di)g. Although q is compatible with S1, it is not answerable against S1 , since no tuple from S1 can be extracted under (no values for domain D are available). Conversely, q is answerable against S2 = fr(Ai; B); s(Bi; C; D)g, since an answer like fr(a; b); s(b; c; d)g could be extracted by rst accessing r with binding hai, thus extracting value b, and then s with binding hbi. In order to check answerability, we need to check that all the required relations can be accessed according to the access patterns. To this end, we rst refer to a schema enriched with unary relations representing the keywords in the KQ. 1 De nition 11 (Expanded schema). Let q be a KQ over a schema S . The expanded schema Sq of S wrt. q is de ned as Sq = S [frc(C)jc 2 qg, where rc is a new unary relation, not occurring in S , whose only attribute C is an output attribute with abstract domain dom(C) = dom(c).
Then, we use the notion of dependency graph (d-graph) to denote output-input dependencies between relation arguments, indicating that a relation under access patterns needs values from other relations. 1 If other values are known besides the keywords, this knowledge may be represented by means of appropriate unary relations with output mode in the schema.
A a
Ai B r
B C Di s
Ci D s
C c
C c
Ai B r
A a
A a
B D Ei u
Ai B r
is a directed graph hN ; E i de ned as follows. For each attribute A of each relation in the expanded schema Sq , there is a node in N labeled with A's access mode and abstract domain. There is an arc uyv in E whenever: (i) u and v have the same abstract domain; (ii) u is an output node; and (iii) v is an input node. Some relations are made invisible by the access patterns and can be discarded.
visible if there is a sequence of arcs u1yv1; : : : ; unyvn in E such that (i) u1's relation has no input attributes, and (ii) vi's and ui+1's relation are the same, for 1 i n 1. A relation is visible if all of its input nodes are. Example 5 (cont.). Consider the KQ and the schemas from Example 5. The dgraphs GqS1 and GqS2 are shown in Figures 2a and Figure 2b, respectively. Bi C D s
C c (a) D-graph GqS1 from Example 5; s is not visible. (b) D-graph GqS2 from Example 5; all relations are visible. (c) D-graph GqS from Example 6; u is not visible.
Answerability of a KQ q is checked by means of compatibility with a schema in which all non-visible relations have been eliminated.
Example 6. Consider a KQ q = fa : A; c : Cg and a schema S = fr(Ai; B); s(Ci; D); u(B; D; Ei)g. Relation u is not visible in GqS (Figure 2c). Then, q is not answerable in S , since q is not compatible with schema fr(A; B); s(C; D)g (i.e., S without relation u).
We have de ned the problem of keyword search in the Deep Web. We are currently working on minimizing the number of accesses to the data sources.
We believe that several interesting issues can be studied in the framework de ned in this paper. We plan, e.g., to leverage known values (besides the keywords) and ontologies to speed up the search for an optimal answer as well as to consider the case in which nodes and arcs of the join graph are weighted to model source availability and proximity, respectively.