Recursive query plans for data integration

Generating query-answering plans for data integration systems requires to t ranslate a user query, formulated in terms of a mediated schema, to a query that uses relations that are actually stored in data sources. Previous sol utions to the translation problem produced sees of conjunctive plans, and w ere therefore limited in their ability to handle recursive queries and to e xploit data sources with binding-pattern limitations and functional depende ncies that are known to hold in the mediated schema. As a result, these pla ns were incomplete w.r.t. sources encountered in practice (i.e., produced o nly a subset of the possible answers). We describe the novel class of recur sive query answering plans, which enables us to settle three open problems. First, we describe an algorithm for finding a query plan that produces the maximal set of answers from the sources for arbitrary recursive queries. S econd, we extend this algorithm to use the presence of functional and full dependencies in the mediated schema. Third, we describe an algorithm for fi nding the maximal query plan in the presence of binding-pattern restriction s in the sources. In all three cases, recursive plans are necessary in orde r to obtain a maximal query plan. (C) 2000 Published by Elsevier Science In c. All rights reserved.