Optimization of logic queries in knowledge base systems
Premchand S. Nair · Spectrum Research Repository (Concordia University) · 1989
One of the ways for implementing a Knowledge Base System is to augment a traditional Relational Data Base System with deductive capabilities. A major issue has been to find an efficient implementation supporting recursive queries expressed in first order logic. An efficient optimization strategy, called Integrated Magic Set (IMS) method, is introduced and is shown to be superior to other known query optimization methods. Two parallel algorithms for efficient query evaluation of Datalog programs have been developed which can be implemented in any distributed architecture. The performance comparisons between the parallel algorithms and a serial algorithm are presented using an analytical model. The analysis establishes the superiority of the parallel algorithms over the semi-naive serial algorithm. Optimization techniques based on the concept of permutation dependency are presented. This achieves optimization at different levels: (1) for storing a base predicate, (2) for removing redundant rules from a Datalog program, (3) for rewriting a Datalog program so that the resultant program is more suitable for magic set optimization and (4) for efficient computation of a derived predicate satisfying a permutation dependency. A classification of chain rule programs based on their computational complexity is provided. A non-regular chain rule program is shown to be computationally more complex than a chain rule program. An algorithm to determine whether or not a given binary rule program has an equivalent chain rule program is presented.