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

Cristina Civili, Riccardo Rosati

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

Abstract / Description of output

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 languageEnglish
Title of host publicationDatalog in Academia and Industry
Subtitle of host publicationSecond International Workshop, Datalog 2.0, Vienna, Austria, September 11-13, 2012. Proceedings
PublisherSpringer Berlin Heidelberg
Number of pages13
ISBN (Electronic)978-3-642-32925-8
ISBN (Print)978-3-642-32924-1
Publication statusPublished - 2012

Publication series

NameLecture Notes in Computer Science
PublisherSpringer Berlin Heidelberg
ISSN (Print)0302-9743


Dive into the research topics of 'A Broad Class of First-Order Rewritable Tuple-Generating Dependencies'. Together they form a unique fingerprint.

Cite this