Dynamic table woes

Help!
1

I’m busy with part 2 of my Prolog databases tutorial, redoing the Social-Network problems from the Stanford SQL MooC in Prolog.

It’s all gone well until the final problem which involves adding entries to a relation I needed to declare as a table to avoid cycle hangs.

My problem goes as follows:

For all cases where A is friends with B, and B is friends with C, add a new friendship for the pair A and C. Do not add duplicate friendships, friendships that already exist, or friendships with oneself.

My solution looks like so:

findall(friend(A, C),
            (    friend(A, B), friend(B, C),
                 \+friend(A, C), A \== C
            ), L),
forall(member(friend(ID1, ID2), L),
    assertz(friend(ID1, ID2))).

Nothing gets changed in the friend/2 table by running the above. I’m stuck on whether this is due to with faulty logic in my code, or if this is due to the friend/2 relation being tabled.

I added this to the top of the data declarations, but it doesn’t seem to have a difference.

:- table friend/2 as dynamic.
2

Wel, you either want to table friend/2 or you want to compute your own transitive closure using more or less what you are trying. Tabling a fact is not impossible, but useless and just looses memory and makes your program slower. If you compute your own closure you do not need a findall/3, just assert inside your generate and test loop. You do need to continue doing so until nothing is changed. One way to check that is to check the last_modified_generation(Gen) property. If didn’t change during an iteration you are done.

As is, you do need a helper predicate for the tabled version. This is probably the most elegant in current SWI-Prolog (requires the development version):

:- dynamic friend/2 as monotonic.
:- table friended/2 as monotonic.

friended(A,C) :-
    friended(A,B),
    friended(B,C).
friended(A,B) :-
    friend(A,B).

Now you can assert and retract friend/2 facts and enjoy the transitive closure in friended/2. Asserts only compute the new consequences incrementally. A retract recomputes the closure from scratch.

2 Likes
4

Why does the exercise, Stanford SQL MooC, require no self friends?

What this means is that if we want “friends of friends”, you inevitably will be a friend of your friend: mathematically friend(A, B), friend(B, C) will always include C = A unless it’s filtered out.

6

Do you mind to share an example of generating self friended friend/2 ground base ?
Cannot find it by myself, given Jan W. definition…

8

Ok, thanks. I was trying with a ground friend/2…

Now I wander how to debug the following non terminating (half baked) snippet.

:- module(friended,
          [friended/2
          ,friend/2
          ]).

friend(1510, 1381).
friend(1510, 1689).
friend(1689, 1709).
friend(1381, 1247).
friend(1709, 1247).
friend(1689, 1782).
friend(1782, 1468).
friend(1782, 1316).
friend(1782, 1304).
friend(1468, 1101).
friend(1468, 1641).
friend(1101, 1641).
friend(1247, 1911).
friend(1247, 1501).
friend(1911, 1501).
friend(1501, 1934).
friend(1316, 1934).
friend(1934, 1304).
friend(1304, 1661).
friend(1661, 1025).
friend(A, B) :- A\==B, friend(B, A).

:- table friended/2 as monotonic.

friended(A,C) :-
    friended(A,B),
    friended(B,C).
friended(A,B) :-
    friend(A,B).

?- friended(X,Y). doesn’t complete, I understand the clause

friend(A, B) :- A\==B, friend(B, A).

could be the culprit, then maybe (==)/2 should be warned (at runtime) as invalid ?

9

I guess it is the negation that breaks it.

10

The idea of separating the friend/2 facts from the friended/2 rules is to properly deal with a dynamic friend/2 database. If the data is not dynamic, you can simply define friend/2 with both the facts and the rules and table it. If you separate the rules from the facts, move all rules to the friended/2 layer. As is you hav an infinite recursion in a non-tabled predicate.

11

Many thanks for the prompt answer as always @jan.

I got it to work like this

:-  dynamic friended/2.

friended(ID1, ID2) :- friend(ID1, ID2).

friended(ID1, ID3) :-
    friend(ID1, ID2), friend(ID2, ID3),
    \+friend(ID1, ID3), ID1 \== ID3.