The Deep Web is constituted by data accessible through Web pages, but not readily indexable by search engines, as they are returned in dynamic pages. In this paper we propose a framework for accessing Deep Web sources, represented as relational tables with so-called access limitations, with keyword-based queries. We formalize the notion of optimal answer and investigate methods for query processing. To our knowledge, this problem has never been studied in a systematic way.
Access limitations. An access pattern for a schema R(A1; : : : ; Ak) is a mapping sending each attribute Ai into an access mode, which can be either input or output; Ai is correspondingly called an input (resp., output ) attribute for R wrt.
. For ease of notation, we shall mark input attributes with an `i' superscript to distinguish them from the output ones. Let A01; : : : ; A0l be all the input attributes for R wrt. ; any tuple hc1; : : : ; cli such that ci 2 dom(A0i) for 1 i l is called a binding for R wrt. . An access consists of an access pattern for a schema R and a binding for R wrt. ; the output of such an access on an instance r is the set T = A1=c1;:::;Al=cl (r): Intuitively, we can only access a relation if we can provide a value for every input attribute. Given an instance r for a database schema R, a set of access patterns for the relations in R, and a set of values C D, an access path (for R, and C) is a sequence of accesses 1; : : : ; n on r such that each value in the binding of i, 1 i n, either occurs in the output of an access j with j < i or is a value in C. A tuple t in r is said to be reachable if there exists an access path P such that t is in the output of some (a) Access paths (b) Join graph (c) Answers access in P ; the reachable portion reach(r; tuples in r given the values in C. ; C) of r is the set of all reachable Keyword queries. A keyword query is a set of values in D called keywords. Example 1 Consider a query q = fk1; k2g, a schema (with access patterns R = fR1(Ai1; A2); R2(Ai2; A1); R3(Ai1; A2; A3)g, and an instance r such that )
Ai1 A2 r1 = k1 c1 t11 c2 c3 t12
Ai2 A1 c1 c2 t21 c4 c2 t22 c1 c6 t23 r2 = r3 =
Ai1 A2 A3 c2 c1 k2 t31 c5 c4 k2 t32 c6 c7 k2 t33 Given a set T of tuples, the join graph of T is a node-labelled undirected graph T = hN; Ei constructed as follows: (i) the nodes N are labelled with tuples of T , and (ii) there is an arc between two nodes n1 and n2 if the tuples labelling n1 and n2 have at least one value in common.
Example 1 (cont.) The join graph of reach(r; ; q) is shown in Figure 1(b).
De nition 1 (Answer). An answer to a keyword query q against a database
instance r over a schema R with access patterns is a set of tuples A in
reach(r; ; q) such that: (1) each c 2 q occurs in at least one tuple t in A;
(2) the join graph of A is connected; (3) for every subset A0 A such that A0
enjoys Condition 1 above, the join graph of A0 is not connected.
It is straightforward to see that there could be several answers to a keyword
query; below we give a widely accepted criterium for ranking such answers [
Keyword-based answering in the Deep Web We now present a vanilla algorithm to discuss the computational complexity of answering a keyword query q in the deep Web modeled as an instance r of a schema R with access patterns . Example 1 shows that, in the worst case, we need to extract the whole reachable portion to obtain the tuples involved in an optimal answer. In fact, s = reach(r; ; q) is actually a connected join graph, since every tuple in it is in some output of some access path starting from the values in the query (see for example Figure 1.a), but further paths may exist between tuples in s (see Figure 1.b). Therefore, query answering requires in general two main steps, described in Algorithm 1: (i) extract the reachable portion s of r; (ii) if possible, remove tuples from s so that the obtained set satis es the conditions of De nition 1, while minimizing its size. Algorithm 1: Computing an optimal answer (Answer(q; ; r)) Input: Keyword query q, access patterns , instance r over R Output: Answer A 1. A := reachableP ortion(r; ; q); // see Algorithm 2 2. if A does not contain all values in q then return nil; 3. else prune(A; q); // see Algorithm 3 4. return A;
A simple way of extracting the reachable portion, inspired by the procedure
described in [
Algorithm 2: Reachable portion (reachableP ortion(r; ; q)) Input: Instance r over R, access patterns , initial values q Flag: boolean ! // if ! = true the answer is guaranteed to be optimal Output: Reachable portion RP 1. RP := ;; C := ;; 2. while an access can be made with a new binding b for some R 2 R wrt. 3. O := output of access to r over R with binding b; 4. RP := RP [ O; // cumulating all the obtained tuples into RP 5. C := C [ SA2R;t2Oft(A)g; // cumulating all the obtained values into C 6. if C q ^ :! then break; 7. return RP ; using values in C [ q
Basically, determining an optimal answer from the reachable portion
corresponds to nding a Steiner tree of its join graph [
The extraction of the reachable portion of an instance r with access
limitations can be implemented by a Datalog program over r [
Discussion and future work In this paper, we have de ned the problem of keyword search in the Deep Web and provided some preliminary insights on query answering in this context. As future work on the problem in question, we plan to: { devise optimization strategies for query answering; in particular, identify conditions under which an optimal answer can be derived without extracting the whole reachable instance; { leverage known values (besides the keywords), modeled as relations with only one (output) attribute, to speed up the search for an optimal answer; { study the problem in a scenario in which the domains of the keywords are known in advance: in this case schema-based techniques can be used; { consider the case in which nodes and arcs of the join graph are weighted to model source availability and proximity, respectively.
Acknowledgments. Andrea Cal acknowledges support by the EPSRC grant \Logic-based Integration and Querying of Unindexed Data" (EP/E010865/1). References