Record Details

On a theory of probabilistic deductive databases

DSpace at IIT Bombay

View Archive Info
 
 
Field Value
 
Title On a theory of probabilistic deductive databases
 
Creator LAKSHMANAN, LVS
SADRI, F
 
Subject logic
semantics
probabalistic databases
uncertain databases
deductive databases
 
Description We propose a framework for modeling uncertainty where both belief and doubt can be given independent, first-class status. We adopt probability theory as the mathematical formalism for manipulating uncertainty. An agent can express the uncertainty in her knowledge about a piece of information in the form of a confidence level, consisting of a pair of intervals of probability, one for each of her belief and doubt. The space of confidence levels naturally leads to the notion of a trilattice, similar in spirit to Fitting's bilattices. Intuitively, the points in such a trilattice can be ordered according to truth, information, or precision. We develop a framework for probabilistic deductive databases by associating confidence levels with the facts and rules of a classical deductive database. While the trilattice structure offers a variety of choices for defining the semantics of probabilistic deductive databases, our choice of semantics is based on the truth-ordering, which we find to be closest to the classical framework for deductive databases. In addition to proposing a declarative semantics based on valuations and an equivalent semantics based on fixpoint theory, we also propose a proof procedure and prove it sound and complete. We show that while classical Datalog query programs have a polynomial time data complexity, certain query programs in the probabilistic deductive database framework do not even terminate on some input databases. We identify a large natural class of query programs of practical interest in our framework, and show that programs in this class possess polynomial time data complexity, i.e. not only do they terminate on every input database, they are guaranteed to do so in a number of steps polynomial in the input database size.
 
Publisher CAMBRIDGE UNIV PRESS
 
Date 2011-07-19T10:40:43Z
2011-12-26T12:51:09Z
2011-12-27T05:37:36Z
2011-07-19T10:40:43Z
2011-12-26T12:51:09Z
2011-12-27T05:37:36Z
2001
 
Type Article
 
Identifier THEORY AND PRACTICE OF LOGIC PROGRAMMING, 1(), 5-42
1471-0684
http://dx.doi.org/10.1017/S1471068400001058
http://dspace.library.iitb.ac.in/xmlui/handle/10054/5269
http://hdl.handle.net/10054/5269
 
Language en