Semigroups and transitive closure in deductive databases
Jeffrey David Ullman, Thane Plambeck · 1990
This thesis examines the transitive closure operation and more general linear recursive operations in deductive databases from a semigroup standpoint. An algebraic theory capable of completely characterizing all redundance encountered upon the expansion of linear recursive inference rules in first developed, and then the scope and computational complexity of the theory is studied. In addition, we sharpen and extend earlier results on efficient boundedness testing and more general query containment problems.