Title: Towards a logical reconstruction of a theory for locally closed databases
Authors: Denecker, Marc ×
Cort├ęs-Calabuig, Alvaro
Bruynooghe, Maurice
Arieli, Ofer #
Issue Date: Jul-2010
Publisher: Association for Computing Machinery
Series Title: ACM Transactions on Database Systems vol:35 issue:3 pages:1-60
Article number: 22
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 paper, 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 paper distinguishes
between the data that is conveyed by a database and the
meta-knowledge 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
ISSN: 0362-5915
Publication status: published
KU Leuven publication type: IT
Appears in Collections:Informatics Section
× corresponding author
# (joint) last author

Files in This Item:
File Description Status SizeFormat
Cortesetal.pdfmain article Accepted 443KbAdobe PDFView/Open
AppendixCortesetal.pdfAppendix Accepted 172KbAdobe PDFView/Open


All items in Lirias are protected by copyright, with all rights reserved.

© Web of science