Accession Number : ADA323766

Title :   Connections in Acyclic Hypergraphs,

Corporate Author : STANFORD UNIV CA

Personal Author(s) : Maier, David ; Ullman, Jeffrey D.

PDF Url : ADA323766

Report Date : MAY 1981

Pagination or Media Count : 14

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.

Descriptors :   *COMPUTER PROGRAMS, *DATA BASES, *GRAPHS, THEORY.

Subject Categories : Computer Programming and Software
      Computer Systems

Distribution Statement : APPROVED FOR PUBLIC RELEASE