Titre du document / Document title

Rule ordering in bottom-up fixpoint evaluation of logic programs

Auteur(s) / Author(s)

RAGHU RAMAKRISHNAN ⁽¹⁾ ; DIVESH SRIVASTAVA ; SUDARSHAN S. ;

Affiliation(s) du ou des auteurs / Author(s) Affiliation(s)

⁽¹⁾ Univ. Wisconsin, computer sci. dep., Madison WI 53706, ETATS-UNIS

Résumé / Abstract

Logic programs can be evaluated bottom-up by repeatedly applying all rules, in «iterations,» until the fixpoint is reached. However, it is often desirable-and, in some cases, e.g., programs with stratified negation, it is even necessary to guarantee the semantics-to apply the rules in some order. We present two algorithms that apply rules in a specified order without repeating inferences. One of them (GSN) is capable of dealing with a wide range of rule orderings, but with a little more overhead than the well-known seminaive algorithm (which we call BSN). The other (PSN) handles a smaller class of rule orderings, but with no overheads beyond those in BSN.. We also demonstrate that by choosing a good ordering, we can reduce the number of rule applications (and thus the number of joins)

Revue / Journal Title

IEEE transactions on knowledge and data engineering   ISSN 1041-4347 

Source / Source

1994, vol. 6, n^o4, pp. 501-517 (26 ref.)

Langue / Language

Anglais

Editeur / Publisher

IEEE Computer Society, New York, NY, ETATS-UNIS  (1989) (Revue)

Mots-clés anglais / English Keywords

Transactional analysis ; Database query ; Logical programming ; Deductive database ; Performance evaluation ; Integration ; Database ; Intelligent system ;

Mots-clés français / French Keywords

Analyse transactionnelle ; Interrogation base donnée ; Programmation logique ; Base donnée déductive ; Evaluation performance ; Intégration ; Base donnée ; Système intelligent ; Bottom up evaluation ; Control expression ; Cyclic ordering ; Query evaluation ; Rule ordering ; Seminaire evaluation ;

Mots-clés espagnols / Spanish Keywords

Análisis transaccional ; Interrogación base datos ; Programación lógica ; Base dato deductiva ; Evaluación prestación ; Integración ; Base dato ; Sistema inteligente ;

Localisation / Location

INIST-CNRS, Cote INIST : 22205, 35400004072014.0010