A bottom-up query evaluation method for stratified databases

A labeling algorithm for stratified databases is presented. The algorithm that is performed prior to the magic-set algorithm can be used to distinguish the context for constructing magic sets. It is shown that the culprit cycles cause the destratification of a database. Based on this analysis, three subprocedures are developed to remove the different kinds of culprit cycles. The negnumber procedure numbers the different occurrences of a negative literal in a rule. The dynlabel procedure gives each negative body literal a dynamic subscript when it appears in a recursive rule. The label procedure labels each body literal p when there exists a sequence of paths connecting it to a negative body literal-q in the same rule, or a sequence of paths with at least one path being negative connecting it to a positive body literal q in the same rule and there is an arc of the form N→r in the sideways information-passing strategy (SIPS) such that q∈N and p=r