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

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

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 proceeding › Conference 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 language	English
Title of host publication	Proceedings of the 4th International Workshop on the Resurgence of Datalog in Academia and Industry (Datalog-2.0 2022)
Editors	Mario Alviano, Andreas Pieris
Publisher	CEUR-WS.org
Pages	14-26
Publication status	Published - 5 Sept 2022
Event	4th International Workshop on the Resurgence of Datalog in Academia and Industry - Genova - Nervi, Italy Duration: 5 Sept 2022 → 5 Sept 2022 https://sites.google.com/unical.it/datalog20-2022

Publication series

Name	CEUR Workshop Proceedings
Volume	3203
ISSN (Electronic)	1613-0073

Workshop

Workshop	4th International Workshop on the Resurgence of Datalog in Academia and Industry
Abbreviated title	DATALOG 2.0 2022
Country/Territory	Italy
City	Genova - Nervi
Period	5/09/22 → 5/09/22
Internet address	https://sites.google.com/unical.it/datalog20-2022

Keywords / Materials (for Non-textual outputs)

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

Access to Document

Certain Answers_GHEERBRANT_DOA05082022_VOR_CC-BYFinal published version, 1.16 MBLicence: Creative Commons: Attribution (CC-BY)

http://ceur-ws.org/Vol-3203/Licence: Creative Commons: Attribution (CC-BY)

MAGIC: MAnaGing InComplete Data - New Foundations
Libkin, L.
EPSRC
1/10/16 → 31/08/22
Project: Research

Cite this

Gheerbrant, A., Libkin, L., Rogova, A., & Sirangelo, C. (2022). Certain Answers of Extensions of Conjunctive Queries by Datalog and First-Order Rewriting. In M. Alviano, & A. Pieris (Eds.), Proceedings of the 4th International Workshop on the Resurgence of Datalog in Academia and Industry (Datalog-2.0 2022) (pp. 14-26). (CEUR Workshop Proceedings; Vol. 3203). CEUR-WS.org. http://ceur-ws.org/Vol-3203/

Gheerbrant, Amélie ; Libkin, Leonid ; Rogova, Alexandra et al. / Certain Answers of Extensions of Conjunctive Queries by Datalog and First-Order Rewriting. Proceedings of the 4th International Workshop on the Resurgence of Datalog in Academia and Industry (Datalog-2.0 2022). editor / Mario Alviano ; Andreas Pieris. CEUR-WS.org, 2022. pp. 14-26 (CEUR Workshop Proceedings).

@inproceedings{deacdc3a69c64bb59e965d64ae4536a3,

title = "Certain Answers of Extensions of Conjunctive Queries by Datalog and First-Order Rewriting",

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.",

keywords = "Incomplete information, Certain answers, Datalog rewritings, First-order rewritings, Functional dependencies,, Chase",

author = "Am{\'e}lie Gheerbrant and Leonid Libkin and Alexandra Rogova and Cristina Sirangelo",

year = "2022",

month = sep,

day = "5",

language = "English",

series = "CEUR Workshop Proceedings",

publisher = "CEUR-WS.org",

pages = "14--26",

editor = "Mario Alviano and Andreas Pieris",

booktitle = "Proceedings of the 4th International Workshop on the Resurgence of Datalog in Academia and Industry (Datalog-2.0 2022)",

note = "4th International Workshop on the Resurgence of Datalog in Academia and Industry, DATALOG 2.0 2022 ; Conference date: 05-09-2022 Through 05-09-2022",

url = "https://sites.google.com/unical.it/datalog20-2022",

}

Gheerbrant, A, Libkin, L, Rogova, A & Sirangelo, C 2022, Certain Answers of Extensions of Conjunctive Queries by Datalog and First-Order Rewriting. in M Alviano & A Pieris (eds), Proceedings of the 4th International Workshop on the Resurgence of Datalog in Academia and Industry (Datalog-2.0 2022). CEUR Workshop Proceedings, vol. 3203, CEUR-WS.org, pp. 14-26, 4th International Workshop on the Resurgence of Datalog in Academia and Industry, Genova - Nervi, Italy, 5/09/22. <http://ceur-ws.org/Vol-3203/>

Certain Answers of Extensions of Conjunctive Queries by Datalog and First-Order Rewriting. / Gheerbrant, Amélie; Libkin, Leonid; Rogova, Alexandra et al.
Proceedings of the 4th International Workshop on the Resurgence of Datalog in Academia and Industry (Datalog-2.0 2022). ed. / Mario Alviano; Andreas Pieris. CEUR-WS.org, 2022. p. 14-26 (CEUR Workshop Proceedings; Vol. 3203).

Research output: Chapter in Book/Report/Conference proceeding › Conference contribution

TY - GEN

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

AU - Gheerbrant, Amélie

AU - Libkin, Leonid

AU - Rogova, Alexandra

AU - Sirangelo, Cristina

PY - 2022/9/5

Y1 - 2022/9/5

N2 - 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.

AB - 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.

KW - Incomplete information

KW - Certain answers

KW - Datalog rewritings

KW - First-order rewritings

KW - Functional dependencies,

KW - Chase

M3 - Conference contribution

T3 - CEUR Workshop Proceedings

SP - 14

EP - 26

BT - Proceedings of the 4th International Workshop on the Resurgence of Datalog in Academia and Industry (Datalog-2.0 2022)

A2 - Alviano, Mario

A2 - Pieris, Andreas

PB - CEUR-WS.org

T2 - 4th International Workshop on the Resurgence of Datalog in Academia and Industry

Y2 - 5 September 2022 through 5 September 2022

ER -

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

Abstract

Publication series

Workshop

Keywords / Materials (for Non-textual outputs)

Access to Document

Fingerprint

Projects

MAGIC: MAnaGing InComplete Data - New Foundations

Cite this