Semantics, Consistency and Query Processing of

Empirical Deductive Databases

Raymond T. Ng?

Department of Computer Science
University of British Columbia
Vancouver, B.C., Canada V6T 1Z4

Abstract

In recent years, there has been growing interest in reasoning with uncertainty in logic programming and deductive databases. However, most frameworks proposed thus far are either non-probabilistic in nature or based on subjective probabilities. In this paper, we address the problem of incorporating empirical probabilities { that is, probabilities obtained from statistical findings { in deductive databases. To this end, we develop a formal model-theoretic basis for such databases. We also present a sound and complete algorithm for checking the consistency of such databases. Moreover, we develop consistency-preserving ways to optimize the algorithm for practical usage. Finally, we show how query answering for empirical deductive databases can be carried out.
Keywords: deductive databases, empirical probabilities, model semantics, constraint satisfaction, optimizations, query answering

1 Introduction

Uncertainty management plays a central role in everyday human decision making in general, and in many next-generation DBMSs in particular (e.g. one managing a scientific or image database). Of all scientific investigations into reasoning with uncertainty and chance, probability theory is one of the best understood paradigms. However, most of the probabilistic frameworks studied in deductive databases and artificial intelligence are based on subjective probabilities [18, 19, 21]. As argued by Bacchus [1], the subjective interpretation of probabilities view probabilities as degrees of belief, held by a particular agent at a particular time." This leads to the following difficulties in terms of usability: i) this view does not suggest how an agent can acquire the probabilities, and ii) this view does not provide a mechanism for the agent to revise the probabilities. In contrast, empirical probabilities represent statistical truths about the world. They are objective in nature and are independent of the belief of an agent. They can be obtained and updated by statistical samples. Thus, the aim of this paper is to study how empirical probabilities can be incorporated in deductive databases. ?Research partially sponsored by NSERC Grants OGP0138055 and STR0134419.