Paper Info
Title
Towards a logical reconstruction of a theory for locally closed databases
Abstract
The Closed World Assumption (CWA) on databases expresses the assumption that an atom not in the database is false. This assumption is applicable only in cases where the database has complete knowledge about the domain of discourse. In this article, we investigate locally closed databases, that is: databases that are sound but partially incomplete about their domain. Such databases consist of a standard database instance, augmented with a collection of Local Closed World Assumptions (LCWAs). A LCWA is a “local” form of the CWA, expressing that a database relation is complete in a certain area, called a window of expertise. In this work, we study locally closed databases both from a knowledge representation and from a computational perspective. At the representation level, the approach taken in this article distinguishes between the data that is conveyed by a database and the metaknowledge about the area in which the data is complete. We study the semantics of the LCWA's and relate it to several knowledge representation formalisms. At the reasoning level, we study the complexity of, and algorithms for two basic reasoning tasks: computing certain and possible answers to queries and determining whether a database has complete knowledge on a query. As the complexity of these tasks is unacceptably high, we develop efficient approximate methods for query answering. We also prove that for useful classes of queries and locally closed databases, these methods are optimal, and thus they solve the original query in a tractable way. As a result, we obtain classes of queries and locally closed databases for which query answering is tractable.
Year
DOI
Venue
2010
10.1145/1806907.1806914
ACM Trans. Database Syst.
Keywords
DocType
Volume
representation level,knowledge representation formalisms,Closed World Assumption,Local Closed World Assumptions,logical reconstruction,locally closed databases,closed world assumption,knowledge representation,databases,standard database instance,original query,query answering,database relation,complete knowledge
Journal
35
Issue
ISSN
Citations 
3
0362-5915
16
PageRank 
References 
Authors
0.75
61
4
Name
Order
Citations
PageRank
Marc Denecker11626106.40
Álvaro Cortés-Calabuig2674.40
Maurice Bruynooghes3160.75
Ofer Arieli470551.54