2011 | OriginalPaper | Buchkapitel
Datalog as a Query Language for Data Exchange Systems
verfasst von : Marcelo Arenas, Pablo Barceló, Juan Reutter
Erschienen in: Datalog Reloaded
Verlag: Springer Berlin Heidelberg
Aktivieren Sie unsere intelligente Suche, um passende Fachinhalte oder Patente zu finden.
Wählen Sie Textabschnitte aus um mit Künstlicher Intelligenz passenden Patente zu finden. powered by
Markieren Sie Textabschnitte, um KI-gestützt weitere passende Inhalte zu finden. powered by
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 for negated atoms, while most database query languages are equipped with negation. Unfortunately, adding an unrestricted form of negation to these languages yields to intractability of the problem of computing certain answers.
In order to face this challenge, we have recently proposed a language, called
Datalog
C( ≠ )
[5], that extends
Datalog
with a restricted form of negation while keeping the good properties of
Datalog
, and UCQ, for data exchange. In this article, we provide evidence in favor of the use of
Datalog
C( ≠ )
as a query language for data exchange systems. More precisely, we introduce the syntax and semantics of
Datalog
C( ≠ )
, we present some of the fundamental results about this language shown in [5], and we extend those results to the case of data exchange settings that allow for constraints in the target schema. All of these results provide justification for the use of
Datalog
C( ≠ )
in practice.