On the decidability and complexity of query answering over inconsistent and incomplete databases

By Andrea Calì, Domenico Lembo, Riccardo Rosati. ACM SIGACT-SIGMOD-SIGART Symposium on Principles of Database Systems, 2003

323 citations recorded by the source corpus.

How researchers see this paper

The researchers whose trusted networks rank it highest, strongest advocate first. Every researcher gets a different order.

Minimal-change integrity maintenance using tuple deletions (2002, background): “We also address in detail the issues arising in more recent work, namely [17] and [57].”
Taming the Infinite Chase: Query Answering under Expressive Relational Constraints (2008, background): “A mapping from a set of symbols S1 to another set of symbols S2 can be seen as a function µ : S1 → S2 defined as follows: (i) ∅ (the empty mapping) is a mapping; (ii) if µ is a mapping, then µ∪ {X → Y }, where X ∈ S1 and Y ∈ S2 is a mapping if µ does not already contain some X → Y ′ with Y 6= Y ′.”
A general datalog-based framework for tractable query answering over ontologies (2009, background): “We lift a result from [13] about non-key-conflicting inclusion dependencies to the setting of arbitrary TGDs to prove that the keys that we consider do not increase the complexity.”
On rules with existential variables: Walking the decidability line (2011, background): “In [13] an abstract condition called separability (generalizing the non-key-conflicting notions introduced in [17] and [12]) is defined on the set T ∪ E , where T is a set of TGDs and E is a set of EGDs.”