Abstract
To support temporal operators and to increase the efficiency of temporal queries, indexing based on temporal attributes is required. We consider the problem of indexing the temporal dimension in valid time databases where the temporal information of data objects are represented as valid time intervals that need to be managed dynamically by an efficient index structure. We propose an indexing scheme that uses augmented B+trees called Interval B+trees for indexing a dynamic set of valid time intervals. We apply time-splits at the leaf level of the IB+tree that would partition long valid time intervals into disjoint subintervals and distribute them among several leaf nodes to increase efficiency of search operation, especially for timeslice queries. We compared IB+trees with time-splits to one dimensional R-trees and observed that while their performances for timeslice queries are comparable, IB+trees are far more superior for many temporal queries that are based on beginning points of time intervals.
This work has been partially supported by NSF grants IRI 92-24660, IRI 96-31214, and the NSF FAW Award IRI-90-24152.
Preview
Unable to display preview. Download preview PDF.
References
J.F. Allen, P.J. Hayes, “A Common-sense Theory of Time”, Proceedings of the International Joint Conference on Artificial Intelligence, August 1985.
T. Bozkaya, “Index Structures for Temporal and Multimedia Databases”, PHD Thesis, CES Dept., Case Western Reserve University, Cleveland, Ohio, May 1998.
B. Becker, S. Gschwind, T. Ohler, B. Seeger, P. Widmayer, “On Optimal Multiversion Access Structures”, Proceedings of Symposium on Large Spatial Databases, in LNCS, Vol 692, pages 123–141, Singapore 1993.
T. Bozkaya, M.Ozsoyoglu, “Indexing Transaction Time Databases”, to appear in Information Sciences.
T. H. Cormen, C. E. Leiserson, R.L. Rivest “Introduction to Algorithms”, MCGraw-Hill 1992.
R. Elmasri, G.T.J. Wuu, Y. Kim, “The Time-Index: An Access Structure for Temporal Data”, Proc. VLDB'90, pages 1–12, August 1990.
R. Elmasri, G. T. J. Wuu, V. Kouramajiam, “The Time-Index and The Monotonic B+tree”, In [T93], chapter 18.
C.H. Goh, H. Lu, B.C. Ooi, K-L. Tan, “Indexing Temporal Data Using Existing B+-Trees”, Data and Knowledge Engineering, vol 18, no 2, pages 147–165, March 1996.
A. Guttman, “R-trees: A Dynamic Index Structure for Spatial Searching”, Proc. ACM SIGMOD'84, pages 47–57, May 1984.
A. Kumar, V.J. Tsotras, C. Faloutsos, “Access Methods for Bi-Temporal Databases”, Proc. International Workshop on Temporal Databases, Zurich, Switzerland, pages 235–254, 17–18 September 1995.
C. Kolovson, M. Stonebraker, “Segment Indexes: Dynamic Indexing Techniques for Multi-dimensional Interval Data”, Proc. ACM SIGMOD, pages 138–147, May 1991.
D.B. Lomet, B. Salzberg, “The Performance of a Multiversion Access Method”, Proc. ACM SIGMOD'90, pages 353–363, June 1990.
E.M. McCreight, “Priority Search Trees”, SIAM Journal on Computing, pages 257–277, 1985.
M.A. Nascimento and M.H. Dunham, “Indexing Valid Time Databases Via B+-Trees — The MAP21 Approach”, Technical Report 97-CSE-08, Southern Methodist University.
F.P. Preparata, M.I. Shamos, “Computational Geometry, An Introduction”, Springer-Verlag, 1985.
S. Ramaswamy, “Efficient Indexing for Constraint and Temporal Databases”, Proc. ICDT'97, January 1997.
A. Segev, H. Gunadhi, “Efficient Indexing Method for Temporal Relations”, IEEE Transactions on Knowledge and Data Engineering,5(3), pages 496–509, 1993.
H. Shen, B. C. Ooi, H. Lu, “ The TP-Index: A Dynamic and Efficient Indexing Mechanism for Temporal Databases”, Proc. IEEE DE, pages 274–281, 1994.
B. Salzberg, V.J.Tsotras, “A Comparison of Access Methods for Time Evolving Data”, To appear in ACM Computing Surveys.
A. U. Tansel et. al. “Temporal Databases, Theory, Design and Implementation”, Benjamin/Cummings (1993).
V. J. Tsotras, N. Kangelaris, “The Snapshot Index: An I/O Optimal Access Method For Timeslice Queries”, Information Systems, 20(3), pages 237–260, 1995.
Author information
Authors and Affiliations
Editor information
Rights and permissions
Copyright information
© 1998 Springer-Verlag Berlin Heidelberg
About this paper
Cite this paper
Bozkaya, T., Ozsoyoglu, M. (1998). Indexing valid time intervals. In: Quirchmayr, G., Schweighofer, E., Bench-Capon, T.J. (eds) Database and Expert Systems Applications. DEXA 1998. Lecture Notes in Computer Science, vol 1460. Springer, Berlin, Heidelberg. https://doi.org/10.1007/BFb0054512
Download citation
DOI: https://doi.org/10.1007/BFb0054512
Published:
Publisher Name: Springer, Berlin, Heidelberg
Print ISBN: 978-3-540-64950-2
Online ISBN: 978-3-540-68060-4
eBook Packages: Springer Book Archive