Soft stratification for magic set based query evaluation in deductive databases

Abstract

In this paper we propose a new bottom-up query evaluation method for stratified deductive databases based on the Magic Set approach. As the Magic Sets rewriting may lead to unstratifiable rules, we propose to use Kerisit's weak consequence operator to compute the well-founded model of magic rules (guaranteed to be two-valued). We show that its application in combination with the concept weak stratification, however, may lead to a set of answers which is neither sound nor complete with respect to the well-founded model. This problem is cured by introducing the new concept soft stratification instead.