Accession Number : ADA328351
Title : Semigroups and Transitive Closure in Deductive Databases.
Descriptive Note : Doctoral thesis,
Corporate Author : STANFORD UNIV CA DEPT OF COMPUTER SCIENCE
Personal Author(s) : Plambeck, Thane E.
PDF Url : ADA328351
Report Date : AUG 1990
Pagination or Media Count : 136
Abstract : 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 is 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.
Descriptors : *DATA BASES, *DATA MANAGEMENT, COMPUTER COMMUNICATIONS, COMPUTER LOGIC, COMPUTER PROGRAMMING, PROGRAMMING LANGUAGES, LINEAR PROGRAMMING, THESES, RECURSIVE FUNCTIONS, SYSTEMS ANALYSIS, SYNTAX, GROUPS(MATHEMATICS).
Subject Categories : Computer Programming and Software
Distribution Statement : APPROVED FOR PUBLIC RELEASE