Stratifikovaný DATALOG

• Př.: Program P(x) :-  Q(x) (1)

• R(1) (2)

• Q(x) :- Q(x),  R(x) (3)

• je stratifikovatelný. Stratifikace: {(2)}  {(3)}  {(1)}

• Program P(x) :-  Q(x)

• Q(x) :-  P(x)

• není stratifikovatelný.

• Df.: Nechť (U,V) je hrana závislostního grafu. (U,V) je positivní (negativní), existuje-li pravidlo V:- … U … a U se tam vyskytuje positivně (negativně).

• Pz.: Hrana může být positivní i negativní.