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

A Query Language and Optimization Techniques for Unstructured Data.

Peter Buneman, Susan B. Davidson, Gerd G. Hillebrand, Dan Suciu: A Query Language and Optimization Techniques for Unstructured Data. SIGMOD Conference 1996: 505-516
@inproceedings{DBLP:conf/sigmod/BunemanDHS96,
  author    = {Peter Buneman and
               Susan B. Davidson and
               Gerd G. Hillebrand and
               Dan Suciu},
  editor    = {H. V. Jagadish and
               Inderpal Singh Mumick},
  title     = {A Query Language and Optimization Techniques for Unstructured
               Data},
  booktitle = {Proceedings of the 1996 ACM SIGMOD International Conference on
               Management of Data, Montreal, Quebec, Canada, June 4-6, 1996},
  publisher = {ACM Press},
  year      = {1996},
  pages     = {505-516},
  ee        = {http://doi.acm.org/10.1145/233269.233368, db/conf/sigmod/BunemanDHS96.html},
  crossref  = {DBLP:conf/sigmod/96},
  bibsource = {DBLP, http://dblp.uni-trier.de}
}

Abstract

A New kind of data model has recently emerged in which the database is not constrained by a conventional schema. Systems like ACeDB, which has become very popular with biologists, and the recent Tsimmis proposal for data integration organize data in tree-like structures whose components can be used equally well to represent sets and tuples. Such structures allow great flexibility in data representation.

What query language is appropriate for such structures? Here we propose a simple language UnQL for querying data organized as a rooted, edge-labeled graph. In this model, relational data may be represented as fixed-depth trees, and on such trees UnQL is equivalent to the relational algebra. The novelty of UnQL is consists in its programming constructs for arbitrarly deep data and for cyclic structures. While strictly more powerful than query languages with path expressions like XSQL, UnQL can still be efficiently evaluated. We describe new optimization techniques for the deep or "vertical" dimension of UnQL queries. Furthermore, we show that known optimization techniques for operators on flat relations apply to the "horizontal" dimension on UnQL.

Copyright © 1996 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.


ACM SIGMOD Anthology

Online Version (ACM WWW Account required): Full Text in PDF Format

CDROM Version: Load the CDROM "Volume 1 Issue 1, SIGMOD '93-'97" and ...

DVD Version: Load ACM SIGMOD Anthology DVD 1" and ...

Printed Edition

H. V. Jagadish, Inderpal Singh Mumick (Eds.): Proceedings of the 1996 ACM SIGMOD International Conference on Management of Data, Montreal, Quebec, Canada, June 4-6, 1996. ACM Press 1996 CiteSeerX Google scholar pubzone.org BibTeX bibliographical record in XML, SIGMOD Record 25(2), June 1996
Contents

Online Edition: ACM Digital Library

[Index Terms]
[Full Text in PDF Format, 1158 KB]

References

[BBW92]
Val Tannen, Peter Buneman, Limsoon Wong: Naturally Embedded Query Languages. ICDT 1992: 140-154 CiteSeerX Google scholar pubzone.org BibTeX bibliographical record in XML
[BDH+95]
Peter Buneman, Susan B. Davidson, Kyle Hart, G. Christian Overton, Limsoon Wong: A Data Transformation System for Biological Data Sources. VLDB 1995: 158-169 CiteSeerX Google scholar pubzone.org BibTeX bibliographical record in XML
[BDHS96]
...
[BDS94]
...
[BLS+94]
Peter Buneman, Leonid Libkin, Dan Suciu, Val Tannen, Limsoon Wong: Comprehension Syntax. SIGMOD Record 23(1): 87-96(1994) CiteSeerX Google scholar pubzone.org BibTeX bibliographical record in XML
[BTS91]
Val Tannen, Ramesh Subrahmanyam: Logical and Computational Aspects of Programming with Sets/Bags/Lists. ICALP 1991: 60-75 CiteSeerX Google scholar pubzone.org BibTeX bibliographical record in XML
[CM90]
Mariano P. Consens, Alberto O. Mendelzon: GraphLog: a Visual Formalism for Real Life Recursion. PODS 1990: 404-416 CiteSeerX Google scholar pubzone.org BibTeX bibliographical record in XML
[GP84]
...
[GRS93]
...
[KKS92]
Michael Kifer, Won Kim, Yehoshua Sagiv: Querying Object-Oriented Databases. SIGMOD Conference 1992: 393-402 CiteSeerX Google scholar pubzone.org BibTeX bibliographical record in XML
[KL89]
Michael Kifer, Georg Lausen: F-Logic: A Higher-Order language for Reasoning about Objects, Inheritance, and Scheme. SIGMOD Conference 1989: 134-146 CiteSeerX Google scholar pubzone.org BibTeX bibliographical record in XML
[Kos95]
...
[Mil89]
...
[PGMW95]
Yannis Papakonstantinou, Hector Garcia-Molina, Jennifer Widom: Object Exchange Across Heterogeneous Information Sources. ICDE 1995: 251-260 CiteSeerX Google scholar pubzone.org BibTeX bibliographical record in XML
[TMD92]
...
[Won94]
Limsoon Wong: Querying Nested Collections. Ph.D. thesis, Univ. Pennsylvania 1994
CiteSeerX Google scholar pubzone.org BibTeX bibliographical record in XML

Copyright © Sun Mar 14 23:25:46 2010 by Michael Ley (ley@uni-trier.de)