A nondeterministic deductive database language with tuple-identifications
Yeh-Heng Sheng · 1991
The use of non-deterministic database languages is motivated using both pragmatic and theoretical considerations. There are natural non-deterministic queries whose implementation using deterministic languages is unintuitive and inefficient. One typical example is sampling queries, i.e., queries that randomly choose certain samples from a set of tuples, such as Find an arbitrary set of employee samples that contains exactly N employees from each department (assuming each department has at least N employees), and Find an arbitrary cafe at the intersection of Blvd. St. Germain and Blvd. St. Michel (ASV90) . Another consideration in favor of non-determinism is optimization. Intuitively, a non-deterministic program gives a certain degree of freedom in the computation of a query, which can be exploited in optimization. The theoretical considerations for non-determinism involve mainly issues of expressive power. The expressive power of pure deductive database languages, such as DATALOG and stratified DATALOG with negation, is limited in a sense that some useful queries such as functions involving aggregation are not definable in these languages. By having in the database language an on the domain of the database, the expressive power can be enhanced so that, for example, some functions involving aggregation can be defined. Yet, a direct implementation of the ordering in deductive database languages may seem unintuitive, and may not be very efficient to use in practice. This dissertation proposes a non-deterministic deductive database language that employs tuple-identifications and has a declarative semantics which is a simple extension of first-order logic semantics. Sampling queries can be easily defined in this language. Tuple-identifications also provide users with an explicit construct for optimization. Moreover, through the use of these tuple-identifications, different orderings are defined as a result. Compared with orderings on the database domain, the proposed deductive database language is more intuitive, easier to use, and can be implemented efficiently. It has greater expressive power and, in fact, the language defines all computable queries.