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

Sequence Query Processing.

Praveen Seshadri, Miron Livny, Raghu Ramakrishnan: Sequence Query Processing. SIGMOD Conference 1994: 430-441
@inproceedings{DBLP:conf/sigmod/SeshadriLR94,
  author    = {Praveen Seshadri and
               Miron Livny and
               Raghu Ramakrishnan},
  editor    = {Richard T. Snodgrass and
               Marianne Winslett},
  title     = {Sequence Query Processing},
  booktitle = {Proceedings of the 1994 ACM SIGMOD International Conference on
               Management of Data, Minneapolis, Minnesota, May 24-27, 1994},
  publisher = {ACM Press},
  year      = {1994},
  pages     = {430-441},
  ee        = {http://doi.acm.org/10.1145/191839.191926, db/conf/sigmod/SeshadriLR94.html},
  crossref  = {DBLP:conf/sigmod/94},
  bibsource = {DBLP, http://dblp.uni-trier.de}
}

Abstract

Many applications require the ability to manipulate sequences of data. We motivate the importance of sequence query processing, and present a framework for the optimization of sequence queries based on several novel techniques. These include query transformations, optimizations that utilize meta-data, and caching of intermediate results. We present a bottom-up algorithm that generates an efficient query evaluation plan based on cost estimates. This work also identifies a number of directions in which future research can be directed.

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

Richard T. Snodgrass, Marianne Winslett (Eds.): Proceedings of the 1994 ACM SIGMOD International Conference on Management of Data, Minneapolis, Minnesota, May 24-27, 1994. ACM Press 1994 CiteSeerX Google scholar pubzone.org BibTeX bibliographical record in XML, SIGMOD Record 23(2), June 1994
Contents

Online Edition: ACM Digital Library

[Abstract and Index Terms]
[Full Text in PDF Format, 1326 KB]

References

[BR91]
Catriel Beeri, Raghu Ramakrishnan: On the Power of Magic. J. Log. Program. 10(1/2/3&4): 255-299(1991) CiteSeerX Google scholar pubzone.org BibTeX bibliographical record in XML
[CC87]
James Clifford, Albert Croker: The Historical Relational Data Model (HRDM) and Algebra Based on Lifespans. ICDE 1987: 528-537 CiteSeerX Google scholar pubzone.org BibTeX bibliographical record in XML
[Day87]
Umeshwar Dayal: Of Nests and Trees: A Unified Approach to Processing Queries That Contain Nested Subqueries, Aggregates, and Quantifiers. VLDB 1987: 197-208 CiteSeerX Google scholar pubzone.org BibTeX bibliographical record in XML
[EWK90]
Ramez Elmasri, Gene T. J. Wuu, Yeong-Joon Kim: The Time Index: An Access Structure for Temporal Data. VLDB 1990: 1-12 CiteSeerX Google scholar pubzone.org BibTeX bibliographical record in XML
[Gad86]
Shashi K. Gadia: Toward a Multihomogeneous Model for a Temporal Database. ICDE 1986: 390-397 CiteSeerX Google scholar pubzone.org BibTeX bibliographical record in XML
[GHK92]
Sumit Ganguly, Waqar Hasan, Ravi Krishnamurthy: Query Optimization for Parallel Execution. SIGMOD Conference 1992: 9-18 CiteSeerX Google scholar pubzone.org BibTeX bibliographical record in XML
[GJS92]
Narain H. Gehani, H. V. Jagadish, Oded Shmueli: Composite Event Specification in Active Databases: Model & Implementation. VLDB 1992: 327-338 CiteSeerX Google scholar pubzone.org BibTeX bibliographical record in XML
[GS89a]
Arie Segev, Himawan Gunadhi: Event-Join Optimization in Temporal Relational Databases. VLDB 1989: 205-215 CiteSeerX Google scholar pubzone.org BibTeX bibliographical record in XML
[GS89b]
Himawan Gunadhi, Arie Segev: A Framework for Query Optimization in Temporal Databases. SSDBM 1990: 131-147 CiteSeerX Google scholar pubzone.org BibTeX bibliographical record in XML
[GS91]
Himawan Gunadhi, Arie Segev: Query Processing Algorithms for Temporal Intersection Joins. ICDE 1991: 336-344 CiteSeerX Google scholar pubzone.org BibTeX bibliographical record in XML
[GW87]
Richard A. Ganski, Harry K. T. Wong: Optimization of Nested SQL Queries Revisited. SIGMOD Conference 1987: 23-33 CiteSeerX Google scholar pubzone.org BibTeX bibliographical record in XML
[JCG+92]
Christian S. Jensen, James Clifford, Shashi K. Gadia, Arie Segev, Richard T. Snodgrass: A Glossary of Temporal Database Concepts. SIGMOD Record 21(3): 35-43(1992) CiteSeerX Google scholar pubzone.org BibTeX bibliographical record in XML
[Kim82]
Won Kim: On Optimizing an SQL-like Nested Query. ACM Trans. Database Syst. 7(3): 443-469(1982) CiteSeerX Google scholar pubzone.org BibTeX bibliographical record in XML
[LM93]
...
[LS89]
David B. Lomet, Betty Salzberg: Access Methods for Multiversion Data. SIGMOD Conference 1989: 315-324 CiteSeerX Google scholar pubzone.org BibTeX bibliographical record in XML
[NA89]
...
[NG93]
...
[Ric92]
Joel E. Richardson: Supporting Lists in a Data Model (A Timely Approach). VLDB 1992: 127-138 CiteSeerX Google scholar pubzone.org BibTeX bibliographical record in XML
[RS87]
Doron Rotem, Arie Segev: Physical Organization of Temporal Data. ICDE 1987: 547-553 CiteSeerX Google scholar pubzone.org BibTeX bibliographical record in XML
[SK86]
Arie Shoshani, Kyoji Kawagoe: Temporal Data Management. VLDB 1986: 79-88 CiteSeerX Google scholar pubzone.org BibTeX bibliographical record in XML
[SLR]
Praveen Seshadri, Miron Livny, Raghu Ramakrishnan: SEQ: A Model for Sequence Databases. ICDE 1995: 232-239 CiteSeerX Google scholar pubzone.org BibTeX bibliographical record in XML
[SMALP79]
Patricia G. Selinger, Morton M. Astrahan, Donald D. Chamberlin, Raymond A. Lorie, Thomas G. Price: Access Path Selection in a Relational Database Management System. SIGMOD Conference 1979: 23-34 CiteSeerX Google scholar pubzone.org BibTeX bibliographical record in XML
[Sno87]
Richard T. Snodgrass: The Temporal Query Language TQuel. ACM Trans. Database Syst. 12(2): 247-298(1987) CiteSeerX Google scholar pubzone.org BibTeX bibliographical record in XML
[Soo91]
Michael D. Soo: Bibliography on Temporal Databases. SIGMOD Record 20(1): 14-23(1991) CiteSeerX Google scholar pubzone.org BibTeX bibliographical record in XML
[SP90]
...
[SPL]
Praveen Seshadri, Hamid Pirahesh, T. Y. Cliff Leung: Complex Query Decorrelation. ICDE 1996: 450-458 CiteSeerX Google scholar pubzone.org BibTeX bibliographical record in XML
[SS87]
Arie Segev, Arie Shoshani: Logical Modeling of Temporal Data. SIGMOD Conference 1987: 454-466 CiteSeerX Google scholar pubzone.org BibTeX bibliographical record in XML
[SS88]
Arie Segev, Arie Shoshani: The Representation of a Temporal Data Model in the Relational Environment. SSDBM 1988: 39-61 CiteSeerX Google scholar pubzone.org BibTeX bibliographical record in XML
[WD92]
Gene T. J. Wuu, Umeshwar Dayal: A Uniform Model for Temporal Object-Oriented Databases. ICDE 1992: 584-593 CiteSeerX Google scholar pubzone.org BibTeX bibliographical record in XML

Referenced by

  1. Davood Rafiei: On Similarity-Based Queries for Time Series Data. ICDE 1999: 410-417
  2. Ke Wang, Beng Chin Ooi, Sam Yuan Sung: P-Tree: A B-Tree Index for Lists. DASFAA 1999: 221-228
  3. Ling Lin, Tore Risch: Querying Continuous Time Sequences. VLDB 1998: 170-181
  4. Raghu Ramakrishnan, Donko Donjerkovic, Arvind Ranganathan, Kevin S. Beyer, Muralidhar Krishnaprasad: SRQL: Sorted Relational Query Language. SSDBM 1998: 84-95
  5. Byoung-Kee Yi, H. V. Jagadish, Christos Faloutsos: Efficient Retrieval of Similar Time Sequences Under Time Warping. ICDE 1998: 201-208
  6. Stacie Hibino, Elke A. Rundensteiner: Processing Incremental Multidimensional Range Queries in a Direct Manipulation Visual Query. ICDE 1998: 458-465
  7. Iakovos Motakis, Carlo Zaniolo: Temporal Aggregation in Active Database Rules. SIGMOD Conference 1997: 440-451
  8. Praveen Seshadri, Miron Livny, Raghu Ramakrishnan: The Design and Implementation of a Sequence Database System. VLDB 1996: 99-110
  9. Leonid Libkin, Rona Machlin, Limsoon Wong: A Query Language for Multidimensional Arrays: Design, Implementation, and Optimization Techniques. SIGMOD Conference 1996: 228-239
  10. Hagit Shatkay, Stanley B. Zdonik: Approximate Queries and Representations for Large Data Sequences. ICDE 1996: 536-545
  11. Divesh Srivastava, S. Sudarshan, Raghu Ramakrishnan, Jeffrey F. Naughton: Space Optimization in Deductive Databases. ACM Trans. Database Syst. 20(4): 472-516(1995)
  12. Gultekin Özsoyoglu, Richard T. Snodgrass: Temporal and Real-Time Databases: A Survey. IEEE Trans. Knowl. Data Eng. 7(4): 513-532(1995)
  13. H. V. Jagadish, Inderpal Singh Mumick, Abraham Silberschatz: View Maintenance Issues for the Chronicle Data Model. PODS 1995: 113-124
  14. H. V. Jagadish, Alberto O. Mendelzon, Tova Milo: Similarity-Based Queries. PODS 1995: 36-45
  15. Bharathi Subramanian, Theodore W. Leung, Scott L. Vandenberg, Stanley B. Zdonik: The AQUA Approach to Querying Lists and Trees in Object-Oriented Databases. ICDE 1995: 80-89
  16. Praveen Seshadri, Miron Livny, Raghu Ramakrishnan: SEQ: A Model for Sequence Databases. ICDE 1995: 232-239

Copyright © Mon Nov 2 21:12:02 2009 by Michael Ley (ley@uni-trier.de)