Efficient reordering of C-PROLOG

ABSTRACT

PROLOG uses a depth-first search of an AND/OR graph to satisfy queries against its database. It searches sequentially through the clauses of a predicate whose head matches the query, trying to satisfy the goals in the clause body in a sequential left-to-right order. The ordering of clauses and goals is a major factor in the efficiency of a PROLOG program. We have developed a profiler for C-PROLOG that collects statistics including the failure rate of clauses and goals in a C-PROLOG program. These statistics are used by any of several reordering predicates capable of local or global reordering. The intent is to construct a reordered PROLOG program that outputs an equivalent set of answers, and is more efficient. Test results are promising.

REFERENCES

• 1: W F. Clocksin , Christopher S. Mellish, Programming in Prolog (2nd ed.), Springer-Verlag New York, Inc., New York, NY, 1984
• 2: Jacques Cohen, A view of the origins and development of Prolog, Communications of the ACM, v.31 n.1, p.26-36, Jan. 1988 [doi>10.1145/35043.35045]
• 3: M. M. Gooley , B. W. Wah, Efficient Reordering of Prolog Programs, IEEE Transactions on Knowledge and Data Engineering, v.1 n.4, p.470-482, December 1989 [doi>10.1109/69.43422]
• 4: Pereira, Fernando and Tweed, Christopher, C- PROLOG User'8 Manual Version 1.5 and 1.5+, SKI International, Menlo Park, CA, 1988.
• 5: F. N. Sibai , K. L. Watson , Mi Lu, A Parallel Unification Machine, IEEE Micro, v.10 n.4, p.21-33, July 1990 [doi>10.1109/40.57728]
• 6: Wang, Jian, E.gicient Reordering in C-Prolog, MS Thesis, Middle Tennessee State University, Murfreesboro, TN, 1992.
• 7: Warren, D.H.D., "Applied Logic- its Use and Implementation as a Programming Tool," Technical Note 290, SRI International, Menlo Park, CA, 1983.

INDEX TERMS

Primary Classification:
  H. Information Systems
  H.2 DATABASE MANAGEMENT
      H.2.3 Languages
          Subjects: Query languages

Additional Classification:
  D. Software
  D.2 SOFTWARE ENGINEERING
      D.2.8 Metrics
          Subjects: Performance measures

  H. Information Systems
  H.2 DATABASE MANAGEMENT
      H.2.3 Languages

          Nouns: Prolog

General Terms:
Algorithms, Design, Languages, Performance