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
Distribution Statement : APPROVED FOR PUBLIC RELEASE