Semigroups and Transitive Closure in Deductive Databases.

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.

Open PDF

Document Details

Document Type
Technical Report
Publication Date
Aug 01, 1990
Accession Number
ADA328351

Entities

People

  • Thane E. Plambeck

Organizations

  • Stanford University

Tags

Communities of Interest

  • C4I
  • Energy and Power Technologies

DTIC Thesaurus Topics

  • Algorithms
  • Alphabets
  • Case Studies
  • Computational Complexity
  • Computations
  • Computer Programming
  • Computer Programs
  • Computer Science
  • Computers
  • Context Free Grammars
  • Databases
  • Language
  • New York
  • Numbers
  • Programming Languages
  • Relational Databases
  • Theses

Fields of Study

  • Mathematics

Readers

  • Artificial Intelligence
  • Finite Element Method (FEM) for solving Partial Differential Equations (PDEs)
  • Systems Analysis and Design

Technology Areas

  • AI & ML
  • AI & ML - Autonomous Systems
  • AI & ML - Machine Learning Algorithms