OPUS 4 Latest Documents RSS Feed
Latest documents
http://publikationen.stub.unifrankfurt.de/index/index/
Thu, 12 Aug 2010 09:54:44 +0100
Thu, 12 Aug 2010 09:54:44 +0100

Foundations of query answering in relational data exchange
http://publikationen.stub.unifrankfurt.de/frontdoor/index/index/docId/20435
Relational data exchange deals with translating relational data according to a given specification. This problem is one of the many tasks that arise in data integration, for example, in data restructuring, in ETL (ExtractTransformLoad) processes used for updating data warehouses, or in data exchange between different, possibly independently created, applications. Systems for relational data exchange exist for several decades now. Motivated by their experiences with one of those systems, Fagin, Kolaitis, Miller, and Popa (2003) studied fundamental and algorithmic issues arising in relational data exchange. One of these issues is how to answer queries that are posed against the target schema (i.e., against the result of the data exchange) so that the answers are consistent with the source data. For monotonic queries, the certain answers semantics proposed by Fagin, Kolaitis, Miller, and Popa (2003) is appropriate. For many nonmonotonic queries, however, the certain answers semantics was shown to yield counterintuitive results. This thesis deals with computing the certain answers for monotonic queries on the one hand, and on the other hand, it deals with the issue of which semantics are appropriate for answering nonmonotonic queries, and how hard it is to evaluate nonmonotonic queries under these semantics. As shown by Fagin, Kolaitis, Miller, and Popa (2003), computing the certain answers for unions of conjunctive queries  a subclass of the monotonic queries  basically reduces to computing universal solutions, provided the data transformation is specified by a set of tgds (tuplegenerating dependencies) and egds (equalitygenerating dependencies). If M is such a specification and S is a source database, then T is called a solution for S under M if T is a possible result of translating S according to M. Intuitively, universal solutions are most general solutions. Since the abovementioned work by Fagin, Kolaitis, Miller, and Popa it was unknown whether it is decidable if a source database has a universal solution under a given data exchange specification. In this thesis, we show that this problem is undecidable. More precisely, we construct a specification M that consists of tgds only so that it is undecidable whether a given source database has a universal solution under M. From the proof it also follows that it is undecidable whether the chase procedure  by which universal models can be obtained  terminates on a given source database and the set of tgds in M. The above results in particular strengthen results of Deutsch, Nash, and Remmel (2008). Concerning the issue of which semantics are appropriate for answering nonmonotonic queries, we study several semantics for answering such queries. All of these semantics are based on the closed world assumption (CWA). First, the CWAsemantics of Libkin (2006) are extended so that they can be applied to specifications consisting of tgds and egds. The key is to extend the concept of CWAsolution, on which the CWAsemantics are based. CWAsolutions are characterized as universal solutions that are derivable from the source database using a suitably controlled version of the chase procedure. In particular, if CWAsolutions exist, then there is a minimal CWAsolution that is unique up to isomorphism: the core of the universal solutions introduced by Fagin, Kolaitis, and Popa (2003). We show that evaluation of a query under some of the CWAsemantics reduces to computing the certain answers to the query on the minimal CWAsolution. The CWAsemantics resolve some the known problems with answering nonmonotonic queries. There are, however, two natural properties that are not possessed by the CWAsemantics. On the one hand, queries may be answered differently with respect to data exchange specifications that are logically equivalent. On the other hand, there are queries whose answer under the CWAsemantics intuitively contradicts the information derivable from the source database and the data exchange specification. To find an alternative semantics, we first test several CWAbased semantics from the area of deductive databases for their suitability regarding nonmonotonic query answering in relational data exchange. More precisely, we focus on the CWAsemantics by Reiter (1978), the GCWAsemantics (Minker 1982), the EGCWAsemantics (Yahya, Henschen 1985) and the PWSsemantics (Chan 1993). It turns out that these semantics are either too weak or too strong, or do not possess the desired properties. Finally, based on the GCWAsemantics we develop the GCWA*semantics which intuitively possesses the desired properties. For monotonic queries, some of the CWAsemantics as well as the GCWA*semantics coincide with the certain answers semantics, that is, results obtained for the certain answers semantics carry over to those semantics. When studying the complexity of evaluating nonmonotonic queries under the abovementioned semantics, we focus on the data complexity, that is, the complexity when the data exchange specification and the query are fixed. We show that in many cases, evaluating nonmonotonic queries is hard: coNP or NPcomplete, or even undecidable. For example, evaluating conjunctive queries with at least one negative literal under simple specifications may be coNPhard. Notice, however, that this result only says that there is such a query and such a specification for which the problem is hard, but not that the problem is hard for all such queries and specifications. On the other hand, we identify a broad class of queries  the class of universal queries  which can be evaluated in polynomial time under the GCWA*semantics, provided the data exchange specification is suitably restricted. More precisely, we show that universal queries can be evaluated on the core of the universal solutions, independent of the source database and the specification.
AndrĂ© Hernich
doctoralthesis
http://publikationen.stub.unifrankfurt.de/frontdoor/index/index/docId/20435
Wed, 08 Dec 2010 09:54:44 +0100