dblp.uni-trier.de www.dagstuhl.de www.uni-trier.de

On the Recognition and Design of Acyclic Databases.

Alessandro D'Atri, Marina Moscarini: On the Recognition and Design of Acyclic Databases. PODS 1984: 1-8
@inproceedings{DBLP:conf/pods/DAtriM84,
  author    = {Alessandro D'Atri and
               Marina Moscarini},
  editor    = {Daniel J. Rosenkrantz and
               Ronald Fagin},
  title     = {On the Recognition and Design of Acyclic Databases},
  booktitle = {Proceedings of the Third ACM SIGACT-SIGMOD Symposium on Principles
               of Database Systems, April 2-4, 1984, Waterloo, Ontario, Canada},
  publisher = {ACM},
  year      = {1984},
  isbn      = {0-89791-128-8},
  pages     = {1-8},
  ee        = {http://doi.acm.org/10.1145/588011.588013, db/conf/pods/DAtriM84.html},
  crossref  = {DBLP:conf/pods/84},
  bibsource = {DBLP, http://dblp.uni-trier.de}
}

Abstract

The acyclicity degree of a relational database scheme is an interesting topic due to several desirable properties of the corresponding database [5,16]. In this paper a simple and homogeneous way to characterize the acyclicity degree of a database scheme is given. The method is based on the existence in all acyclic database schemes of a nonempty set of relation schemes that satisfy a "pruning predicate", which is a property similar to the property satisfied by the leaves in an ordinary tree. This fact implies that such relation schemes may be eliminated using a recursive pruning algorithm in order to determine the acyclicity degree. Furthermore, if we use an incremental step by step design methodology, enriching the scheme one relation at a time, the pruning predicate suggests a set of properties that have to be verified by the new relation scheme in order to preserve the acyclicity degree of the database scheme.

Copyright © 1984 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

Daniel J. Rosenkrantz, Ronald Fagin (Eds.): Proceedings of the Third ACM SIGACT-SIGMOD Symposium on Principles of Database Systems, April 2-4, 1984, Waterloo, Ontario, Canada. ACM 1984, ISBN 0-89791-128-8
Contents CiteSeerX Google scholar pubzone.org BibTeX bibliographical record in XML

Online Edition: ACM Digital Library


References

[1]
...
[2]
...
[3]
...
[4]
Catriel Beeri, Philip A. Bernstein, Nathan Goodman: A Sophisticate's Introduction to Database Normalization Theory. VLDB 1978: 113-124 CiteSeerX Google scholar pubzone.org BibTeX bibliographical record in XML
[5]
Catriel Beeri, Ronald Fagin, David Maier, Mihalis Yannakakis: On the Desirability of Acyclic Database Schemes. J. ACM 30(3): 479-513(1983) CiteSeerX Google scholar pubzone.org BibTeX bibliographical record in XML
[6]
Catriel Beeri, Michael Kifer: Elimination of Intersection Anomalies from Database Schemes. PODS 1983: 340-351 CiteSeerX Google scholar pubzone.org BibTeX bibliographical record in XML
[7]
...
[8]
...
[9]
E. F. Codd: A Relational Model of Data for Large Shared Data Banks. Commun. ACM 13(6): 377-387(1970) CiteSeerX Google scholar pubzone.org BibTeX bibliographical record in XML
[10]
...
[11]
...
[12]
Alessandro D'Atri, Marina Moscarini, Nicolas Spyratos: Answering Queries in Relational Databases. SIGMOD Conference 1983: 173-177 CiteSeerX Google scholar pubzone.org BibTeX bibliographical record in XML
[13]
Ronald Fagin: A Normal Form for Relational Databases That Is Based on Domians and Keys. ACM Trans. Database Syst. 6(3): 387-415(1981) CiteSeerX Google scholar pubzone.org BibTeX bibliographical record in XML
[14]
Ronald Fagin: Acyclic Database Schemes (of Various Degrees): A Painless Introduction. CAAP 1983: 65-89 CiteSeerX Google scholar pubzone.org BibTeX bibliographical record in XML
[15]
Ronald Fagin: Degrees of Acyclicity for Hypergraphs and Relational Database Schemes. J. ACM 30(3): 514-550(1983) CiteSeerX Google scholar pubzone.org BibTeX bibliographical record in XML
[16]
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
[17]
Nathan Goodman, Oded Shmueli: The Tree Property is Fundamental for Query Processing. PODS 1982: 40-48 CiteSeerX Google scholar pubzone.org BibTeX bibliographical record in XML
[18]
Nathan Goodman, Oded Shmueli: Transforming Cyclic Schemas into Trees. PODS 1982: 49-54 CiteSeerX Google scholar pubzone.org BibTeX bibliographical record in XML
[19]
Nathan Goodman, Oded Shmueli, Y. C. Tay: GYO Reductions, Canonical Connections, Tree and Cyclic Schemas and Tree Projections. PODS 1983: 267-278 CiteSeerX Google scholar pubzone.org BibTeX bibliographical record in XML
[20]
...
[21]
...
[22]
...
[23]
Kent Laver, Alberto O. Mendelzon, Marc H. Graham: Functional Dependencies on Cyclic Database Schemes. SIGMOD Conference 1983: 79-91 CiteSeerX Google scholar pubzone.org BibTeX bibliographical record in XML
[24]
Y. Edmund Lien: On the Equivalence of Database Models. J. ACM 29(2): 333-362(1982) CiteSeerX Google scholar pubzone.org BibTeX bibliographical record in XML
[25]
David Maier: The Theory of Relational Databases. Computer Science Press 1983, ISBN 0-914894-42-0
Contents CiteSeerX Google scholar pubzone.org BibTeX bibliographical record in XML
[26]
...
[27]
Domenico Saccà: On the Recognition of Coverings of Acyclic Database Hypergraphs. PODS 1983: 297-304 CiteSeerX Google scholar pubzone.org BibTeX bibliographical record in XML
[28]
Jeffrey D. Ullman: Principles of Database Systems, 2nd Edition. Computer Science Press 1982, ISBN 0-914894-36-6
CiteSeerX Google scholar pubzone.org BibTeX bibliographical record in XML
[29]
Mihalis Yannakakis: Algorithms for Acyclic Database Schemes. VLDB 1981: 82-94 CiteSeerX Google scholar pubzone.org BibTeX bibliographical record in XML
[30]
...

Last update Fri Sep 14 17:28:24 2012 CET by the DBLP TeamThis material is Open Data Data released under the ODC-BY 1.0 license — See also our legal information page