Abstract
After the schema of a relation has evolved some tuples no longer fit the current schema. The mismatch between the schema a tuple is supposed to have and the schema a tuple actually has is inherent to evolving schemas, and is the defining property of legacy tuples. Handling this mismatch is at the very core of a DBMS that supports schema evolution. The paper proposes tuple versioning as a structure for evolving databases that permits conditional schema changes and precisely keeps track of schema mismatches at the level of individual tuples. Together with the change history this allows the DBMS to correctly identify current, legacy, and invalid tuples. We give an algorithm that classifies tuples, in time and space proportional to the length of the change history. We show how tuple versioning supports a flexible semantics needed to accurately answer queries over evolving databases.
This research was supported in part by the Danish Technical Research Council through grant 9700780 and Nykredit, Inc.
Access this chapter
Tax calculation will be finalised at checkout
Purchases are for personal use only
Preview
Unable to display preview. Download preview PDF.
Similar content being viewed by others
References
G. Ariav. Temporally Oriented Data Definitions: Managing Schema Evolution in Temporally Oriented Databases. Data Knowledge Engineering, 6(6):451–467, 1991.
P. Atzeni and V. de Antonellis. Relational Database Theory. Benjamin/Cummings, 1993.
P. Atzeni and N. M. Morfuni. Functional dependencies in relations with null values. Information Processing Letters, 18(4):233–238, 1984.
J. Banerjee, W. Kim, H.-J. Kim, and H.F. Korth. Semantics and Implementation of Schema Evolution in Object-Oriented Databases. In ACM SIGMOD International Conference on Management of Data, pages 311–322. ACM Press, 1987.
Elisa Bertino. A view mechanism for object-oriented databases. In Alain Pirotte, Claude Delobel, and Georg Gottlob, editors, Advances in Database Technology—EDBT’92, 3rd International Conference on Extending Database Technology, Vienna, Austria, March 23–27, 1992, Proceedings, volume 580 of Lecture Notes in Computer Science, pages 136–151. Springer, 1992.
C.D. Castro, F. Grandi, and M.R. Scalas. On Schema Versioning in Temporal Databases. In: Recent Advances in Temporal Databases. Springer, 1995.
C.D. Castro, F. Grandi, and R.R. Scalas. Schema Versioning for Multitemporal Relational Databases. Information Systems, 22(5):249–290, 1997.
J. Clifford and A. Croker. The Historical Relational Data Model (HRDM) and Algebra based on Lifespans. In 3rd International Conference of Data Engineering, Los Angeles, California, USA, Proceedings, pages 528–537. IEEE Computer Society Press, 1987.
G. Grahne. The Problem of Incomplete Information in Relational Databases. In Springer LNCS No. 554, 1991.
O. G. Jensen and M. H. Böhlen. Evolving Relations. In Database Schema Evolution and Meta-Modeling, volume 9th International Workshop on Foundations of Models and Languages for Data and Objects of Springer LNCS 2065, page 115 ff., 2001.
A. M. Keller. Set-theoretic problems of null completion in relational databases. Information Processing Letters, 22(5):261–265, 1986.
N. Lerat and W. Lipski. Nonapplicable Nulls. Theoretical Computer Science, 46:67–82, 1986.
L.E. McKenzie and R.T. Snodgrass. Schema Evolution and the Relational Algebra. Information Systems, 15(2):207–232, 1990.
R. van der Meyden. Logical Approaches to Incomplete Information: a Survey. In: Logics for Databases and Information Systems (chapter 10). Kluwer Academic Publishers, 1998.
Simon R. Monk and Ian Sommerville. Schema Evolution in OODBs using Class Versioning. SIGMOD Record, 22(3):16–22, 1993.
Young-Gook Ra and Elke A. Rundensteiner. A transparent object-oriented schema change approach using view evolution. In Philip S. Yu and Arbee L. P. Chen, editors, Proceedings of the Eleventh International Conference on Data Engineering, March 6–10, 1995, Taipei, Taiwan, pages 165–172. IEEE Computer Society, 1995.
J.F. Roddick. Schema Evolution in Database Systems an Annotated Bibliography. ACM SIGMOD Record, 21(4):35–40, 1992.
J.F. Roddick. SQL/SE—A Query Language Extension for Databases Supporting Schema Evolution. ACM SIGMOD Record, 21(3):10–16, 1992.
J.F. Roddick. A Survey of Schema Versioning Issues for Database Systems. Information Software Technology, 37(7):383–393, 1995.
J.F. Roddick, N.G. Craske, and T.J. Richards. A Taxonomy for Schema Versioning based on the Relational and Entity Relationship Models. In 12th International Conference on Entity-Relationship Approach, Arlington, Texas, USA, December 15–17, 1993, Proceedings, pages 137–148. Springer-Verlag, 1993.
J.F. Roddick and R.T. Snodgrass. Schema Versioning. In: The TSQL92 Temporal Query Language. Noewell-MA: Kluwer Academic Publishers, 1995.
Andrea H. Skarra and Stanley B. Zdonik. The Management of Changing Types in an Object-Oriented Database. In OOPSLA, 1986, Portland, Oregon, Proceedings, pages 483–495, 1986.
R.T. Snodgrass et al. TSQL2 Language Specification. ACM SIGMOD Record, 23(1), 1994.
Markus Tresch and Marc H. Scholl. Schema transformation without database reorganization. SIGMOD Record, 22(1):21–27, 1993.
Y. Vassiliou. Null values in Database Management: A Denotational Semantics Approach. In Proceedings of the 1979 ACM SIGMOD International Conference on Management of Data, pages 162–169, 1979.
Y. Vassiliou. Functional Dependencies and Incomplete Information. In International Conference on Very Large Databases, pages 260–269, 1980.
Author information
Authors and Affiliations
Editor information
Editors and Affiliations
Rights and permissions
Copyright information
© 2002 Springer-Verlag Berlin Heidelberg
About this paper
Cite this paper
Jensen, O.G., Böhlen, M. (2002). Current, Legacy, and Invalid Tuples in Conditionally Evolving Databases. In: Yakhno, T. (eds) Advances in Information Systems. ADVIS 2002. Lecture Notes in Computer Science, vol 2457. Springer, Berlin, Heidelberg. https://doi.org/10.1007/3-540-36077-8_7
Download citation
DOI: https://doi.org/10.1007/3-540-36077-8_7
Published:
Publisher Name: Springer, Berlin, Heidelberg
Print ISBN: 978-3-540-00009-9
Online ISBN: 978-3-540-36077-3
eBook Packages: Springer Book Archive