Advertisement
Published in:
2010 | OriginalPaper | Chapter
Managing Lineage and Uncertainty under a Data Exchange Setting
Authors : Foto N. Afrati, Angelos Vasilakopoulos
Published in: Scalable Uncertainty Management
Publisher: Springer Berlin Heidelberg
Activate our intelligent search to find suitable subject content or patents.
Select sections of text to find matching patents with Artificial Intelligence. powered by
Select sections of text to find additional relevant content using AI-assisted search. powered by
We present a data exchange framework that is capable of exchanging uncertain data with lineage and give meaningful certain answers on queries posed on the target schema. The data are stored in a
database with uncertainty and lineage (ULDB)
which represents a set of possible instances that are
databases with lineage (LDBs)
. Hence we need first to revisit all the notions related to data exchange for the case of LDBs. Producing all possible instances of a ULDB, like the semantics of certain answers would indicate, is exponential. We present a more efficient approach: a u-chase algorithm that extends the known chase procedure of traditional data exchange and show that it can be used to correctly compute certain answers for conjunctive queries in PTIME for a set of weakly acyclic tuple generating dependencies. We further show that if we allow equality generating dependencies in the set of constraints then computing certain answers for conjunctive queries becomes NP-hard.