Duplicate-Free Evaluation of Single-Variable Fixpoints of Relational Operations
Original Publication Date: 1988-Jun-01
Included in the Prior Art Database: 2005-Feb-15
A technique is described whereby the least fixpoint of a function of relational database operations is calculated without duplicate processing. It is primarily applicable in cases involving a large class of recursive logic queries where an equation has one fixpoint variable and the relation corresponding to the variable does not appear in a join expression more than once. The concept is an improvement over the straightforward application of Tarski's procedure in that it avoids duplicate computation. Single-variable fixpoints are considered important because a large class of queries can be represented using equations having one variable. This class of queries typically encompasses expressions in function-free "Horn-clause" logic having recursions, if any, that involve only the goal asked as the Query Goal.