Foundations of Query Answering in Relational Data Exchange
Logos Verlag Berlin GmbH, 2010 - 223 pages
Relational data exchange is the problem of translating relational data according to a given specification. It is one of the many tasks that arise in information integration. A fundamental issue is how to answer queries that are posed against the result of the data exchange so that the answers are semantically consistent with the source data. For monotonic queries, the certain answers semantics by Fagin, Kolaitis, Miller, and Popa (2003) yields good answers. For many non-monotonic queries, however, this semantics was shown to yield counter-intuitive answers. This dissertation deals with the problem of computing the certain answers to monotonic queries on the one hand. On the other hand, it presents and compares semantics for answering non-monotonic queries, and investigates how hard it is to evaluate non-monotonic queries under these semantics.
What people are saying - Write a review
We haven't found any reviews in the usual places.
Abiteboul acyclic schema mapping Afrati algorithm Anfragen answers to q atom block atomic FO formula atomic formulas binary relation C-chase C-minimal instances CanSol(M,S cert certGCWA closed world assumption co-NP conjunctive queries consists of st-tgds Const const(T constants core Core(M,S CWA-presolution CWA-solution deductive database defined by st-tgds defined by tgds DM,S dom(T equivalence relation Fagin finite set FO query Furthermore GCWA GCWA∗-answers semantics GCWA∗-solutions ground solution homomorphism h implicit information implies instances in poss(T intuitively Is-i isomorphic Kolaitis Lemma Libkin logically equivalent M’s target schema mapping M defined minC(T minimal solutions monotonic queries naive table nulls packed st-tgds polynomial polynomial time algorithm preserved under homomorphisms proof Proposition query answering semantics query q relational data exchange result schema mappings defined Section semigroups source instance st-tgds and egds target instance tgds and egds Theorem thesis tuple unions of conjunctive universal query universal solution valc(T