Contents

• Contents
• An Introduction to PROLOG Indexing
  • PROLOG and its Compilation into the WAM
  • Compiling a Single Clause
  • Combining Multiple Clauses Into a Procedure
  • Standard PROLOG Indexing
  • Motivation for Extensions of the Standard PROLOG Indexing
• DAXes: Indexing Information Represented in Specialized DAGs
  • Clauses and Fails
  • Choice Points
  • Index Instructions
  • Combining the DAX Components
    • less
    • f
• Extensions of the Standard PROLOG Indexing
  • Looking at Other Approaches
    • Hardware Oriented Approaches
      • m-in-n-Coding
    • Software Oriented Approaches
      • Complete Indexing
    • Index Assistant Functions
      • Shallow Backtracking
      • Quadratic Indexing
  • Our Approach
    • Using Arguments Other Than the First (1N)
    • Using More Than One Argument (MBN, MDN, and MN)
      • Breadth Oriented (MBN)
      • Depth Oriented (MDN)
      • Breadth and Depth Oriented (MN)
    • Allowing Variables in Index Blocks (1V and MV)
      • The 1V-Algorithm
      • The Final Result: The MV-Algorithm
  • Future Extensions
    • Using Additional Information
    • Assert
    • Compiling Higher Order PROLOG Extensions
• Indexing in RELFUN
  • The RELFUN Implementation Structure
  • Compilation Phases
    • A Classifier with Indexing Heuristics
    • A Code Generator with Indexing Heuristics
  • Summary: Heuristic Classification
• Appendix
• User Commands
• Sample Session
• Benchmarks
  • Benchmark Results
  • Benchmark Sources
    • nrev Benchmark
    • dnf Benchmark
    • NET Benchmark
• Implementation of the Heuristics
• References
• About this document ...