Googling the Deep Web Andrea Calı̀1 , Davide Martinenghi2 , and Riccardo Torlone3 1 Birkbeck, University of London, UK, email: andrea@dcs.bbk.ac.uk 2 Politecnico di Milano, Italy, email: davide.martinenghi@polimi.it 3 Università Roma Tre, Italy, email: torlone@dia.uniroma3.it Abstract. The Deep Web is constituted by data that are accessible through Web pages, but not indexable by search engines as they are re- turned in dynamic pages. In this paper we propose a conceptual frame- work 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. Keywords: Keyword Query, Access Pattern, Deep Web. 1 Introduction It is well known that the data available on the Web through forms and in general in dynamic pages constitutes a corpus of data that is way larger than the Web data that are indexed by search engines. The former are commonly referred to as Deep Web, that is, data “hidden” in local databases whose content can only be accessed through queries. This happens for instance when we search for a flight on the Web site of an airline company – the data make sense only for a short time, after which they become obsolete due to the frequent changes of prices and availability. This immediately poses an interesting challenge, i.e., how to automatically retrieve relevant information from the Deep Web – a problem that has been investigated in recent years (see, e.g., [2, 4, 15] for discussion). Usually, a data source in the Deep Web is modeled at the logical level by a relational table in which some columns, called input attributes, represent fields of a form that need to be filled in so as to retrieve data from the source, while all the others, called output attributes, represent values that are returned to the user. Consider for instance the following relations in which the i superscript denotes the input attributes. Empi Proj Depti Emp Proji Emp Role John P1 t21 r1 = IT John t11 r2 = r3 = P1 John DBA t31 Ann P2 t22 AI Mike t12 P1 Ann Analyst t32 Mike P2 t23 Relation r1 represents a form that, given a department, returns all the employ- ees 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. Different approaches have been proposed in the literature for querying databases with access limitations: conjunctive queries [3], natural language [13], and SQL-like statements [11]. In this paper, we address the novel problem of accessing the Deep Web by just providing a set of keywords, in the same way in which we usually search for information on the Web with a search engine. 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 first 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 {t11 , t21 , t31 } 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 {t11 , t31 } 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 first 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 finding 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 first 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 investi- gated in the last years, with different approaches and under different perspectives including: data crawling [16], integration of data sources [9], query plan optimiza- tion [3], and generic structured query models [11]. However, none of them has tackled the problem that we have addressed in this paper. The idea of querying structured data using keywords emerged more than a decade ago [1] as a way to provide high-level access to data and free the user from the knowledge of query languages and data organization. Since then, a lot of work has been done in this field (see, e.g., [18] for a survey) but never in the context of the Deep Web. This problem has been investigated in the context of various data models: relational [12], semi-structured [14], XML [8], and RDF [17]. Within the relational model, the common assumption is that an answer to a keyword query is a graph of minimal size in which the nodes represent tuples, the edges represent foreign key references between them, and the keywords occur in some node of the graph [10]. Our definition of query answer follows this line but it is more general, since it is only based on the presence of common values between tuples, while not forcing the presence of foreign keys. The various approaches to keyword query answering over relational databases are commonly classified into two categories: schema-based and schema-free. Schema-based approaches [1, 10] make use, in a preliminary phase, of the database schema to build SQL queries that are able to return the answer. Conversely, schema-free approaches [7, 12] rely on exploration techniques over a graph-based representation of the whole database. Since the search for an op- timal answer consists in finding a minimal Steiner tree on the graph, which is known to be an NP-Complete problem [6], the various proposals rely on heuris- tics aimed at generating approximations of Steiner trees. Our approach makes use of the schema of the data sources but cannot be classified in any of the approaches above since, given the access limitations, it rather relies on building a minimal query plan of accesses to the data sources. 2 Preliminaries and problem definition We model data sources as relations of a relational database and we assume that, albeit autonomous, they have “compatible” attributes. For this, we fix a set of abstract domains D = {D1 , . . . , Dm }, 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 objectS is uniquely represented by a value. The set of all values is denoted by n D = 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 {A1 , . . . , Ak }, each associated with an abstract domain dom(Ai ) ∈ D, 1 ≤ i ≤ k. A database schema S is a set of schemas {r1 , . . . , rn }. As usual, given a schema r, a tuple t over r is a function that associates a value c ∈ dom(A) with each attribute A ∈ 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 = {r1 , . . . , rn } is a set of relation instances {rI1 , . . . , rIn }, where rIi denotes the relation instance of ri in I. For the sake of simplicity, in the following we assign the same name to at- tributes of different schemas that are defined over the same abstract domain. Definition 1 (Access pattern). An access pattern Π for a schema r(A1 , . . . , Ak ) is a mapping Π : {A1 , . . . , Ak } → M , where M = {i, o} is called access mode, and i and o denote input and output, respectively; Ai is corre- spondingly 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. Definition 2 (Binding). Let A01 , . . . , A0` be all the input attributes for r wrt Π; any tuple b = hc1 , . . . , c` i such that ci ∈ dom(A0i ) for 1 ≤ i ≤ ` is called a binding for r wrt Π. Definition 3 (Access). An access is a pair hΠ, bi, where Π is an access pattern 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 ∈ 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. Definition 4 (Access path). Given an instance I for a database schema S, a set of access patterns Π for the relations in S, and a set of values C ⊆ D, an b b b access path on I (for S, Π and C) is a sequence −→1r1I T1 −→2r2I · · · −→nrnI Tn , where, for 1 ≤ i ≤ n, (i) bi is a binding for a relation ri ∈ S wrt a pattern Πi ∈ Π for ri , (ii) Ti is the output of access hΠi , bi i on I, and (iii) each value in bi either occurs in Tj with j < i or is a value in C. Definition 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 I of a schema S Π = {r1 (Ai , B), r2 (B i , A), r3 (Ai , B, C)}. Bi A Ai B C Ai B b a t a b c t r1 = a1 b1 t11 r2 = 1 2 21 r3 = 2 1 1 31 b2 a2 t22 a3 b2 c2 t32 a2 b3 t12 b1 a4 t23 a4 b4 c1 t33 Then, for instance, {t11 } is the output of the access with binding ha1 i wrt ha1 i hb1 i r1 (Ai , B), and −→r1I {t11 } −→r2I {t21 , t23 }, is an access path for S, Π and C = {a1 }, since, given C, we can extract t11 from r1 and, given {b1 } from t11 , we can extract t21 and t23 from r2 . The reachable portion of I, given C, is reach(I, Π, C) = {t11 , t12 , t21 , t23 , t31 , t33 }, while {t22 , t32 } ∩ reach(I, Π, C) = ∅. Figure 1a shows the reachable portion I 0 of I given C along with the access paths used to extract it, with dotted lines enclosing outputs of accesses. The definition of answer to a keyword query in our setting requires the prelimi- nary notion of join graph. Definition 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. t31 r3 t12 r1 t33 r3 t31 t33 A1 A2 t21 t23 r2 t31 t12 t33 t21 t23 t23 t11 t11 t11 r1 t11 (a) Reachable portion I 0 , given {a1 }. (b) Join graph of I 0 . (c) Two answers to KQ q. Fig. 1: Illustration of Examples 1, 2, and 3. Example 2. Consider instance I of Example 1 and the reachable portion I 0 of I given {a1 }, shown in Figure 1a. The join graph of I 0 is shown in Figure 1b. A keyword query (KQ) is a non-empty set of values in D called keywords. Definition 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 ∈ q occurs in at least one tuple t in A; (ii) the join graph of A is connected; (iii) no proper subset A0 ⊂ A satisfies 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 [18]. Definition 8. Let A1 , A2 be two answers to a KQ q on an instance I. We say that A1 is better than A2 if |A1 | ≤ |A2 |. The optimal answers are those of minimum size. Example 3. Consider a KQ q = {a1 , c1 } over the instance I of Example 1. Fig- ure 1a shows two possible answers: A1 = {t11 , t31 } and A2 = {t11 , t23 , t33 }. A1 is better than A2 and is the optimal answer to q. 3 Detecting non-answerable queries 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 Compatible queries In order to focus on meaningful queries, we semantically characterize queries for which an answer might be found. Definition 9 (Compatibility). A KQ q is said to be compatible with a schema S if there exist a set of access patterns Π and an instance I over S Π such that there is an answer to q against I. Example 4. The KQ q1 = {a : A, c : C} is not compatible with schema S1 = {r1 (A, B), r2 (C, D)}, 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 = {r1 (A, B), r3 (B, C)}, as witnessed by a possible answer {r1 (a, b), r3 (b, c)} and patterns Π such that S2Π = {r1 (Ai , B), r3 (B, C)}. Similarly, KQ q2 = {a : A, a0 : A} is compatible with a schema S3 = {r1 (A, B)}, as witnessed by a possible answer {r1 (a, b), r1 (a0 , b)} and patterns Π such that S3Π = {r1 (Ai , B)}. However, q2 is not compatible with a schema S4 = {r4 (A)}, 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 find an instance that exhibits a witness (i.e., a set of tuples) satisfying all the conditions of Definition 7. 3.2 Answerable queries A stricter requirement than compatibility is given by the notion of answerability. Definition 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 = {a : A, c : C} and schema S1Π = {r(Ai , B), s(B, C, Di )}. 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Π = {r(Ai , B), s(B i , C, D)}, since an answer like {r(a, b), s(b, c, d)} could be extracted by first 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 first refer to a schema enriched with unary relations representing the keywords in the KQ. 1 Definition 11 (Expanded schema). Let q be a KQ over a schema S Π . The expanded schema SqΠ of S Π wrt. q is defined as SqΠ = S Π ∪{rc (C)|c ∈ q}, 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. Π Definition 12 (d-graph). Let q be a KQ over a schema S Π . The d-graph GSq is a directed graph hN , Ei defined 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 uy v 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. Definition 13 (Visibility). An input node vn ∈ N in a d-graph hN , Ei is visible if there is a sequence of arcs u1 y v1 , . . . , un y vn 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 d- SΠ SΠ graphs Gq 1 and Gq 2 are shown in Figures 2a and Figure 2b, respectively. B Bi Ai Ai A C C A C C B B Di D a c a c r r s s SΠ SΠ (a) D-graph Gq 1 from Example 5; s is (b) D-graph Gq 2 from Example 5; all not visible. relations are visible. B Ci Ai C A D D B Ei c a s r u Π (c) D-graph GS q from Example 6; u is not visible. Fig. 2: D-graphs from the Examples. 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 = {a : A, c : C} and a schema S Π = Π {r(Ai , B), s(C i , D), u(B, D, E i )}. Relation u is not visible in GSq (Figure 2c). Then, q is not answerable in S Π , since q is not compatible with schema {r(A, B), s(C, D)} (i.e., S without relation u). 4 Conclusions and future work We have defined the problem of keyword search in the Deep Web. We are cur- rently working on minimizing the number of accesses to the data sources. We believe that several interesting issues can be studied in the framework defined in this paper. We plan, e.g., to leverage known values (besides the key- words) 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. References 1. Sanjay Agrawal, Surajit Chaudhuri, and Gautam Das. Dbxplorer: A system for keyword-based search over relational databases. In ICDE, pages 5–16, 2002. 2. Meghyn Bienvenu et al. Dealing with the deep web and all its quirks. In Proc. of VLDS, pages 21–24, 2012. 3. Andrea Calı̀ and Davide Martinenghi. Querying data under access limitations. In ICDE, pages 50–59, 2008. 4. Andrea Calı̀ and Davide Martinenghi. Querying the deep web. In EDBT, pages 724–727, 2010. 5. Andrea Calı̀, Davide Martinenghi, and Riccardo Torlone. Keyword search in the deep web. In Proc. of the 9th AMW, 2015. 6. M. R. Garey, R. L. Graham, and D. S. Johnson. The complexity of computing Steiner minimal trees. SIAM J. on Applied Mathematics, 32(4):835–859, 1977. 7. Konstantin Golenberg, Benny Kimelfeld, and Yehoshua Sagiv. Keyword proximity search in complex data graphs. In SIGMOD, pages 927–940, 2008. 8. Lin Guo, Feng Shao, Chavdar Botev, and Jayavel Shanmugasundaram. Xrank: ranked keyword search over xml documents. In SIGMOD, pages 16–27, 2003. 9. Bin He, Zhen Zhang, and Kevin Chen-Chuan Chang. Metaquerier: querying struc- tured web sources on-the-fly. In Proc. of SIGMOD, pages 927–929, 2005. 10. Vagelis Hristidis and Yannis Papakonstantinou. Discover: Keyword search in rela- tional databases. In VLDB, pages 670–681, 2002. 11. Hasan M. Jamil and Hosagrahar V. Jagadish. A structured query model for the deep relational web. In CIKM, pages 1679–1682, 2015. 12. Benny Kimelfeld and Yehoshua Sagiv. Finding and approximating top-k answers in keyword proximity search. In PODS, pages 173–182, 2006. 13. Jens Lehmann et al. Deqa: Deep web extraction for question answering. In ISWC’12, pages 131–147. Springer-Verlag, 2012. 14. Guoliang Li et al. EASE: an effective 3-in-1 keyword search method for unstruc- tured, semi-structured and structured data. In SIGMOD, pages 903–914, 2008. 15. Jayant Madhavan, Loredana Afanasiev, Lyublena Antova, and Alon Y. Halevy. Harnessing the deep web: Present and future. In CIDR, 2009. 16. Sriram Raghavan and Hector Garcia-Molina. Crawling the hidden web. In VLDB, pages 129–138, 2001. 17. Thanh Tran et al. Top-k exploration of query candidates for efficient keyword search on graph-shaped (rdf) data. In ICDE, pages 405–416, 2009. 18. Jeffrey Xu Yu, Lu Qin, and Lijun Chang. Keyword search in relational databases: A survey. IEEE Data Eng. Bull., 33(1):67–78, 2010.