On the first-order reducibility of unions of conjunctive queries over inconsistent databases

Domenico Lembo, Riccardo Rosati, Marco Ruzzi.
In Proceedings of the International Workshop on Inconsistency and Incompleteness in Databases (IIDB 2006), Lecture Notes in Computer Science, volume 4254, Springer, 2006. ISBN 978-3-540-46788-5.

 

Abstract:

Recent approaches in the research on inconsistent databases have started analyzing the first-order reducibility of consistent query answering, i.e., the possibility of identifying classes of queries whose consistent answers can be obtained by a first-order (FOL) rewriting of the query, which in turn can be easily formulated in SQL and directly evaluated through any relational DBMS. So far, the investigations in this direction have only concerned subsets of conjunctive queries over databases with key dependencies. In this paper we extend the study of first-order reducibility of consistent query answering under key dependencies to more expressive queries, in particular to unions of conjunctive queries. More specifically: (i) we analyze the applicability of known FOL-rewriting techniques for conjunctive queries in the case of unions of conjunctive queries. It turns out that such techniques are applicable only to a very restricted class of unions of conjunctive queries; (ii) to overcome the above limitations, we define a new rewriting method which is specifically tailored for unions of conjunctive queries. The method can be applied only to unions of conjunctive queries that satisfy an acyclicity condition on unions of conjunctive queries.

Bibtex entry:

@String{IIDB-06 = "Proceedings of the International Workshop on Inconsistency and Incompleteness in Databases (IIDB~2006)"}

@String{LNCS = "Lecture Notes in Computer Science"}

@String{SV = "Springer"}

@Inproceedings{LeRR06,
author = "Domenico Lembo and Riccardo Rosati and Marco Ruzzi",
title = "On the first-order reducibility of unions of conjunctive queries over inconsistent databases",
booktitle = IIDB-06,
publisher = SV,
series = LNCS,
volume = 4254,
year = 2006,
isbn = "978-3-540-46788-5",
}

Link to electronic version of published paper