Certain Answers of Extensions of Conjunctive Queries by Datalog and First-Order Rewriting

Amélie Gheerbrant, Leonid Libkin, Alexandra Rogova, Cristina Sirangelo

Research output: Chapter in Book/Report/Conference proceedingConference contribution

Abstract

To answer database queries over incomplete data the gold standard is finding certain answers: those that are true regardless of how incomplete data is interpreted. Such answers can be found efficiently for conjunctive queries and their unions, even in the presence of constraints such as keys or functional dependencies. With negation added, the complexity of finding certain answers becomes intractable however.

In this paper we exhibit a well-behaved class of queries that extends unions of conjunctive queries with a limited form of negation and that permits efficient computation of certain answers even in the presence of constraints by means of rewriting into Datalog with negation. The class consists of queries that are the closure of conjunctive queries under Boolean operations of union, intersection and difference. We show that for these queries, certain answers can be expressed in Datalog with negation, even in the presence of functional dependencies, thus making them tractable in data complexity. We show that in general Datalog cannot be replaced by first-order logic, but without constraints such a rewriting can be done in first-order.
Original languageEnglish
Title of host publicationProceedings of the 4th International Workshop on the Resurgence of Datalog in Academia and Industry (Datalog-2.0 2022)
EditorsMario Alviano, Andreas Pieris
PublisherCEUR-WS.org
Pages14-26
Publication statusPublished - 5 Sep 2022
Event4th International Workshop on the Resurgence of Datalog in Academia and Industry - Genova - Nervi, Italy
Duration: 5 Sep 20225 Sep 2022
https://sites.google.com/unical.it/datalog20-2022

Publication series

NameCEUR Workshop Proceedings
Volume3203
ISSN (Electronic)1613-0073

Workshop

Workshop4th International Workshop on the Resurgence of Datalog in Academia and Industry
Abbreviated titleDATALOG 2.0 2022
Country/TerritoryItaly
CityGenova - Nervi
Period5/09/225/09/22
Internet address

Keywords

  • Incomplete information
  • Certain answers
  • Datalog rewritings
  • First-order rewritings
  • Functional dependencies,
  • Chase

Cite this