Document Open Access Logo

Optimization of Nonsequenced Queries Using Log-Segmented Timestamps

Author Curtis E. Dyreson

PDF

File

Thumbnail PDF
PDF
LIPIcs.TIME.2023.13.pdf
  • Filesize: 0.71 MB
  • 15 pages

Document Identifiers

Subject Classification

ACM Subject Classification
  • Information systems → Temporal data
  • Information systems → Relational database query languages
Keywords
  • Temporal databases
  • nonsequenced semantics
  • query evaluation
  • query performance

Metrics

  • Access Statistics
  • Total Accesses (updated on a weekly basis)
    0
    PDF Downloads
    0
    Metadata Views

Abstract

In a period-timestamped, relational temporal database, each tuple is timestamped with a period. The timestamp records when the tuple is "alive" in some temporal dimension. Nonsequenced semantics is a query evaluation semantics that involves adding temporal predicates and constructors to a query. We show how to use log-segmented timestamps to improve the efficiency of temporal, nonsequenced queries evaluated using a non-temporal DBMS, i.e., a DBMS that has no special temporal indexes or query evaluation operators. A log-segmented timestamp divides the time-line into segments of known length. Any temporal period can be represented by a small number of such segments. The segments can be appended to a relation as additional columns. The advantage of log-segmented timestamps is that each segment can be indexed using standard database indexes, e.g., a B^+-tree. A query optimizer can use the indexes to generate a lower cost query evaluation plan. This paper shows how to rewrite a query to use the additional columns and evaluates the time cost benefits and space cost disadvantages.

Cite As Get BibTex

Curtis E. Dyreson. Optimization of Nonsequenced Queries Using Log-Segmented Timestamps. In 30th International Symposium on Temporal Representation and Reasoning (TIME 2023). Leibniz International Proceedings in Informatics (LIPIcs), Volume 278, pp. 13:1-13:15, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2023) https://doi.org/10.4230/LIPIcs.TIME.2023.13

Author Details

Curtis E. Dyreson
  • Department of Computer Science, Utah State University, Logan, UT, USA

Supplementary Materials

References

  1. Andreas Behrend, Anton Dignös, Johann Gamper, Philip Schmiegelt, Hannes Voigt, Matthias Rottmann, and Karsten Kahl. Period Index: A Learned 2D Hash Index for Range and Duration Queries. In Proceedings of the 16th International Symposium on Spatial and Temporal Databases, SSTD 2019, Vienna, Austria, August 19-21, 2019, pages 100-109. ACM, 2019. URL: https://doi.org/10.1145/3340964.3340965.
  2. Michael H. Böhlen and Christian S. Jensen. Sequenced semantics. In Encyclopedia of Database Systems, pages 2619-2621. 2009. URL: https://doi.org/10.1007/978-0-387-39940-9_1053.
  3. Michael H. Böhlen and Christian S. Jensen. Sequenced semantics. In Ling Liu and M. Tamer Özsu, editors, Encyclopedia of Database Systems, Second Edition. Springer, 2018. URL: https://doi.org/10.1007/978-1-4614-8265-9_1053.
  4. Michael H. Böhlen, Christian S. Jensen, and Richard T. Snodgrass. Temporal Statement Modifiers. ACM Trans. Database Syst., 25(4):407-456, 2000. URL: http://portal.acm.org/citation.cfm?id=377674.377665.
  5. Michael H. Böhlen, Christian S. Jensen, and Richard T. Snodgrass. Nonsequenced semantics. In Encyclopedia of Database Systems, pages 1913-1915. 2009. URL: https://doi.org/10.1007/978-0-387-39940-9_1052.
  6. Matteo Ceccarello, Anton Dignös, Johann Gamper, and Christina Khnaisser. Indexing Temporal Relations for Range-Duration Queries. CoRR, abs/2206.07428, 2022. URL: https://doi.org/10.48550/arXiv.2206.07428.
  7. Cindy Xinmin Chen and Carlo Zaniolo. Sql^st: A spatio-temporal data model and query language. In ER, pages 96-111, 2000. URL: https://doi.org/10.1007/3-540-45393-8_8.
  8. Jan Chomicki and David Toman. Abstract versus concrete temporal query languages. In Encyclopedia of Database Systems, pages 1-6. 2009. URL: https://doi.org/10.1007/978-0-387-39940-9_1559.
  9. George Christodoulou, Panagiotis Bouros, and Nikos Mamoulis. Hint: A hierarchical index for intervals in main memory, 2021. URL: https://arxiv.org/abs/2104.10939.
  10. Carlo Combi and Pietro Sala. Interval-based temporal functional dependencies: specification and verification. Ann. Math. Artif. Intell., 71(1-3):85-130, 2014. URL: https://doi.org/10.1007/s10472-013-9387-1.
  11. Anton Dignös, Michael H. Böhlen, and Johann Gamper. Temporal Alignment. In SIGMOD, pages 433-444, 2012. URL: https://doi.org/10.1145/2213836.2213886.
  12. Anton Dignös, Michael H. Böhlen, Johann Gamper, Christian S. Jensen, and Peter Moser. Leveraging Range Joins for the Computation of Overlap joins. VLDB J., 31(1):75-99, 2022. URL: https://doi.org/10.1007/s00778-021-00692-3.
  13. Curtis E. Dyreson. Using CouchDB to Compute Temporal Aggregates. In 18th IEEE International Conference on High Performance Computing and Communications (HPCC), pages 1131-1138. IEEE Computer Society, 2016. URL: https://doi.org/10.1109/HPCC-SmartCity-DSS.2016.0159.
  14. Curtis E. Dyreson and M. A. Manazir Ahsan. Achieving a Sequenced, Relational Query Language with Log-Segmented Timestamps. In TIME 2021, volume 206 of LIPIcs, pages 14:1-14:13. Schloss Dagstuhl - Leibniz-Zentrum für Informatik, 2021. URL: https://doi.org/10.4230/LIPIcs.TIME.2021.14.
  15. Curtis E. Dyreson and Venkata A. Rani. Translating Temporal SQL to Nested SQL. In 23rd International Symposium on Temporal Representation and Reasoning, TIME, pages 157-166. IEEE Computer Society, 2016. URL: https://doi.org/10.1109/TIME.2016.24.
  16. Curtis E. Dyreson, Venkata A. Rani, and Amani Shatnawi. Unifying Sequenced and Non-sequenced Semantics. In 22nd International Symposium on Temporal Representation and Reasoning, TIME, pages 38-46. IEEE Computer Society, 2015. URL: https://doi.org/10.1109/TIME.2015.22.
  17. Curtis E. Dyreson and Richard T. Snodgrass. Timestamp semantics and representation. Information Systems, 18(3):143-166, 1993. URL: https://doi.org/10.1016/0306-4379(93)90034-X.
  18. Fabio Grandi. T-SPARQL: A TSQL2-like Temporal Query Language for RDF. In ADBIS, pages 21-30, 2010. URL: http://ceur-ws.org/Vol-639/021-grandi.pdf.
  19. Fabio Grandi, Federica Mandreoli, Riccardo Martoglia, and Wilma Penzo. Unleashing the power of querying streaming data in a temporal database world: A relational algebra approach. Inf. Syst., 103:101872, 2022. URL: https://doi.org/10.1016/j.is.2021.101872.
  20. C. S. Jensen and C. E. Dyreson (editors). A Consensus Glossary of Temporal Database Concepts - February 1998 Version. In Temporal Databases: Research and Practice, Lecture Notes in Computer Science 1399, pages 367-405. Springer-Verlag, 1998. Google Scholar
  21. Seyed Nima Khezr and Nima Jafari Navimipour. Mapreduce and its applications, challenges, and architecture: a comprehensive review and directions for future research. J. Grid Comput., 15(3):295-321, 2017. URL: https://doi.org/10.1007/s10723-017-9408-0.
  22. R. T. Snodgrass. Introduction to TSQL2. In R. T. Snodgrass, editor, The TSQL2 Temporal Query Language, chapter 2, pages 19-31. Kluwer Academic Publishers, 1995. Google Scholar
  23. Richard T. Snodgrass. The Temporal Query Language TQuel. ACM Transactions on Database Systems, 12(2):247-298, 1987. URL: https://doi.org/10.1145/22952.22956.
  24. Richard T. Snodgrass, editor. The TSQL2 Temporal Query Language. Kluwer, 1995. Google Scholar
  25. A. U. Tansel. Modelling temporal data. Information and Software Technology, 32(8):514-520, October 1990. Google Scholar
  26. Kristian Torp, Christian S. Jensen, and Michael H. Böhlen. Layered temporal DBMS: concepts and techniques. In DASFAA, pages 371-380, 1997. Google Scholar
  27. Kristian Torp, Christian S. Jensen, and Richard T. Snodgrass. Stratum Approaches to Temporal DBMS Implementation. In IDEAS, pages 4-13, 1998. URL: https://doi.org/10.1109/IDEAS.1998.694346.
Any Issues?
X

Feedback on the Current Page

CAPTCHA

Thanks for your feedback!

Feedback submitted to Dagstuhl Publishing

Could not send message

Please try again later or send an E-mail
© 2023-2025 Schloss Dagstuhl – LZI GmbH About DROPS Imprint Privacy Contact