Document Open Access Logo

Optimization of Nonsequenced Queries Using Log-Segmented Timestamps

Author Curtis E. Dyreson

PDF
Thumbnail PDF

File

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

Document Identifiers

Author Details

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

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

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.

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

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.
Questions / Remarks / Feedback
X

Feedback for Dagstuhl Publishing


Thanks for your feedback!

Feedback submitted

Could not send message

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