A Query Language and Optimization Techniques for Unstructured Data.

@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

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

• Windows: Click the letter of your CD drive
  A B C D E F G H I J K L M N O P Q R S T U V W X Y Z
• Mac: Click here
• UNIX/LINUX: mount the CD and click on the path of your mount point:
  /Anthology/smod9397 or /cdrom

• Windows: Click the letter of your CD drive
  A B C D E F G H I J K L M N O P Q R S T U V W X Y Z
• Mac: Click here
• UNIX/LINUX: mount the DVD and click on the path of your mount point:
  /Anthology/aDVD1 or /dvd

Printed Edition

Online Edition: ACM Digital Library

References

[BBW92]

Val Tannen, Peter Buneman, Limsoon Wong: Naturally Embedded Query Languages. ICDT 1992: 140-154 BibTeX

[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 BibTeX

[BDHS96]

...

[BDS94]

...

[BLS+94]

Peter Buneman, Leonid Libkin, Dan Suciu, Val Tannen, Limsoon Wong: Comprehension Syntax. SIGMOD Record 23(1): 87-96(1994) BibTeX

[BTS91]

Val Tannen, Ramesh Subrahmanyam: Logical and Computational Aspects of Programming with Sets/Bags/Lists. ICALP 1991: 60-75 BibTeX

[CM90]

Mariano P. Consens, Alberto O. Mendelzon: GraphLog: a Visual Formalism for Real Life Recursion. PODS 1990: 404-416 BibTeX

[GP84]

...

[GRS93]

...

[KKS92]

Michael Kifer, Won Kim, Yehoshua Sagiv: Querying Object-Oriented Databases. SIGMOD Conference 1992: 393-402 BibTeX

[KL89]

Michael Kifer, Georg Lausen: F-Logic: A Higher-Order language for Reasoning about Objects, Inheritance, and Scheme. SIGMOD Conference 1989: 134-146 BibTeX

[Kos95]

...

[Mil89]

...

[PGMW95]

Yannis Papakonstantinou, Hector Garcia-Molina, Jennifer Widom: Object Exchange Across Heterogeneous Information Sources. ICDE 1995: 251-260 BibTeX

[TMD92]

...

[Won94]

Limsoon Wong: Querying Nested Collections. Ph.D. thesis, Univ. Pennsylvania 1994
BibTeX

Referenced by

1. Peter Buneman, Sanjeev Khanna, Wang Chiew Tan: Why and Where: A Characterization of Data Provenance. ICDT 2001: 316-330
2. Mehmet Altinel, Michael J. Franklin: Efficient Filtering of XML Documents for Selective Dissemination of Information. VLDB 2000: 53-64
3. Moshe Y. Vardi: Constraint Satisfaction and Database Theory: a Tutorial. PODS 2000: 76-85
4. Yannis Papakonstantinou, Victor Vianu: DTD Inference for Views of XML Data. PODS 2000: 35-46
5. Frank Neven, Thomas Schwentick: Expressive and Efficient Pattern Languages for Tree-Structured Data. PODS 2000: 145-156
6. Tova Milo, Dan Suciu, Victor Vianu: Typechecking for XML Transformers. PODS 2000: 11-22
7. Hasan Davulcu, Guizhen Yang, Michael Kifer, I. V. Ramakrishnan: Computational Aspects of Resilient Data Extraction from Semistructured Sources. PODS 2000: 136-144
8. Diego Calvanese, Giuseppe De Giacomo, Maurizio Lenzerini, Moshe Y. Vardi: View-Based Query Processing for Regular Path Queries with Inverse. PODS 2000: 58-66
9. Qiu Yue Wang, Jeffrey Xu Yu, Kam-Fai Wong: Approximate Graph Schema Extraction for Semi-Structured Data. EDBT 2000: 302-316
10. Mengchi Liu, Tok Wang Ling: A Data Model for Semistructured Data with Partial and Inconsistent Information. EDBT 2000: 317-331
11. Sergio Flesca, Sergio Greco: Querying Graph Databases. EDBT 2000: 510-524
12. Serge Abiteboul: On Views and XML. SIGMOD Record 28(4): 30-38(1999)
13. Alin Deutsch, Mary F. Fernández, Daniela Florescu, Alon Y. Levy, David Maier, Dan Suciu: Querying XML Data. IEEE Data Eng. Bull. 22(3): 10-18(1999)
14. Serge Abiteboul, Sophie Cluet, Tova Milo, Pini Mogilevsky, Jérôme Siméon, Sagit Zohar: Tools for Data Translation and Integration. IEEE Data Eng. Bull. 22(1): 3-8(1999)
15. David Mattox, Leonard J. Seligman, Kenneth Smith: Rapper: A Wrapper Generator with Linguistic Knowledge. Workshop on Web Information and Data Management 1999: 6-11
16. Uwe Hohenstein, Andreas Ebert: Automatic Migration of Files into Relational Databases. Workshop on Web Information and Data Management 1999: 17-21
17. Jayavel Shanmugasundaram, Kristin Tufte, Chun Zhang, Gang He, David J. DeWitt, Jeffrey F. Naughton: Relational Databases for Querying XML Documents: Limitations and Opportunities. VLDB 1999: 302-314
18. Jason McHugh, Jennifer Widom: Query Optimization for XML. VLDB 1999: 315-326
19. Curtis E. Dyreson, Michael H. Böhlen, Christian S. Jensen: Capturing and Querying Multiple Aspects of Semistructured Data. VLDB 1999: 290-301
20. Yannis Papakonstantinou, Vasilis Vassalos: Query Rewriting for Semistructured Data. SIGMOD Conference 1999: 455-466
21. H. V. Jagadish, Laks V. S. Lakshmanan, Tova Milo, Divesh Srivastava, Dimitra Vista: Querying Network Directories. SIGMOD Conference 1999: 133-144
22. Alin Deutsch, Mary F. Fernández, Dan Suciu: Storing Semistructured Data with STORED. SIGMOD Conference 1999: 431-442
23. Tova Milo, Dan Suciu: Type Inference for Queries on Semistructured Data. PODS 1999: 215-226
24. Yaron Kanza, Werner Nutt, Yehoshua Sagiv: Queries with Incomplete Answers over Semistructured Data. PODS 1999: 227-236
25. Sophie Cluet, Olga Kapitskaia, Divesh Srivastava: Using LDAP Directory Caches. PODS 1999: 273-284
26. Diego Calvanese, Giuseppe De Giacomo, Maurizio Lenzerini, Moshe Y. Vardi: Rewriting of Regular Expressions and Regular Path Queries. PODS 1999: 194-204
27. Jan Van den Bussche, Emmanuel Waller: Type Inference in the Polymorphic Relational Algebra. PODS 1999: 80-90
28. Serge Abiteboul: On Views and XML. PODS 1999: 1-9
29. Tova Milo, Dan Suciu: Index Structures for Path Expressions. ICDT 1999: 277-295
30. Catriel Beeri, Tova Milo: Schemas for Integration and Translation of Structured and Semi-structured Data. ICDT 1999: 296-313
31. Lei Sheng, Z. Meral Özsoyoglu, Gultekin Özsoyoglu: A Graph Query Language and Its Query Processing. ICDE 1999: 572-581
32. Yannis Papakonstantinou, Pavel Velikhov: Enhancing Semistructured Data Mediators with Document Type Definitions. ICDE 1999: 136-145
33. Sin Yeung Lee, Mong-Li Lee, Tok Wang Ling, Leonid A. Kalinichenko: Designing Good Semi-Structured Databases and Conceptual Modeling. ER 1999: 131-145
34. Andreas Ebert, Uwe Hohenstein, Michael Höding: An Approach for Generating File Interfaces. DASFAA 1999: 61-68
35. Jyh-Herng Chow, Josephine M. Cheng, Daniel T. Chang, Jane Xu: Index Design for Structured Documents Based on Abstraction. DASFAA 1999: 89-96
36. Sourav S. Bhowmick, Sanjay Kumar Madria, Wee Keong Ng, Ee-Peng Lim: Pi-Web Join in a Web Warehouse. DASFAA 1999: 255-262
37. Frédérique Laforest, Anne Tchounikine: A Model for Querying Annotated Documents. ADBIS 1999: 61-74
38. Frank Manola: Towards a Richer Web Object Model. SIGMOD Record 27(1): 76-80(1998)
39. Daniela Florescu, Alon Y. Levy, Alberto O. Mendelzon: Database Techniques for the World-Wide Web: A Survey. SIGMOD Record 27(3): 59-74(1998)
40. Gustavo O. Arocena, Alberto O. Mendelzon: Viewing WISs as Database Applications. Commun. ACM 41(7): 101-102(1998)
41. Tova Milo, Sagit Zohar: Using Schema Matching to Simplify Heterogeneous Data Translation. VLDB 1998: 122-133
42. Shaul Dar, Gadi Entin, Shai Geva, Eran Palmon: DTL's DataSpot: Database Exploration Using Plain Language. VLDB 1998: 645-649
43. Svetlozar Nestorov, Serge Abiteboul, Rajeev Motwani: Extracting Schema from Semistructured Data. SIGMOD Conference 1998: 295-306
44. Mary F. Fernández, Daniela Florescu, Jaewoo Kang, Alon Y. Levy, Dan Suciu: Catching the Boat with Strudel: Experiences with a Web-Site Management System. SIGMOD Conference 1998: 414-425
45. Shaul Dar, Gadi Entin, Shai Geva, Eran Palmon: DTL's DataSpot: Database Exploration as Easy as Browsing the Web ... SIGMOD Conference 1998: 590-592
46. Sophie Cluet, Claude Delobel, Jérôme Siméon, Katarzyna Smaga: Your Mediators Need Data Conversion! SIGMOD Conference 1998: 177-188
47. Daniela Florescu, Alon Y. Levy, Dan Suciu: Query Containment for Conjunctive Queries with Regular Expressions. PODS 1998: 139-148
48. Peter Buneman, Wenfei Fan, Scott Weinstein: Path Constraints in Semistructured and Structured Databases. PODS 1998: 129-138
49. Yue Zhuge, Hector Garcia-Molina: Graph Structured Views and Their Incremental Maintenance. ICDE 1998: 116-125
50. Laks V. S. Lakshmanan, Subbu N. Subramanian, Nita Goyal, Ravi Krishnamurthy: On Query Spreadsheets. ICDE 1998: 134-141
51. Mary F. Fernandez, Dan Suciu: Optimizing Regular Path Expressions Using Graph Schemas. ICDE 1998: 14-23
52. Sudarshan S. Chawathe, Serge Abiteboul, Jennifer Widom: Representing and Querying Changes in Semistructured Data. ICDE 1998: 4-13
53. Gustavo O. Arocena, Alberto O. Mendelzon: WebOQL: Restructuring Documents, Databases, and Webs. ICDE 1998: 24-33
54. Sourav S. Bhowmick, Wee Keong Ng, Ee-Peng Lim: Information Coupling in Web Databases. ER 1998: 92-106
55. Sourav S. Bhowmick, Sanjay Kumar Madria, Wee Keong Ng, Ee-Peng Lim: Web Warehousing: Design and Issues. ER Workshops 1998: 93-104
56. Sourav S. Bhowmick, Sanjay Kumar Madria, Wee Keong Ng, Ee-Peng Lim: Data Visualization in a Web Warehouse. ER Workshops 1998: 68-80
57. Roy Goldman, Jennifer Widom: DataGuides: Enabling Query Formulation and Optimization in Semistructured Databases. VLDB 1997: 436-445
58. Paolo Atzeni, Giansalvatore Mecca, Paolo Merialdo: To Weave the Web. VLDB 1997: 206-215
59. Mary F. Fernández, Daniela Florescu, Jaewoo Kang, Alon Y. Levy, Dan Suciu: STRUDEL: A Web-site Management System. SIGMOD Conference 1997: 549-552
60. Alberto O. Mendelzon, Tova Milo: Formal Models of Web Queries. PODS 1997: 134-143
61. Alon Y. Levy, Dan Suciu: Deciding Containment for Queries with Complex Objects. PODS 1997: 20-31
62. Peter Buneman: Semistructured Data. PODS 1997: 117-121
63. Paolo Atzeni, Giansalvatore Mecca: Cut & Paste. PODS 1997: 144-153
64. Serge Abiteboul, Victor Vianu: Regular Path Queries with Constraints. PODS 1997: 122-133
65. Peter Buneman, Susan B. Davidson, Mary F. Fernandez, Dan Suciu: Adding Structure to Unstructured Data. ICDT 1997: 336-350
66. Serge Abiteboul: Querying Semi-Structured Data. ICDT 1997: 1-18
67. Mary F. Fernandez, Lucian Popa, Dan Suciu: A Structure-Based Approach to Querying Semi-Structured Data. DBPL 1997: 136-159
68. Atsuyuki Morishima, Hiroyuki Kitagawa: A Data Modelling and Query Processing Scheme for Integration of Structured Document Repositories and Relational Databases. DASFAA 1997: 145-154
69. Dan Suciu: Query Decomposition and View Maintenance for Query Languages for Unstructured Data. VLDB 1996: 227-238
70. Peter Buneman, Susan B. Davidson, Dan Suciu: Programming Constructs for Unstructured Data. DBPL 1995: 12