Extended Deductive Databases with Uncertain Information

Authors: Daniel Stamate

Abstract:

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.

Keywords: Reasoning under uncertainty, multivalued logics, deductive databases, logic programs, multivalued semantics.

Digital Object Identifier (DOI): doi.org/10.5281/zenodo.1333482

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