Extended Deductive Databases with Uncertain Information

The paper presents an approach for handling uncertain information in deductive databases using multivalued logics. Uncertainty means that database facts may be assigned logical values other than the conventional ones - true and false. The logical values represent various degrees of truth, which may be combined and propagated by applying the database rules. A corresponding multivalued database semantics is defined. We show that it extends successful conventional semantics as the well-founded semantics, and has a polynomial time data complexity.

Authors:

• Daniel Stamate

Keywords:

• Reasoning under uncertainty
• multivalued logics
• deductive databases
• logic programs
• multivalued semantics.

References:

[1] S. V. Alagar, F. Sadri, J. N. Said, "Semantics of an Extended Relational
Model for Managing Uncertain Information", Proc. of International
Conference on Information and Knowledge Management, 1995
[2] P. Bosc, H. Prade, "An Introduction to the Fuzzy Set and Possibility
Theory-Based Treatment of Flexible Queries and Uncertain or Imprecise
Databases", Uncertainty Management in Information Systems, Kluwer
Academic Publishers, 1996
[3] D. Dubois, J. Lang, H. Prade, "Towards Possibilistic Logic Programming",
Proc. of the Eight Intl. Conf. on Logic Programming, 1991
[4] M. H. van Emden, "Quantitative deduction and its fi xpoint theory", J.
Logic Programming, 3(1), 1986
[5] R. Fagin, "Combining fuzzy information from multiple systems", J.
Computer and System Sciences, 58:1, 1999
[6] M. Fitting, "The Family of Stable Models", J. Logic Programming,
17(2,3&4), 1993
[7] M. Fitting, "Fixpoint semantics for logic programming - a survey", J.
Theoretical Computer Science, 278(1-2), 2002
[8] N. Fuhr T. R¨olleke "HySpirit - a Probabilistic Inference Engine for
Hypermedia Retrieval in Large Databases", Proc. of 6th International
Conference on Extending Database Technology, 1998
[9] M. Gelfond, V. Lifschitz, "The Stable Model Semantics for Logic
Programming", Proc. of the Fifth Logic Programming Symposium, 1988
[10] A. Van Gelder, K.A. Ross, J.S. Schlipf, "The Well-Founded Semantics
for General Logic Programs", J. ACM, 38(3), 1991
[11] M. Kifer, V. S. Subrahmanian, "Theory of Generalized Annotated Logic
Programming and its Applications", J. Logic Programming, 12:(3-4),
1992
[12] V. S. Lakshmanan, F. Sadri, "Modeling Uncertainty in Deductive
Databases", Proc. of 5th International Conference of Database and
Expert Systems Applications, 1994
[13] V.S. Lakshmanan, N. Leone, R. Ross, V.S. Subrahmanian, "ProbView:
a flexible probabilistic database system", J. ACM Transactions on
Database Systems 22:3, 1997
[14] V.S. Lakshmanan, F. Sadri "Probabilistic Deductive Databases", Proc.
of International Logic Programming Symp., 1994
[15] V. S. Lakshmanan, F. Sadri, "On a theory of probabilistic deductive
databases", J. Theory and Practice of Logic Programming, 1(1), 2001
[16] Y. Loyer, N. Spyratos, D. Stamate, "Parameterised Semantics for Logic
Programs - a Unifying Framework", J. Theor. Comput. Sci., 308(1-3),
2003
[17] Y. Loyer, N. Spyratos, D. Stamate, "Hypothesis-based semantics of logic
programs in multivalued logics", J. ACM Transactions on Computational
Logic 15(3), 2004
[18] B. Mobasher, D. Pigozzi, G. Slutzki, "Multi-valued logic programming
semantics: An algebraic approach", J. Theor. Comput. Sci., 171:(1-2),
1997
[19] R. Ng, V. S. Subrahmanian, "Relating Dempster-Shafer Theory to Stable
Semantics", Proc. of International Logic Programming Symp., 1991
[20] R. Ng, V. S. Subrahmanian "Probabilistic Logic Programming", J.
Information and Computation, 101:2, 1992
[21] T.C. Przymusinski, "Extended Stable Semantics for Normal and Disjunctive
Programs", Proc. of the Seventh Intl. Conference on Logic
Programming, 1990
[22] T.C. Przymusinski, "Well-Founded Semantics Coincides with Three-
Valued Stable Semantics", Fundam. Inform., 13, 1990
[23] F. Sadri, M. Bianco "On Equivalence of Queries in Uncertain
Databases", Proc. of ACM International Conference on Information and
Knowledge Management, 2000
[24] E.Y. Shapiro, "Logic Programs With Uncertainties: A Tool for Implementing
Rule-Based Systems", Proc. of 8th International Joint Conference
on Artifi cial Intelligence, 1983
[25] V.S. Subrahmanian, "Probabilistic Databases and Logic Programming",
Proc. of 17th International Conference of Logic Programming, 2001
[26] M.Y. Vardi, "The complexity of relational query languages", Proc. of
ACM Symp. on Theory of Computing, STOC, 1982