More Web Proxy on the site http://driver.im/

article

Free access

A query language and optimization techniques for unstructured data

Authors:

Susan Davidson,

Gerd Hillebrand,

Dan SuciuAuthors Info & Claims

ACM SIGMOD Record, Volume 25, Issue 2

Pages 505 - 516

https://doi.org/10.1145/235968.233368

Published: 01 June 1996 Publication History

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 y 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 consists in its programming constructs for arbitrarily 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 of UnQL.

References

[1]

Val Breazu-Tannen, Peter Buneman, and Limsoon Wong. Naturally embedded query languages. In J. Biskup and R. Hull, editors, LNCS 6~6: Proceedings of,~h International Conference on Database Theory, Berlin, Germany, October, 1992, pages 140-154. Springer-Verlag, October 1992.

Digital Library

[2]

Peter Buneman, Susan Davidson, Kyle Hart, Chris Overton and Limsoon Wong. A Data Transformation System for Biological Data Sources. Proceedings of 21st VLDB, September 1995.

Digital Library

[3]

Peter Buneman, Susan Davidson, Gerd Hillebrand and Dan Suciu. A Query Language and Optimization Techniques for Unstructured Data. Technical Report MS- CIS-96-09, Department of Computer and Information Science, University of Pennsylvania, Philadelphia, PA 19104, February 1996.

[4]

Peter Buneman, Susan Davidson, and Dan Suciu. Programming constructs for unstructured data. Technical Report MS-CIS- 95-14, Department of Computer and Information Science, University of Pennsylvania, Philadelphia, PA 19104, March 1994.

[5]

P. Buneman, L. Libkin, D. Suciu, V. Tanhen, and L. Wong. Comprehension syntax. SIGMOD Record, 23(1):87-96, March 1994.

Digital Library

[6]

V. Breazu-Tannen and R. Subrahmanyam. Logical and computational aspects of programming with Sets/Bags/Lists. In LNCS 510: Proceedings of 18th International Colloquium on Automata, Languages, and Programming, Madrid, Spain, July 1991, pages 60-75. Springer Verlag, 1991.

Digital Library

[7]

M. Consens and A. Mendelzon. Graphlog: a visual formalism for real life recursion. In Proceedings of the 9th A CM SIGACT- SIGMOD-SIGART Symposium on Principles of Database Systems, April 1990.

Digital Library

[8]

A. Goldberg and R. Paige. Stream processing. In Proceedings of ACM Symposium on LISP and Functional Programming, pages 53-62, Austin, Texas, August 1984.

Digital Library

[9]

N. Goodman, S. Rozen, and L. Stein. Requirements for a deductive query language in the MapBase genome-mapping database. In Proceedings of Workshop on Programming with Logic Databases, Vancouver, BC, October 1993.

[10]

M. Kifer, W. Kim, and Y. Sagiv. Querying object-oriented databases. In M. Stonebraker, editor, Proceedings A CM-SIGMOD International Conference on Management of Data, pages 393-402, San Diego, California, June 1992.

Digital Library

[11]

M. Kifer and G. Lausen. F-logic: A higher order language for reasoning about objects, inheritance, and scheme. In Proceedings of A CM-SIGMOD 1989, pages 46-57, June 1989.

Digital Library

[12]

Anthony S. Kosky. Observational Properties of Databases with Object Identity Technical Report MS-CIS-95-20, University of Pennsylvania, 1995.

[13]

Robin Milner. Communication and concurrency. Prentice Hall, 1989.

Digital Library

[14]

Y. Papakonstantinou, H. Garcia-Molina, and J. Widom. Object exchange across heterogeneous information sources. In IEEE International Conference on Data Engineemng, March 1995.

Digital Library

[15]

J. Thierry-Mieg and R. Durbin. Syntactic Definitions for the ACEDB Data Base Manager. Technical Report MRC-LMB xx.92, MRC Laboratory for Molecular Biology, Cambridge,CB2 2QH, UK, 1992.

[16]

Limsoon Wong. Querying Nested Collections. PhD thesis, Department of Computer and Information Science, University of Pennsylvania, Philadelphia, PA 19104, August 1994.

Digital Library

Cited By

Grant JParisi F(2024)On Measuring Inconsistency in Graph Databases with Regular Path ConstraintsArtificial Intelligence10.1016/j.artint.2024.104197(104197)Online publication date: Aug-2024
https://doi.org/10.1016/j.artint.2024.104197
Reznichenko V(2022)60 Years of Databases (part four)PROBLEMS IN PROGRAMMING10.15407/pp2022.02.057(57-95)Online publication date: Jun-2022
https://doi.org/10.15407/pp2022.02.057
Jachiet LGenevès PGesbert NLayaida NMaier DPottinger RDoan ATan WAlawini ANgo H(2020)On the Optimization of Recursive Relational Queries: Application to Graph QueriesProceedings of the 2020 ACM SIGMOD International Conference on Management of Data10.1145/3318464.3380567(681-697)Online publication date: 11-Jun-2020
https://dl.acm.org/doi/10.1145/3318464.3380567
Show More Cited By

Index Terms

A query language and optimization techniques for unstructured data
1. Information systems
  1. Data management systems
    1. Database design and models
    2. Query languages

Recommendations

A query language and optimization techniques for unstructured data
SIGMOD '96: Proceedings of the 1996 ACM SIGMOD international conference on Management of data

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 ...
Query XML Documents Using XTQ Language
WSCS '08: Proceedings of the IEEE International Workshop on Semantic Computing and Systems

Up to now many XML query languages, including XPath and XQuery which become the standard of XML query standard by W3C, have been prosposed. However, since the navigational query approach adopted by XPath can only get homogeneous data, it often incurs ...
XML Query Optimisation: Specify your Selectivity
DEXA '07: Proceedings of the 18th International Conference on Database and Expert Systems Applications

The problem of efficiently evaluating XPath and XQuery queries has become increasingly significant since more and more XML data is stored in its native form. We propose a novel optimisation technique for XML queries that is based on the semantic ...

Comments

Please enable JavaScript to view thecomments powered by Disqus.

Information & Contributors

Information

Published In

cover image ACM SIGMOD Record

ACM SIGMOD Record Volume 25, Issue 2

June 1996

557 pages

ISSN:0163-5808

DOI:10.1145/235968

Chairman:
T. H. Merrett
McGill Univ.
,
Editors:
H. V. Jagadish,
Inderpal Singh Mumick

Issue’s Table of Contents

SIGMOD '96: Proceedings of the 1996 ACM SIGMOD international conference on Management of data
June 1996
560 pages
ISBN:0897917944
DOI:10.1145/233269
Editor:
Jennifer Widom
Stanford Univ., Stanford, CT

Copyright © 1996 ACM.

Permission to make digital or hard copies of all or part of this work for personal or classroom use is granted without fee provided that copies are not made or distributed for profit or commercial advantage and that copies bear this notice and the full citation on the first page. Copyrights for components of this work owned by others than ACM must be honored. Abstracting with credit is permitted. To copy otherwise, or republish, to post on servers or to redistribute to lists, requires prior specific permission and/or a fee. Request permissions from [email protected]

Publisher

Association for Computing Machinery

New York, NY, United States

Publication History

Published: 01 June 1996

Published in SIGMOD Volume 25, Issue 2

Check for updates

Qualifiers

Article

Contributors

Other Metrics

View Article Metrics

Bibliometrics & Citations

Bibliometrics

Article Metrics

414
Total Citations
View Citations
2,443
Total Downloads

Downloads (Last 12 months)245
Downloads (Last 6 weeks)47

Reflects downloads up to 05 Mar 2025

Other Metrics

View Author Metrics

Citations

Cited By

Grant JParisi F(2024)On Measuring Inconsistency in Graph Databases with Regular Path ConstraintsArtificial Intelligence10.1016/j.artint.2024.104197(104197)Online publication date: Aug-2024
https://doi.org/10.1016/j.artint.2024.104197
Reznichenko V(2022)60 Years of Databases (part four)PROBLEMS IN PROGRAMMING10.15407/pp2022.02.057(57-95)Online publication date: Jun-2022
https://doi.org/10.15407/pp2022.02.057
Jachiet LGenevès PGesbert NLayaida NMaier DPottinger RDoan ATan WAlawini ANgo H(2020)On the Optimization of Recursive Relational Queries: Application to Graph QueriesProceedings of the 2020 ACM SIGMOD International Conference on Management of Data10.1145/3318464.3380567(681-697)Online publication date: 11-Jun-2020
https://dl.acm.org/doi/10.1145/3318464.3380567
Özsu MValduriez PÖzsu MValduriez P(2019)Big Data ProcessingPrinciples of Distributed Database Systems10.1007/978-3-030-26253-2_10(449-518)Online publication date: 3-Dec-2019
https://doi.org/10.1007/978-3-030-26253-2_10
Suciu D(2018)Semi-structured Data ModelEncyclopedia of Database Systems10.1007/978-1-4614-8265-9_337(3446-3451)Online publication date: 7-Dec-2018
https://doi.org/10.1007/978-1-4614-8265-9_337
Reutter JRomero MVardi M(2017)Regular Queries on Graph DatabasesTheory of Computing Systems10.1007/s00224-016-9676-261:1(31-83)Online publication date: 1-Jul-2017
https://dl.acm.org/doi/10.1007/s00224-016-9676-2
Suciu D(2017)Semi-structured Data ModelEncyclopedia of Database Systems10.1007/978-1-4899-7993-3_337-2(1-5)Online publication date: 27-Jan-2017
https://doi.org/10.1007/978-1-4899-7993-3_337-2
Yakovets NGodfrey PGryz JÖzcan FKoutrika GMadden S(2016)Query Planning for Evaluating SPARQL Property PathsProceedings of the 2016 International Conference on Management of Data10.1145/2882903.2882944(1875-1889)Online publication date: 26-Jun-2016
https://dl.acm.org/doi/10.1145/2882903.2882944
Zhuang YWang YShao JChen LLu WSun JWei BWu J(2016)D-OceanFrontiers of Computer Science: Selected Publications from Chinese Universities10.1007/s11704-015-5045-610:2(353-369)Online publication date: 1-Apr-2016
https://dl.acm.org/doi/10.1007/s11704-015-5045-6
Fadoua HAmel G(2016)Heterogeneous NoSQL Databases Abstraction Approach Based on Full Text Search IndexesIntelligent Decision Technologies 201610.1007/978-3-319-39627-9_37(417-427)Online publication date: 9-Jun-2016
https://doi.org/10.1007/978-3-319-39627-9_37
Show More Cited By

View Options

View options

PDF

View or Download as a PDF file.

eReader

View online with eReader.

Login options

Check if you have access through your login credentials or your institution to get full access on this article.

Full Access

Get this Publication

Figures

Tables

Media

View Issue’s Table of Contents