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

On the Cyclic to Acyclic Scheme Transformation and Solving Cyclic Queries.

Z. Meral Özsoyoglu, Elarbi Choukhmane: On the Cyclic to Acyclic Scheme Transformation and Solving Cyclic Queries. PODS 1984: 133-142
@inproceedings{DBLP:conf/pods/OzsoyogluC84,
  author    = {Z. Meral {\"O}zsoyoglu and
               Elarbi Choukhmane},
  editor    = {Daniel J. Rosenkrantz and
               Ronald Fagin},
  title     = {On the Cyclic to Acyclic Scheme Transformation and Solving Cyclic
               Queries},
  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     = {133-142},
  ee        = {http://doi.acm.org/10.1145/588011.588031, db/conf/pods/OzsoyogluC84.html},
  crossref  = {DBLP:conf/pods/84},
  bibsource = {DBLP, http://dblp.uni-trier.de}
}

Abstract

Relational database schemes can be partitioned into acyclic (tree) schemes and cyclic schemes. This partitioning also classifies the natural join queries into tree queries and cyclic queries. The problems of determining the minimum number of joins needed (i) to transform a cyclic scheme into an acyclic one, and (ii) to solve a cyclic query are shown [GS1 82, GS2 82] to be two different NP-complete problems. We consider a class of database schemes, called simple schemes. We show that the two problems above are equivalent but remain to be NP-complete when they are restricted to simple schemes. We give a polynomial time algorithm for both problems on simple schemes whose qual graphs are chordal. As a by-product, we also show that an edge contraction problem on undirected graphs is NP-complete and it is polynomial when the graph is chordal.

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

[BC 81]
Philip A. Bernstein, Dah-Ming W. Chiu: Using Semi-Joins to Solve Relational Queries. J. ACM 28(1): 25-40(1981) CiteSeerX Google scholar pubzone.org BibTeX bibliographical record in XML
[BE 76]
...
[BFMMUY 81]
Catriel Beeri, Ronald Fagin, David Maier, Alberto O. Mendelzon, Jeffrey D. Ullman, Mihalis Yannakakis: Properties of Acyclic Database Schemes. STOC 1981: 355-362 CiteSeerX Google scholar pubzone.org BibTeX bibliographical record in XML
[BFMY 82]
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
[BG 81]
Philip A. Bernstein, Nathan Goodman: Power of Natural Semijoins. SIAM J. Comput. 10(4): 751-771(1981) CiteSeerX Google scholar pubzone.org BibTeX bibliographical record in XML
[FA 81]
...
[Ga 72]
Fanica Gavril: Algorithms for Minimum Coloring, Maximum Clique, Minimum Covering by Cliques, and Maximum Independent Set of a Chordal Graph. SIAM J. Comput. 1(2): 180-187(1972) CiteSeerX Google scholar pubzone.org BibTeX bibliographical record in XML
[GJ 79]
M. R. Garey, David S. Johnson: Computers and Intractability: A Guide to the Theory of NP-Completeness. W. H. Freeman 1979, ISBN 0-7167-1044-7
CiteSeerX Google scholar pubzone.org BibTeX bibliographical record in XML
[GO 80]
...
[Gr 79]
...
[GS1 82]
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
[GS2 82]
Nathan Goodman, Oded Shmueli: Transforming Cyclic Schemas into Trees. PODS 1982: 49-54 CiteSeerX Google scholar pubzone.org BibTeX bibliographical record in XML
[GST 83]
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
[Sh 81]
...
[Oz 80]
...
[OC 83]
...
[Ul 82]
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
[YO 79]
...

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