On A Theory of Probabilistic Deductive Databases

Title: On A Theory of Probabilistic Deductive Databases

Research Question: How can we model uncertainty in a knowledge-based system, where both belief and doubt can be given independent, first-class status?

Methodology: The authors propose a framework for managing uncertainty using probability theory. They introduce the concept of a confidence level, which consists of a pair of intervals of probability representing an agent's belief and doubt about a piece of information. This leads to the creation of a trilattice, similar to Fitting's bilattices, which can order points based on truth, information, or precision.

Results: The authors develop a framework for probabilistic deductive databases by associating confidence levels with facts and rules in a classical deductive database. They propose a declarative semantics based on valuations and an equivalent semantics based on fixpoint theory. Additionally, they provide a proof procedure and prove it to be sound and complete. The authors identify a large, naturally occurring class of query programs with polynomial time data complexity, demonstrating that these programs terminate in a number of steps polynomial in the input database size.

Implications: This research has significant implications for the field of knowledge-based systems. It provides a comprehensive framework for dealing with uncertainty, which is crucial for handling incomplete, inconsistent, and imperfect knowledge. The proposed methodology can lead to more accurate and reliable decision-making processes in various applications, such as expert systems, artificial intelligence, and data analysis.

Link to Article: https://arxiv.org/abs/0312043v1 Authors: arXiv ID: 0312043v1