NDLI: Query languages for data exchange: beyond unions of conjunctive queries

Please wait, while we are loading the content...

Automatic verification of database-driven systems: a new frontier

Repair checking in inconsistent databases: algorithms and complexity

Structural characterizations of schema-mapping languages

Optimal splitters for database partitioning with size bounds

A compositional query algebra for second-order logic and uncertain databases

Incremental XPath evaluation

Towards a theory of search queries

Automatic construction of simple artifact-based business processes

Tight results for clustering and summarizing data streams

Containment of conjunctive queries on annotated relations

$Datalog^{±}:$ a unified approach to ontologies and integrity constraints

Consistent query answering under primary keys: a characterization of tractable queries

Query languages for data exchange: beyond unions of conjunctive queries

Efficient data structures for range-aggregate queries on trees

A logical account of uncertain databases based on linear logic

Efficient asymmetric inclusion between regular expression types

Reconcilable differences

TOP-K projection queries for probabilistic business processes

Analysis of sampling techniques for association rule mining

Optimizing user views for workflows

On approximating optimum repairs for functional dependency violations

Querying data sources that export infinite sets of views

Faster join-projects and sparse matrix multiplications

A compositional framework for complex queries over uncertain data

How big must complete XML query languages be?

Automatic verification of data-centric business processes

The average-case complexity of counting distinct elements

Query languages for data exchange: beyond unions of conjunctive queries

Content Provider	ACM Digital Library
Author	Reutter, Juan Arenas, Marcelo Barceló, Pablo
Abstract	The class of unions of conjunctive queries (UCQ) has been shown to be particularly well-behaved for data exchange; its certain answers can be computed in polynomial time (in terms of data complexity). However, this is not the only class with this property; the certain answers to any Datalog program can also can be computed in polynomial time. The problem is that both UCQ and Datalog do not allow negated atoms, as adding an unrestricted form of negation to these languages yields to intractability. In this paper, we propose a language called $Datalog^{C(≠)}$ that extends Datalog with a restricted form of negation, and study some of its fundamental properties. In particular, we show that the certain answers to a $Datalog^{C(≠)}$ program can be computed in polynomial time (in terms of data complexity), and that every union of conjunctive queries with at most one inequality or negated relational atom per disjunct, can be efficiently rewritten as a $Datalog^{C(≠)}$ program in the context of data exchange. Furthermore, we show that this is also the case for a syntactic restriction of the class of unions of conjunctive queries with at most two inequalities per disjunct. This syntactic restriction is given by two conditions that are optimal, in the sense that computing certain answers becomes intractable if one removes any of them. Finally, we provide a thorough analysis of the combined complexity of computing certain answers to $Datalog^{C(≠)}$ programs and other related query languages. In particular, we show that this problem is Exptime-complete for $Datalog^{C(≠)},$ even if one restricts to conjunctive queries with single inequalities, which is a fragment of $Datalog^{C(≠)}$ by the result mentioned above. Furthermore, we show that the combined complexity is CoNexptime-complete for the case of conjunctive queries with k inequalities, for every k ≥ 2.
Starting Page	73
Ending Page	83
Page Count	11
File Format	PDF
ISBN	9781605584232
DOI	10.1145/1514894.1514904
Language	English
Publisher	Association for Computing Machinery (ACM)
Publisher Date	2009-03-23
Publisher Place	New York
Access Restriction	Subscribed
Content Type	Text
Resource Type	Article

Sl.	Authority	Responsibilities	Communication Details
1	Ministry of Education (GoI), Department of Higher Education	Sanctioning Authority	https://www.education.gov.in/ict-initiatives
2	Indian Institute of Technology Kharagpur	Host Institute of the Project: The host institute of the project is responsible for providing infrastructure support and hosting the project	https://www.iitkgp.ac.in
3	National Digital Library of India Office, Indian Institute of Technology Kharagpur	The administrative and infrastructural headquarters of the project	Dr. B. Sutradhar bsutra@ndl.gov.in
4	Project PI / Joint PI	Principal Investigator and Joint Principal Investigators of the project	Dr. B. Sutradhar bsutra@ndl.gov.in Prof. Saswat Chakrabarti will be added soon
5	Website/Portal (Helpdesk)	Queries regarding NDLI and its services	support@ndl.gov.in
6	Contents and Copyright Issues	Queries related to content curation and copyright issues	content@ndl.gov.in
7	National Digital Library of India Club (NDLI Club)	Queries related to NDLI Club formation, support, user awareness program, seminar/symposium, collaboration, social media, promotion, and outreach	clubsupport@ndl.gov.in
8	Digital Preservation Centre (DPC)	Assistance with digitizing and archiving copyright-free printed books	dpc@ndl.gov.in
9	IDR Setup or Support	Queries related to establishment and support of Institutional Digital Repository (IDR) and IDR workshops	idr@ndl.gov.in

Query Languages for Data Exchange: Beyond Unions of Conjunctive Queries

Query Languages for Data Exchange: Beyond Unions of Conjunctive Queries (2010)

The Data Complexity of Consistent Query Answering for Self-Join-Free Conjunctive Queries Under Primary Key Constraints

Containment of conjunctive queries: beyond relations as sets

Data exchange: computing cores in polynomial time

Efficient approximations of conjunctive queries

Scalable containment for unions of conjunctive queries under constraints

Expressive languages for path queries over graph-structured data

Equivalence and minimization of conjunctive queries under combined semantics

Query languages for data exchange: beyond unions of conjunctive queries

Similar Documents

Query Languages for Data Exchange: Beyond Unions of Conjunctive Queries

Query Languages for Data Exchange: Beyond Unions of Conjunctive Queries (2010)

The Data Complexity of Consistent Query Answering for Self-Join-Free Conjunctive Queries Under Primary Key Constraints

Containment of conjunctive queries: beyond relations as sets

Data exchange: computing cores in polynomial time

Efficient approximations of conjunctive queries

Scalable containment for unions of conjunctive queries under constraints

Expressive languages for path queries over graph-structured data

Equivalence and minimization of conjunctive queries under combined semantics

Query languages for data exchange: beyond unions of conjunctive queries