Data exchange: semantics and query answering

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

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

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

Database theory (68P15) Logic in computer science (03B70) Abstract data types; algebraic specification (68Q65) Data structures (68P05)

Related Items

On the data complexity of consistent query answering, On the data complexity of consistent query answering over graph databases, Inconsistency-tolerant query answering for existential rules, MV-Datalog+-: Effective Rule-based Reasoning with Uncertain Observations, Querying incomplete information in RDF with SPARQL, UPDATE TRANSLATION IN INSTANCE MAPPED HETEROGENEOUS PEER DATABASES, Towards knowledge exchange: state-of-the-art and open problems, On the Interaction of Existential Rules and Equality Constraints in Ontology Querying, Knowledge base exchange: the case of OWL 2 QL, Limits of schema mappings, Reasoning about integrity constraints for tree-structured data, Querying Regular Graph Patterns, XML Schema Mappings, Bringing existential variables in answer set programming and bringing non-monotony in existential rules: two sides of the same coin, Query optimization in information integration, Relaxed notions of schema mapping equivalence revisited, Towards more expressive ontology languages: the query answering problem, Algebraic data integration, Craig interpolation with clausal first-order tableaux, Preserving Constraints with the Stable Chase, Bounds in ontology-based data access via circuit complexity, Magic Sets and their application to data integration, First-order query rewriting for inconsistent databases, Solutions and query rewriting in data exchange, The language of plain SO-tgds: composition, inversion and structural properties, Solutions in XML data exchange, On simplification of schema mappings, Semantic query optimization in the presence of types, Terminating Evaluation of Logic Programs with Finite Three-Valued Models, Temporal Minimal-World Query Answering over Sparse ABoxes, Finite model reasoning over existential rules, Answer Counting under Guarded TGDs, Checking termination of bottom-up evaluation of logic programs with function symbols, The notion of abstraction in ontology-based data management, On the k-Boundedness for Existential Rules, Restricted Chase Termination: A Hierarchical Approach and Experimentation, Polynomial combined first-order rewritings for linear and guarded existential rules, Feferman-vaught decompositions for prefix classes of first order logic, A Logic Framework for P2P Deductive Databases, Uniform Restricted Chase Termination, A Tutorial on Query Answering and Reasoning over Probabilistic Knowledge Bases, Early detection of temporal constraint violations, Information-based distance measures and the canonical reflection of view updates, Inseparability and Conservative Extensions of Description Logic Ontologies: A Survey, Characterisations of multivalued dependency implication over undetermined universes, Query languages for data exchange: beyond unions of conjunctive queries, Unnamed Item, Logical foundations of information disclosure in ontology-based data integration, On rules with existential variables: walking the decidability line, Reasoning on anonymity in Datalog, Reasoning about functional and full hierarchical dependencies over partial relations, Disjunctive logic programs with existential quantification in rule heads, Logic programming with function symbols: Checking termination of bottom-up evaluation through program adornments, Combining decidability paradigms for existential rules, Fuzzy data exchange, SOME MODEL THEORY OF GUARDED NEGATION, Datalog and Its Extensions for Semantic Web Databases, Disjunctive datalog with existential quantifiers: Semantics, decidability, and complexity issues, Query answering under probabilistic uncertainty in Datalog$+/-$ ontologies, Game-based notions of locality over finite models, Data exchange and schema mappings in open and closed worlds, Querying incomplete data over extended ER schemata, Tractable XML data exchange via relations, Logic, Languages, and Rules for Web Data Extraction and Reasoning over Data, A sound and complete model-generation procedure for consistent and confidentiality-preserving databases, Towards practical feasibility of core computation in data exchange, Unnamed Item, Unnamed Item, Unnamed Item, Unnamed Item, Data Privacy for $\mathcal{ALC}$ Knowledge Bases, Information-Optimal Reflections of View Updates on Relational Database Schemata, Semi-oblivious chase termination: the sticky case, Restricted Chase Termination for Existential Rules: A Hierarchical Approach and Experimentation, Characterizing Boundedness in Chase Variants, Schema mapping coverage, Universal solutions for temporal data exchange, Semantic Acyclicity for Conjunctive Queries: Approximations and Constraints, A Single Approach to Decide Chase Termination on Linear Existential Rules, Datalog: Bag Semantics via Set Semantics, A Fuzzy Extension of Data Exchange, Combining Consistency and Confidentiality Requirements in First-Order Databases, Foundations of ontology-based data access under bag semantics, A more general theory of static approximations for conjunctive queries, Query answering over inconsistent knowledge bases: a probabilistic approach, Semantic Bijectivity and the Uniqueness of Constant-Complement Updates in the Relational Context, Schema Mappings: A Case of Logical Dynamics in Database Theory, The Impact of Active Domain Predicates on Guarded Existential Rules, Preference-based inconsistency-tolerant query answering under existential rules

Cites Work