bottom-up method for processing recursive sets of rules
The paper proposes a semi-naive method for processing recursive loops in the dependency graph for a given query. The process goes through two phases. During the expand phase answers are generated using translation to base conjunctions. Entries in recursive predicates with undistinguished arguments are also stored in the database for further processing. During the shrink phase the occurrences of recursive predicates in rule-bodies are replaced with the answers already generated during the expand phase. Thus, the whole rule-body becomes a base conjunction, which generates new answers. The proposed method is suitable for queries with bound arguments, it reduces unnecessary computations and generates only facts relevant to the given query.
knowledge-based systems deductive databases logic programming algorithms