Normal Forms and Syntactic Completeness Proofs for Functional Independencies

Abstract

We prove normal form theorems of a complete axiom system for the inference of functional dependencies and independencies in relational databases. We also show that all proofs in our system have a normal form where the application of independency rules is limited to three levels. Our normal form results in a faster proof search engine in deriving consequences of functional independencies. As a result, we get a new construction of an Armstrong relation for a given set of functional dependencies. It is also shown that an Armstrong relation for a set of functional dependencies and independencies do not exist in general, and this generalizes the same result valid under the closed world assumption.

Open PDF

Document Details

Document Type
Technical Report
Publication Date
Nov 01, 1998
Accession Number
ADA364422

Entities

People

  • A. Nerode
  • D. Wijesekera
  • J. Srivastava
  • M. Ganesh

Organizations

  • University of California, Berkeley

Tags

Communities of Interest

  • C4I

DTIC Thesaurus Topics

  • Algorithms
  • Applied Mathematics
  • Artificial Intelligence
  • Computer Science
  • Computers
  • Consistency
  • Construction
  • Data Mining
  • Databases
  • Inference Engines
  • Language
  • Logic
  • Mathematics
  • Relational Databases
  • Sequences
  • Standards
  • Theorems

Fields of Study

  • Computer science

Readers

  • Artificial Intelligence
  • Statistical inference.

Technology Areas

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