A Broad Class of First-Order Rewritable Tuple-Generating Dependencies

Cristina Civili; Riccardo Rosati

doi:10.1007/978-3-642-32925-8_8

A Broad Class of First-Order Rewritable Tuple-Generating Dependencies

Cristina Civili, Riccardo Rosati

School of Informatics

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

Abstract

We study reasoning, and in particular query answering, over databases with tuple-generating dependencies (TGDs). Our focus is on classes of TGDs for which conjunctive query answering is first-order rewritable, i.e., can be reduced to the standard evaluation of a first-order query over the database. In this paper, we define the class of weakly recursive TGDs, and prove that this class comprises and generalizes every previously known FOL-rewritable class of TGDs, under fairly general assumptions on the form of the TGDs.

Original language	English
Title of host publication	Datalog in Academia and Industry
Subtitle of host publication	Second International Workshop, Datalog 2.0, Vienna, Austria, September 11-13, 2012. Proceedings
Publisher	Springer Berlin Heidelberg
Pages	68-80
Number of pages	13
ISBN (Electronic)	978-3-642-32925-8
ISBN (Print)	978-3-642-32924-1
DOIs	https://doi.org/10.1007/978-3-642-32925-8_8
Publication status	Published - 2012

Publication series

Name	Lecture Notes in Computer Science
Publisher	Springer Berlin Heidelberg
Volume	7494
ISSN (Print)	0302-9743

Access to Document

10.1007/978-3-642-32925-8_8

http://link.springer.com/chapter/10.1007%2F978-3-642-32925-8_8

Cite this

@inproceedings{58e3b8c1b9a547bfbc200b3178f9921d,

title = "A Broad Class of First-Order Rewritable Tuple-Generating Dependencies",

abstract = "We study reasoning, and in particular query answering, over databases with tuple-generating dependencies (TGDs). Our focus is on classes of TGDs for which conjunctive query answering is first-order rewritable, i.e., can be reduced to the standard evaluation of a first-order query over the database. In this paper, we define the class of weakly recursive TGDs, and prove that this class comprises and generalizes every previously known FOL-rewritable class of TGDs, under fairly general assumptions on the form of the TGDs.",

author = "Cristina Civili and Riccardo Rosati",

year = "2012",

doi = "10.1007/978-3-642-32925-8_8",

language = "English",

isbn = "978-3-642-32924-1",

series = "Lecture Notes in Computer Science",

publisher = "Springer Berlin Heidelberg",

pages = "68--80",

booktitle = "Datalog in Academia and Industry",

}

A Broad Class of First-Order Rewritable Tuple-Generating Dependencies. / Civili, Cristina; Rosati, Riccardo.

Datalog in Academia and Industry: Second International Workshop, Datalog 2.0, Vienna, Austria, September 11-13, 2012. Proceedings. Springer Berlin Heidelberg, 2012. p. 68-80 (Lecture Notes in Computer Science; Vol. 7494).

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

TY - GEN

T1 - A Broad Class of First-Order Rewritable Tuple-Generating Dependencies

AU - Civili, Cristina

AU - Rosati, Riccardo

PY - 2012

Y1 - 2012

N2 - We study reasoning, and in particular query answering, over databases with tuple-generating dependencies (TGDs). Our focus is on classes of TGDs for which conjunctive query answering is first-order rewritable, i.e., can be reduced to the standard evaluation of a first-order query over the database. In this paper, we define the class of weakly recursive TGDs, and prove that this class comprises and generalizes every previously known FOL-rewritable class of TGDs, under fairly general assumptions on the form of the TGDs.

AB - We study reasoning, and in particular query answering, over databases with tuple-generating dependencies (TGDs). Our focus is on classes of TGDs for which conjunctive query answering is first-order rewritable, i.e., can be reduced to the standard evaluation of a first-order query over the database. In this paper, we define the class of weakly recursive TGDs, and prove that this class comprises and generalizes every previously known FOL-rewritable class of TGDs, under fairly general assumptions on the form of the TGDs.

U2 - 10.1007/978-3-642-32925-8_8

DO - 10.1007/978-3-642-32925-8_8

M3 - Conference contribution

SN - 978-3-642-32924-1

T3 - Lecture Notes in Computer Science

SP - 68

EP - 80

BT - Datalog in Academia and Industry

PB - Springer Berlin Heidelberg

ER -