ELS-programs and the efficient evaluation of non-stratified programs by transformation to ELS

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

Research output: Chapter in Book/Report/Conference proceedingConference PaperResearchpeer-review

9 Citations (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
Title of host publicationDeductive and Object-Oriented Databases - 4th International Conference, DOOD 1995, Proceedings
EditorsLaurent Vieille, Alberto O. Mendelzon, Tok Wang Ling
Number of pages18
ISBN (Print)9783540606086
Publication statusPublished - 1 Jan 1995
Externally publishedYes
Event4th International Conference on Deductive and Object-Oriented Databases, DOOD 1995 - Singapore, Singapore
Duration: 4 Dec 19957 Dec 1995

Publication series

NameLecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics)
ISSN (Print)0302-9743
ISSN (Electronic)1611-3349


Conference4th International Conference on Deductive and Object-Oriented Databases, DOOD 1995

Cite this