An Efficient Evaluation Technique for Non-Stratified Programs by Transformation to Explicitly Locally Stratified Programs

David B. Kemp, Kotagiri Ramamohanarao, Peter J. Stuckey

Research output: Contribution to journalArticleResearchpeer-review

1 Citation (Scopus)


We give a simple transformation from normal programs with no stratification (local, weak, modular, etc.) into a subclass of the locally stratified programs, called Explicitly Locally Stratified (ELS) programs, for which there are efficient evaluation techniques. One set of predicates are generated for the true tuples and a different set of predicate are generated for the true and undefined tuples. A similar transformation is given that incorporates a magic sets like transformation. Previous approaches to magic sets transformations of unstratified programs either restricted the class of sips used or generated a program that required special treatment of the magic sets predicates. Our transformation does not suffer from these flaws.

Original languageEnglish
Pages (from-to)191-230
Number of pages40
JournalJournal of Systems Integration
Issue number3-4
Publication statusPublished - 1 Dec 1997
Externally publishedYes


  • Deductive databases
  • Explicitly locally stratified
  • Logic programming
  • Magic sets

Cite this