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