Data exchange: semantics and query answering

DOI10.1016/j.tcs.2004.10.033zbMath1080.68019WikidataQ60431740 ScholiaQ60431740MaRDI QIDQ555772

Phokion G. Kolaitis, Ronald Fagin, Renée J. Miller, Lucian Popa

Publication date: 10 June 2005

Published in: Theoretical Computer Science (Search for Journal in Brave)

Full work available at URL: https://doi.org/10.1016/j.tcs.2004.10.033

zbMATH Keywords

Computational complexity; Certain answers; Chase; Data exchange; Data integration; Dependencies; First-order inexpressibility; Query answering; Universal solution

Mathematics Subject Classification ID

68P15: Database theory

03B70: Logic in computer science

68Q65: Abstract data types; algebraic specification

68P05: Data structures

Related Items

Information-Optimal Reflections of View Updates on Relational Database Schemata, Semantic Bijectivity and the Uniqueness of Constant-Complement Updates in the Relational Context, Magic Sets and their application to data integration, First-order query rewriting for inconsistent databases, Game-based notions of locality over finite models, Data Privacy for $\mathcal{ALC}$ Knowledge Bases

Cites Work

• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• The complexity of querying indefinite data about linearly ordered domains
• The core of a graph
• Inclusion dependencies and their interaction with functional dependencies
• Why Horn formulas matter in computer science: initial structures and generic examples
• On monadic NP vs monadic co-NP
• On the foundations of the universal relation model
• A Proof Procedure for Data Dependencies
• Horn clauses and database dependencies
• CONVERT
• Recursive query plans for data integration
• The complexity of satisfiability problems
• Answering queries using views: A survey