Query Languages for Data Exchange: Beyond Unions of Conjunctive Queries

Simple item page
dc.contributor.authorArenas, Marcelo
dc.contributor.authorBarcelo, Pablo
dc.contributor.authorReutter, Juan
dc.date.accessioned2025-01-21T00:01:45Z
dc.date.available2025-01-21T00:01:45Z
dc.date.issued2011
dc.description.abstractThe 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.
dc.description.abstractIn this paper, we propose a language called Datalog (C(not equal)) 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(not equal)) 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(not equal)) 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(not equal)) programs and other related query languages. In particular, we show that this problem is Exptime-complete for Datalog (C(not equal)), even if one restricts to conjunctive queries with single inequalities, which is a fragment of Datalog (C(not equal)) 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 ka parts per thousand yen2.
dc.fuente.origenWOS
dc.identifier.doi10.1007/s00224-010-9259-6
dc.identifier.eissn1433-0490
dc.identifier.issn1432-4350
dc.identifier.urihttps://doi.org/10.1007/s00224-010-9259-6
dc.identifier.urihttps://repositorio.uc.cl/handle/11534/95394
dc.identifier.wosidWOS:000291159100014
dc.issue.numero2
dc.language.isoen
dc.pagina.final564
dc.pagina.inicio489
dc.revistaTheory of computing systems
dc.rightsacceso restringido
dc.subjectData exchange
dc.subjectCertain answers
dc.subjectQuery languages
dc.subjectDatalog
dc.subjectCombined complexity
dc.titleQuery Languages for Data Exchange: Beyond Unions of Conjunctive Queries
dc.typeartículo
dc.volumen49
sipa.indexWOS
sipa.trazabilidadWOS;2025-01-12
Files
Collections
Artículos de revistas