This paper discusses the design and implementation of a set-oriented logic
programming paradigm, called subset-logic programming. Subset-logic program
s are built up of three kinds of program clauses: subset, equational and re
lational clauses. Using these clauses, we can program solutions to a broad
range of problems of interest in logic programming and deductive databases.
In previous research, we developed the implementation of subset and equati
onal program clauses. This paper substantially extends that work, and focus
es on the more expressive paradigm of subset and relational clauses. This p
aradigm supports setof operations, transitive closures, monotonic aggregati
on as well as incremental and lazy enumeration of sets. Although the subset
-logic paradigm differs substantially from that of Prolog, we show that few
additional changes are needed to the Warren Abstract Machine (WAM) to impl
ement the paradigm and that these changes blend well with the overall machi
nery of the WAM. A central feature in the implementation of subset-logic pr
ograms is that of a monotonic memo-table, i.e., a memo-table whose entries
can monotonically grow or shrink in an appropriate partial order. We presen
t in stages the paradigm of subset-logic progams, showing the effect of eac
h feature on the implementation. The implementation has been completed, and
we present performance figures to show the efficiency and costs of memoiza
tion. Our conclusion is that the monotonic memo-tables are a practical tool
for implementing a set-oriented logic programming language. We also compar
e this system with other closely related systems, especially XSB and CORAL.
(C) 2000 Elsevier Science Inc. All rights reserved.