Imposing an order to facts in Prolog

5
votes

Suppose that f(X) is a dynamic fact that can be asserted and retracted, and suppose that X is always number. Now, suppose that the most executed query is about finding the f(X) such that is minimum. In SWI-Prolog I may write:

min_f(R) :- aggregate(min(X), f(X), R).

But, apparently, this always causes Prolog to perform a linear search on all facts. Now, suppose that there will be a large number (e.g. 1,000,000) of such facts. Since I know before hand that I will often execute min_f/1:

  • can I impose an ordering on f/1, so that the engine can find the minimum in O(1) ?
  • I may explicitly assert a min-heap containing all the facts, and then peek at the head; could the facts be stored in a min-heap implicitly ?

I have no restriction on the Prolog dialect, so any alternative Prolog implementation would be fine.

2
prolog
I recommend you simply use library(heaps), available in SICStus, SWI etc. Maintain an explicit heap that you thread through, and you will always have O(1) access to the minimum. It also simplifies debugging and reasoning about your code, since you do not depend on side effects and implicit states as would be the case if you modify the global database. Also, it is in all likelihood faster. - mat
I second the recommendation by @mat. A logical variable is usually much cleaner method for maintaining state than using the database together with assert and retract. For your use case, library(heaps) seems to be a good match. Even just keeping a sorted list of values (with or without duplicates) might be an acceptable choice: accessing the head is constant time, even thought insertion is not. - user1812457
I'm playing with SWI-Prolog heaps right now. Apparently, it makes the interpreter segfault when it becomes large enough (~100.000 entries) - Edoardo Vacchi
If you really get a segfault, please file an issue on the development version. If you only get a global stackoverflow, you can increase the global stack size with, for example -G2G to set the global stack limit to 2GB on the command line (this needs at least a 64-bit architecture). - mat
A quick test: ?- length(_, Exp), N is 2^Exp, length(Ls, N), numlist(1, N, Ps), pairs_keys_values(Pairs, Ps, _), list_to_heap(Pairs, H). With default SWI settings on a 64bit system (using ~270MB global stack), this goes up to 2^20, thus creating a heap with more than 1 million elements without problems. Of course, you may need more space depending on the concrete structure of your heap elements. You may also be able to "outsource" at least parts of them to the global database for fast lookup. Still, it's nice to have the heap available as an explicit argument, easing tests etc. - mat

2 Answers

1
votes

An alternative to data structures that can quickly deliver a minimum or maximum, would be to use mode directed tabling. In mode directed tabling one can specify desired aggregate functions:

f(5).
f(4).
f(6).

:- table min_f(min).
min_f(X) :- f(X).

The minimum will be only computed once, here is an example query. Works in SWI-Prolog and since release 1.4.0 also in Jekejeke Prolog:

?- min_f(X).
X = 4.

Theoretically it is left to the tabling implementation, how it calculates min. There are currently also developments going on, incremental tabling, which would allow making f/1 dynamic and then track changes.

0
votes
:- dynamic(f/1).

min_f(X) :-
    f(X),
    !.
assert_f(X) :- 
    min_f(Min),
    Min<X,
    assertz(f(X)),
    !.
assert_f(X) :-
    asserta(f(X)).

Use assert_f/1 instead of assert/1. First solution to f/1 will allways be the minimun value, but don't assume that solutions to f/1 are listed low to high.