Empirical probabilities in monadic deductive databases

ABSTRACT

We address the problem of supporting empirical probabilities in monadic logic databases. Though the semantics of multivalued logic programs has been studied extensively, the treatment of probabilities as results of statistical findings has not been studied in logic programming/deductive databases. We develop a model-theoretic characterization of logic databases that facilitates such a treatment. We present an algorithm for checking consistency of such databases and prove its total correctness. We develop a sound and complete query processing procedure for handling queries to such databases.

References

1. S. Amager, D. Dubois and H. Prude. (1991) Constraint Propagation with Imprecise Conditional Probabilities, Proc. 1991 International Conference on Uncertainty in AI, pp 26-34.
2. F. Bacchus. (1990) Representing and Reasoning with Probabilistic Knowledge, MIT Press.
3. J.F. Baldwin. (1987) Evidential Support Logic Programming, J. of Fuzzy Sets and Systems, 24, pp. 1-26.
4. C. Bell, A. Nerode, R. Ng and V.S. Subrahmanian. (1992) Implementing Deductive Databases by Linear Programming, to appear in Symposium on Principles of Database Systems.
5. H. A. Blair and V.S. Subrahmanian. (1987) Paraconsistent Logic Programming, Theoretical Computer Science, 68, pp. 35-54.
6. D. Dubois, H. Prade and J. Lang. (1991) Towards Possibilistic Logic Programming, Proc. 1991 Intl. Conf. on Logic Programming, ed. K. Furukawa, pp. 581-595, MIT Press.
7. R. Fagin, J. Y. Halpern and N. Megiddo. (1989) A Logic for Reasoning About Probabilities, to appear in: Information and Computation.
8. M. C. Fitting. (1988) Bilattices and the Semantics of Logic Programming, to appear in: Journal of Logic Programming.
9. H. Geffner (1989) Default Reasoning: Causal and Conditional Theories, Technical Report 137, Cognitive Systems Laboratory, University of California, Los Angeles.
10. D. Kavvadias and C. H. Papadimitriou. (1990) A Linear Programming Approach to Reasoning About Probabilities, Annals of Mathematics and Artificial Intelligence, 1, pp. 189-205.
11. M. Kifer and V. S. Subrahmanian. (1991) Theory of Generalized Annotated Logic Programming and its Applications, Journal of Logic Programming, 12, 4, pp. 335-368.
12. H. E. Kyburg, Jr. (1974) The Logical Foundations of Statistical Inference, D. Reidel.
13. R.T. Ng and V.S. Subrahmanian. (1989) Probabilistic Logic Programming, to appear in: Information and Computation. Preliminary version in: Proc. 5th International Symposium on Methodologies for Intelligent Systems, pp 9-16.
14. R.T. Ng and V.S. Subrahmanian. (1991) Stable Semantics for Probabilistic Deductive Databases, to appear in: Information and Computation (1993). Preliminary versions in: Proc. 1991 International Conference on Uncertainty in AI, pp 249-256.
15. R.T. Ng and V.S. Subrahmanian. (1992) Empirical Probabilities in Monadic Deductive Databases, Technical Report, University of Maryland, College Park.
16. N. Nilsson. (1986) Probabilistic Logic, AI Journal 28, pp 71-87.
17. G. Paass. (1988) Probabilistic Logic, Non-Standard Logics for Automated Reasoning, Academic Press, London, pp 213-252.
18. J. Pearl. (1988) Probabilistic Reasoning in Intelligent Systems: Networks of Plausible Inference, Morgan Kaufmann.
19. S. Schaible and T. Ibaraki. Fractional Programming, European Journal of Operations Research, 12, pp. 325-338.
20. M.H. van Emden. (1986) Quantitative Deduction and its Fixpoint Theory, Journal of Logic Programming, 4, 1, pp 37-53.

Index Terms

• Computing methodologies

  • Artificial intelligence

    • Knowledge representation and reasoning

      • Probabilistic reasoning

      • Vagueness and fuzzy logic

• Information systems

  • Information systems applications

• Theory of computation

  • Models of computation

    • Probabilistic computation