Recursive query plans for data integration

✍ Scribed by Oliver M. Duschka; Michael R. Genesereth; Alon Y. Levy

• Publisher: Elsevier Science
• Year: 2000
• Tongue: English
• Weight: 204 KB
• Volume: 43
• Category: Article
• ISSN: 0743-1066
• DOI: 10.1016/s0743-1066(99)00025-4

✦ Synopsis

Generating query-answering plans for data integration systems requires to translate a user query, formulated in terms of a mediated schema, to a query that uses relations that are actually stored in data sources. Previous solutions to the translation problem produced sets of conjunctive plans, and were therefore limited in their ability to handle recursive queries and to exploit data sources with binding-pattern limitations and functional dependencies that are known to hold in the mediated schema. As a result, these plans were incomplete w.r.t. sources encountered in practice (i.e., produced only a subset of the possible answers). We describe the novel class of recursive query answering plans, which enables us to settle three open problems. First, we describe an algorithm for ®nding a query plan that produces the maximal set of answers from the sources for arbitrary recursive queries. Second, we extend this algorithm to use the presence of functional and full dependencies in the mediated schema. Third, we describe an algorithm for ®nding the maximal query plan in the presence of binding-pattern restrictions in the sources. In all three cases, recursive plans are necessary in order to obtain a maximal query plan.