Connections in Acyclic Hypergraphs,

Abstract

We demonstrate a sense in which the equivalence between blocks (subgraphs without articulation points) and biconnected components (subgraphs in which there are two edge-disjoint paths between any air of nodes) that holds in ordinary graph theory can be generalized to hypergraphs. The result has an interpretation for relational databases that the universal relations described by acyclic join dependencies are exactly those for which the connections among attributes are defined uniquely. We also exhibit a relationship between the process of Graham reduction of hypergraphs and the process of tableau reduction that holds only for acyclic hypergraphs.

Open PDF

Document Details

Document Type
Technical Report
Publication Date
May 01, 1981
Accession Number
ADA323766

Entities

People

  • David Maier
  • Jeffrey D. Ullman

Organizations

  • Stanford University

Tags

Communities of Interest

  • Materials and Manufacturing Processes

DTIC Thesaurus Topics

  • Air Force
  • Algorithms
  • Commerce
  • Computer Programs
  • Computer Science
  • Computers
  • Databases
  • Graph Theory
  • Law
  • Mathematics
  • Relational Databases
  • Scientific Research
  • Sequences

Readers

  • Database Systems and Applications
  • Graph Algorithms and Convex Optimization.