Our research on foreign-key evolution studies how the referential structure of relational databases changes over time and how it relates to table evolution. At the schema level, we find widely different practices in the use and maintenance of foreign keys and introduce the Diachronic Graph to represent all tables and foreign-key relationships appearing throughout a schema history. At the table level, our results show that greater topological complexity is associated with higher update activity, while structurally simple tables are more often stable or unchanged.
In this line of research, we study the evolution of foreign keys in the context of schema evolution for relational databases. Specifically, we study the schema histories of a six free, open-source databases that contain foreign keys.
In [ER17, Computing 19] our findings verify previous results that schemata grow in the long run in terms of tables. To our surprise, we discovered that foreign keys appear to be fairly scarce in the projects that we have studied and they do not necessarily grow in sync with table growth. In fact, we have observed different "cultures" for the handling of foreign keys, ranging from treating foreign keys as an indispensable part of the schema, in full sync with the growth of tables, to the unexpected extreme of treating foreign keys as an optional add-on that twice resulted in their full removal from the schema of the database. Apart from the behavior of entire schemata, we have also studied the behavior of individual tables. We model the schema of any version of the history as a graph, with tables being nodes and foreign keys being edges. The union of these graphs is called the Diachronic Graph of the schema and contains all the tables and foreign keys that ever appeared in the schema history. The study of the Total Degree of tables at the Diachronic Graph, reveals several patterns. The population of tables with total degree in the range of [0-2] includes almost all the tables that were eventually removed from the schema, as well as the vast majority of survivor tables. These low-degree tables (especially the dead ones) tend to be mostly with zero or very few internal updates in their entire history. At the same time, the few tables with degree higher than 2 are typically born very early in the life of the schema, overwhelmingly survivors, and, unusually active, typically undergoing medium or high update activity.
In [ER20] we study the evolution of tables in a schema with respect to the structure of the foreign keys to which tables are related. We organize a hierarchy of topological complexity for the structure of foreign keys, based on a modeling of schemata as graphs, where tables are classified in increasing order of complexity as: isolated (not involved in foreign keys), source (with outgoing foreign keys only), lookup (with incoming foreign keys only) and internal (with both kinds). Our study reveals that this hierarchy reflects also the update behavior of tables: topologically simple tables are more likely to have a life with few or zero schema updates, whereas, topologically complex tables are more likely to undergo high numbers of updates. Early versions of the database attract the large majority of births of complex tables, as opposed to the simple ones, demonstrating a pattern of reducing the introduction of complex, heavily updated constructs in the schema as time progresses.
Konstantinos Dimolikas, Apostolos V. Zarras, Panos Vassiliadis. A study on the effect of a table's involvement in foreign keys to its schema evolution. 39th International Conference on Conceptual Modeling (ER 2020), Nov. 3-6, 2020, Vienna.
Focus: Shows that tables with more complex foreign-key topology tend to undergo more schema updates, while structurally simple tables are more often stable.
DOI: 10.1007/978-3-030-62522-1_34.
Related material: local page for A Study on the Effect of a Table's Involvement in Foreign Keys to its Schema Evolution with paper, video presentation, and related material.
An 8' teaser video with just the key highlights, and a lengthier, full-fledged presentation of the paper
Panos Vassiliadis, Michail-Romanos Kolozoff, Maria Zerva, Apostolos V. Zarras. Schema evolution and foreign keys: a study on usage, heartbeat of change and relationship of foreign keys to table activity. Computing, Volume 101, Issue 10, pp 1431–1456, October 2019. 2019.
Focus: Studies foreign-key evolution at schema and table level, revealing widely different foreign-key usage practices and linking table connectivity in the Diachronic Graph to survival and update activity.
DOI: 10.1007/s00607-019-00702-x.
Related material: local page for Schema evolution and foreign keys with paper and supplementary material; Springer read-only version.
Panos Vassiliadis, Michail-Romanos Kolozoff, Maria Zerva, Apostolos V. Zarras. Schema Evolution and Foreign Keys: Birth, Eviction, Change and Absence. 36th International Conference on Conceptual Modeling (ER 2017), pp. 106-119, Nov. 6th-9th, 2017, Valencia Spain.
Focus: Examines the birth, removal, change, and absence of foreign keys across evolving database schemata, exposing markedly different practices in how projects maintain referential structure.
DOI: 10.1007/978-3-319-69904-2_9.
Related material: local page for Schema Evolution and Foreign Keys: Birth, Eviction, Change and Absence with paper, video presentation, and related material.