EFFICIENT BOTTOM-UP COMPUTATION OF QUERIES ON STRATIFIED DATABASES

Magic-set transformations on (function-free) deductive databases that contain only positive body literals permit the efficient bottom-up evaluation of answers to a wide class of queries. We investigate the applicability of magic sets to stratified and allowed databases containing negative body literals. We introduce a new, less restrictive definition of allowedness. We then present an algorithm that performs a magic-set-based transformation on an initially stratified and allowed database. The answers to a query on the transformed database are evaluated using a structured bottom-up computation which retains the efficiency of the magic-set approach. The set of answers is then proved sound and complete with respect to the perfect model.