Random Databases and Threshold for MonotoneNon-Recursive Datalog

Abstract. In this paper we define a model of randomly generated databases andshow how one can compute the threshold functions for queries expressible in monotone non-recursive datalog6=. We also show that monotone non-recursivedatalog6 = cannot express any property with a sharp threshold. Finally, we show that non-recursive datalog6 = has a 0- 1 law for a large class of probability func-tions, defined in the paper. 1 Introduction In this paper we consider random databases, in which relations are generated based onsome standard probability distributions. Namely, we assume that every tuple belongs to a relation with an equal probability p, called the tuple probability. Similar probabilis-tic models have been intensively studied in the theory of random graphs (see e.g. [2, 11]), but also in the database theory (see e.g. [15, 10, 4]). We are interested in investi-gating the behavior of queries expressible in database query languages on the random databases. There are several interesting questions that can be asked about such queries,for example, calculating the probability of a query to be true as a function of p andthe domain size. One of the most important characteristics of probabilistic behavio