% XY-stratification % Ancestors of Marc and the generation gap. % Chap 10.4, Advanced Database Systems, C. Zaniolo et al. % % Schema %------- database({parent(string, string), g(X:string, Y:string, C:integer)}). %Derivated predicates and rules %------------------------------ export delta_anc(A, B). delta_anc(0, marc). delta_anc(J+1, Y) <- delta_anc(J, X), parent(Y, X), ~all_anc(J, Y, _). all_anc(J+1, X, Y) <- all_anc(J, X, Y). all_anc(J, X, X) <- delta_anc(J, X). % XY Example 2. Floyd's Algorithm % "Negation and Aggregates in Recursive Rules: the LDL++ Approach", DOOD 93. export delta(I, X, Y, C). delta(0, X, X, 0) <- g(X,_,_). delta(0, Y, Y, 0) <- g(_,Y,_). delta(J+1, X, Z, min) <- delta(J,X,Y,C1), g(Y,Z,C2), C=C1+C2, if (all(J,X,Z,C3) then C3>C). all(J+1, X, Z, C) <- all(J, X, Z, C), ~delta(J+1, X, Z, _). all(J, X, Z, C) <- delta(J, X, Z, C).