Title :
CQA-WF: Consistent Query Answers to Conjunctive Queries Using the Well-Founded Semantics
Author :
Belmar, J. ; Cuevas, J. ; Caniupan, M.
Author_Institution :
Univ. del Bio-Bio, Concepcion, Chile
Abstract :
A database instance can become inconsistent with respect to its integrity constraints (ICs), for instance, after update operations. When this happens, it is possible to compute the repairs of the database. A minimal repair is a new database instance that satisfies the ICs, is obtained by applying update operations over the original instance, and differs minimally from the original instance. We can evaluate queries over the repairs, an answer to a conjunctive query is consistent if it is an answer in every repair. The repairs of database instances can be specified by repair programs. Moreover, we can compute consistent answers to queries by evaluating query programs together with the repair programs under the stable model semantics. The use of logic programs does not exceed the intrinsic complexity of consistent query answering. Nevertheless, for a certain class of conjunctive queries and ICs it is possible to use the alternative well-founded semantics (WFS) to evaluate queries. We present CQA-WF, a system that allows the computation of consistent answers to conjunctive queries over inconsistent databases with respect to functional dependencies (FDs). CQA-WF evaluates logic programs under the WFS. The WFS has lower data complexity than the stable models semantics.
Keywords :
data integrity; database management systems; logic programming; programming language semantics; query processing; CQA-WF; conjunctive query; consistent query answers; data complexity; database instance repair; functional dependency; inconsistent database; integrity constraint; logic program evaluation; query evaluation; query program evaluation; stable model semantics; update operation; well-founded semantics; Complexity theory; Computational modeling; Data models; Databases; Maintenance engineering; Null value; Semantics; Well-founded semantics; consistent query answering; functional dependencies; inconsistencies; repairs;
Conference_Titel :
Computer Science Society (SCCC), 2011 30th International Conference of the Chilean
Conference_Location :
Curico
Print_ISBN :
978-1-4673-1364-3
DOI :
10.1109/SCCC.2011.9