License: Creative Commons Attribution 4.0 International license (CC BY 4.0)
When quoting this document, please refer to the following
DOI: 10.4230/LIPIcs.TIME.2023.13
URN: urn:nbn:de:0030-drops-191036
URL: http://dagstuhl.sunsite.rwth-aachen.de/volltexte/2023/19103/
Go to the corresponding LIPIcs Volume Portal

Dyreson, Curtis E.

Optimization of Nonsequenced Queries Using Log-Segmented Timestamps

pdf-format:
LIPIcs-TIME-2023-13.pdf (0.7 MB)

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.

BibTeX - Entry

@InProceedings{dyreson:LIPIcs.TIME.2023.13,
  author =	{Dyreson, Curtis E.},
  title =	{{Optimization of Nonsequenced Queries Using Log-Segmented Timestamps}},
  booktitle =	{30th International Symposium on Temporal Representation and Reasoning (TIME 2023)},
  pages =	{13:1--13:15},
  series =	{Leibniz International Proceedings in Informatics (LIPIcs)},
  ISBN =	{978-3-95977-298-3},
  ISSN =	{1868-8969},
  year =	{2023},
  volume =	{278},
  editor =	{Artikis, Alexander and Bruse, Florian and Hunsberger, Luke},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops.dagstuhl.de/opus/volltexte/2023/19103},
  URN =		{urn:nbn:de:0030-drops-191036},
  doi =		{10.4230/LIPIcs.TIME.2023.13},
  annote =	{Keywords: Temporal databases, nonsequenced semantics, query evaluation, query performance}
}

Keywords: Temporal databases, nonsequenced semantics, query evaluation, query performance
Collection: 30th International Symposium on Temporal Representation and Reasoning (TIME 2023)
Issue Date: 2023
Date of publication: 18.09.2023
Supplementary Material: Software (Source Code): https://www.usu.edu/cs/people/CurtisDyreson/logsegmented/nonsequenced

DROPS-Home | Fulltext Search | Imprint | Privacy Published by LZI