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

Decomposing an N-ary Relation into a Tree of Binary Relations.

Rina Dechter: Decomposing an N-ary Relation into a Tree of Binary Relations. PODS 1987: 185-189
@inproceedings{DBLP:conf/pods/Dechter87,
  author    = {Rina Dechter},
  title     = {Decomposing an N-ary Relation into a Tree of Binary Relations},
  booktitle = {Proceedings of the Sixth ACM SIGACT-SIGMOD-SIGART Symposium on
               Principles of Database Systems, March 23-25, 1987, San Diego,
               California},
  publisher = {ACM},
  year      = {1987},
  isbn      = {0-89791-223-3},
  pages     = {185-189},
  ee        = {http://doi.acm.org/10.1145/28659.28679, db/conf/pods/Dechter87.html},
  crossref  = {DBLP:conf/pods/87},
  bibsource = {DBLP, http://dblp.uni-trier.de}
}
BibTeX

Abstract

We present an efficient algorithm for decomposing an n-ary relation into a tree of binary relations, and provide an efficient test for checking whether or not the tree formed represents the relation. If there exists a tree-decomposition, the algorithm is guaranteed to find one, otherwise, the tree generated will fail the test, then indicating that no tree decomposition exist. The unique features of the algorithm presented in this paper, is that it does not apriori assume any dependencies in the initial relation, rather it derives such dependencies from the bare relation instance.

Copyright © 1987 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 ... BibTeX

Printed Edition

Proceedings of the Sixth ACM SIGACT-SIGMOD-SIGART Symposium on Principles of Database Systems, March 23-25, 1987, San Diego, California. ACM 1987, ISBN 0-89791-223-3
Contents BibTeX

Online Edition: ACM Digital Library

Journal Version

Rina Dechter: Decomposing a Relation into a Tree of Binary Relations. J. Comput. Syst. Sci. 41(1): 2-24(1990) BibTeX

References

[1]
...
[2]
Rina Dechter, Judea Pearl: The Anatomy of Easy Problems: A Constraint-Satisfaction Formulation. IJCAI 1985: 1066-1072 BibTeX
[3]
Jon Doyle: A Truth Maintenance System. Artif. Intell. 12(3): 231-272(1979) BibTeX
[4]
Eugene C. Freuder: A Sufficient Condition for Backtrack-Free Search. J. ACM 29(1): 24-32(1982) BibTeX
[5]
...
[6]
David Maier: The Theory of Relational Databases. Computer Science Press 1983, ISBN 0-914894-42-0
Contents BibTeX
[7]
...

Referenced by

  1. Jyrki Kivinen, Heikki Mannila: Approximate Dependency Inference from Relations. ICDT 1992: 86-98
  2. Heikki Mannila, Kari-Jouko Räihä: Dependency Inference. VLDB 1987: 155-158
BibTeX
ACM SIGMOD Anthology - DBLP: [Home | Search: Author, Title | Conferences | Journals]
ACM SIGMOD Anthology: Copyright © by ACM (info@acm.org), Corrections: anthology@acm.org
DBLP: Copyright © by Michael Ley (ley@uni-trier.de), last change: Sat May 16 23:33:51 2009