Queries in deductive database systems (query processing, artificial intelligence)
Ey-Chih Chow · 1984
The problem of efficiently evaluating queries in deductive, relational database systems is examined. The major areas investigated are: (1) appropriate arrangements of data, intensional and extensional, in deductive database systems, (2) efficient sequential evaluation strategies that take advantage of the underlying data characteristics and query semantics, and (3) efficient parallel evaluation strategies that are tailored to distinct types of queries. First, the database formalism of Prolog logic is argued to be appropriate for such systems. Query evaluation strategies based on the traditional Prolog deductive mechanism are then examined to determine their efficiency under different environments. This examination is done through two distinct categories of systems: a simplified model of a conventional database system and a purely deductive database system. These two systems are distinct in their underlying data characteristics and query semantics. Their different data characteristics are due to different data-saving schemes, which achieve storage saving and high expressive power, respectively, under varying applications. Differences in data characteristics include relative amount of extensional vs. intensional data, the order of each relation, the number of clauses per relation, and the overall syntactic structure of data per relation. Semantics of queries, on the other hand, deal with the number of qualifying instantiations required to answer a query. The analysis shows that, for sequential evaluation in the simplified model of a conventional database system, the traditional Prolog deductive mechanism is able to provide only primitive techniques for trimming down the cross products of multi-relation queries. This turns out to be the most expensive part of query evaluation in such systems. For sequential evaluation in the purely deductive database system, by contrast, the Prolog deductive mechanism is adequate for efficient evaluation of queries provided the system has a sophisticated technique for ordering predicates in the qualifications of queries being evaluated. For parallel evaluation, on the other hand, the maximal efficient strategies in the simplified model of conventional database systems are characterized by dividing-by-relation. Those in the purely deductive database systems are characterized by dividing-by-clause. (Abstract shortened with permission of author.)