Partial Answers in Information Integration Systems

摘要

In the context of local-as-view information integration system a source collection defines a set of possible databases, therefore, querying a source collection, at least conceptually, means applying the query to each possible database, obtaining a set of possible answers. With this in mind we introduced the notion of the exact answer, which can be represented as a relation containing null values, and we gave two methods for computing the exact answer. The first method involves explicitly computing T(S) ― a syntactic representation of the set of global databases implicitly defined by the sources. The φ evaluation is then used to compute the exact answer. The other method reformulates a query in terms of the source relations, and, thus, avoids inverting the entire source collection. In order to achieve this we generalized classical notion of query containment to p-containment and used this notion to reformulate the query as a union of p-contained conjunctive queries. Then we defined the φ-evaluation which uses p-contained rewritings to compute the exact answer on the source collection. We have developed an experimental system, which enables us to evaluate the performance of the proposed methods to compute the exact answer in practice. As the result of our experiments we have established that computation of the exact answer can be done efficiently for all practical situations including the large-scale systems. Moreover, by comparing our results to the results presented in [9], we have confirmed that shifting from the computation of the certain answer to the computation of the exact answer does not change the average running time of query rewriting algorithms.