ACM SIGMOD Anthology ACM SIGMOD dblp.uni-trier.de

Connections in Acyclic Hypergraphs.

David Maier, Jeffrey D. Ullman: Connections in Acyclic Hypergraphs. PODS 1982: 34-39
@inproceedings{DBLP:conf/pods/MaierU82,
  author    = {David Maier and
               Jeffrey D. Ullman},
  title     = {Connections in Acyclic Hypergraphs},
  booktitle = {Proceedings of the ACM Symposium on Principles of Database Systems,
               March 29-31, 1982, Los Angeles, California},
  publisher = {ACM},
  year      = {1982},
  pages     = {34-39},
  ee        = {http://doi.acm.org/10.1145/588111.588118, db/conf/pods/MaierU82.html},
  crossref  = {DBLP:conf/pods/82},
  bibsource = {DBLP, http://dblp.uni-trier.de}
}

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 pair 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 dependencics arc exactly those for which the connections among attributes are defined uniquely. We also exhibit a relationship between the process of Graham reduction [6] of hypergraphs and the process of tableau reduction [1] that holds only for acyclic hypergraphs.

Copyright © 1982 by the ACM, Inc., used by permission. Permission to make digital or hard copies is granted provided that copies are not made or distributed for profit or direct commercial advantage, and that copies show this notice on the first page or initial screen of a display along with the full citation.


Load The ACM SIGMOD Anthology, CDROM Edition, Volume 1-3, PODS '82-'98. and ... Load The ACM SIGMOD Anthology, Silver Edition, DVD 1, Proceedings. and ...

Printed Edition

Proceedings of the ACM Symposium on Principles of Database Systems, March 29-31, 1982, Los Angeles, California. ACM 1982
Contents CiteSeerX Google scholar pubzone.org BibTeX bibliographical record in XML

Online Edition: ACM Digital Library


References

[1]
Alfred V. Aho, Yehoshua Sagiv, Jeffrey D. Ullman: Equivalences Among Relational Expressions. SIAM J. Comput. 8(2): 218-246(1979) CiteSeerX Google scholar pubzone.org BibTeX bibliographical record in XML
[2]
...
[3]
...
[4]
...
[5]
Ronald Fagin, Alberto O. Mendelzon, Jeffrey D. Ullman: A Simplified Universal Relation Assumption and Its Properties. ACM Trans. Database Syst. 7(3): 343-360(1982) CiteSeerX Google scholar pubzone.org BibTeX bibliographical record in XML
[6]
...
[7]
David Maier, Jeffrey D. Ullman: Maximal Objects and the Semantics of Universal Relation Databases. ACM Trans. Database Syst. 8(1): 1-14(1983) CiteSeerX Google scholar pubzone.org BibTeX bibliographical record in XML
[8]
...
[9]
...

Copyright © Mon Mar 15 03:51:31 2010 by Michael Ley (ley@uni-trier.de)