A goal of database reverse engineering techniques is the extraction of a conceptual model describing an otherwise complex or obtuse database system. In such contexts, and notably, when applied to legacy databases, thorough preservation of the knowledge lying in the source schema is a reasonable priority. In the common database reverse engineering pipeline, database normalization is the process in which we are most able to dictate and maintain the information preservation property. We make use of the transformation pattern formalism as our base to guarantee information preservation. We present how these theoretical templates can be applied over complex database schema and how they can serve as the foundation of an automatic, deterministic database normalization methodology.
methodology and served more as guidance for database engineer. To illustrate the various sections of the methodology we provide the following ongoing example Fig. 1: ∶ (, ℎ, , , , , ) onto which are applied several constraints: - a primary key on denoted by a bold underline - a functional dependency → , written with a top single arrow - another functional dependency → , this time restrained to tuples satisfying a condition , ≠ NULL requiring both attributes to be non-null - a multivalued dependency ↠ ℎ signed with a top double-headed arrow and finally - two inclusion dependency ⊆ and ⊆ , both shown as bottoms arrows.
Using transformation patterns as our base, we propose a methodology based on them for automatic database normalization. It starts with a primer on information capacity and what leads us to focus on TPs as a means of preserving knowledge with no loss. Once we present how these restrictive patterns could be applied to more complex schemas, we describe a methodology to remove all null values and all join dependencies from the source schema via schema decompositions. For closure, we contextualize our work among the many adjacent fields it grazes before discussing our future application of transformation patterns.
At its core, most of the literature regarding the preservation of information during a schema
transformation emerged from Hull’s [
A genesis of schema dominance can be found in [
Walking in [
For readability, we write those FO Mappings in relational algebra. We can now translate the previous definitions of schema dominance by interchanging schema transformation with FO mappings. Thus resulting in the notion of FO Dominance, informally a schema FO Dominate another schema if dominates via mapping functions → and → written as FO Mappings. Using the FOS notation, we can also write FO Dominance as such (C ∪ → ) ⊧ (C ∪ →) This lead to this final definition of Losslessness; Definition 5 (Losslessness). Let and be two first-order schemas, if FO Dominates and FO Dominates , then and are the lossless representations of each other. A result which we can also write as (C ∪ → ) ≡ (C ∪ →)
Transformation patterns [
Worker SSN 012-3155 012-3155 024-5143 031-7471 040-5166 040-5166
First, we need a way to represent () in our formalism, and it starts with expressing that is nullable. A condition over a set of attributes is commonly written as ≠ ∅ in a TP to denote that in the relation , tuples satisfying could exists. This is called a guard constraint. They can also express conditions that either always hold or never do by writing = and = ∅ respectively. In our example, the nullable attribute manager would be written as such =NULL ≠ ∅. Put as a database pattern, we have a constraint pattern =NULL ≠ ∅ applying over a set of attributes , coalescing with any other number of unrelated attributes captured as the into the relation pattern ∶ ( , ). This is the first half of a transformation pattern, the part onto which we can match our relation . The second part denotes instead the two tables where is either always null or non-null. Once again, in our formalism, these two conditions are expressed as =NULL1 = ∅ and =NULL2 = 2 for is never satisfied and is always satisfied respectively. From these conditions, we can deduce two relation patterns 1 ∶ ( , ) and 2 ∶ ( ). Finally, its mapping patterns is two sets of FO-Mappings 1 = ≠NULL(), 2 = Π ( =NULL()) and = 1 ⊍ 2. These mappings uses standards relational algebra notation plus the outer union operation denoted by ⊍. The full TP is shown in Fig. 2 () where an additional constraint is used to capture residual constraints, a notion developed in the next section. Applying this TP over our relation requires to match the variables in the former with the attributes in the latter. To do so, has to be rewritten as an FOS so that its semantics can match those of any TPs. Here, this match is trivial and it is quickly deduced that = {} and = {, ℎ, }. We call a transformation pattern, a database pattern or a mapping pattern instantiated once it has been matched with real values from a database schema. (a) TP for Horizontal Decomposition (b) TP for Vertical Decomposition of a MVD
The decomposition resulting from a TP application can be expressed as a set of views. This
is crucial when working with legacy databases or in cases where it’s neither practical nor
desirable to actively modify the source database. And because the transformations are lossless
and thus preserve information capacity, it is possible to update the source database from any of
its equivalent views [
One thing missing for the application of TPs is a proper understanding of the constraint and more generally of the process of constraint propagation. If we added (︀ ︀⌋( , ℎ) and (︀ ︀⌋( ) to the relation used in last example, then they would be considered as residual constraints in the application of the TP ) in Fig. 2 and assigned to both and as constraints over . Here, and separate the residual constraints applied over all variables satisfying and those that do not, respectively. Such basic propagation seems straightforward in our example but as we apply TPs over databases containing several tables, all linked via foreign keys, then we need to have a proper propagation methodology. One that has two main objectives: -matching the TP and the database schema and - merging the newly decomposed schema with the rest of the old one. In Fig. 3 we present the main components of a successful pattern application, this time starting with a vertical decomposition following ↠ ℎ (see Fig. 2 ()) and showing how this afect the attribute .
Here, Σ denote the mapping function between the source database and the desired TP, matching with . The mapping is trivial when only one constraint needs to be matched. Once the TP is applied and we have a decomposition in , we need to merge this new database schema with the previous one, propagating all constraints from the latter in the process. We call the constraints left behind after the application of a TP leftover constraints. In Fig. 3, the leftover constraint is the guard constraint =NULL ≠ ∅. The propagation of those leftover constraints, and of their associated tables is done via a set of rules defined in the merging function Σ . Later on, we will introduce further rules when dealing with overlapping guard constraints, a then-defined notion, but for now, the three most important rules are: • Basic Propagation: If a leftover constraint applies over a set of attributes found again in , then it is propagated fully. • Inclusion Update: Following a vertical decomposition, any inclusion dependencies over a set of attributes captured by the TP will get updated by changing the relations it applies over (i.e., one of the newly generated relations). • Inclusion Split: Following a horizontal decomposition, a previously total inclusion dependency (=) will split into two subset dependencies (⊆) with the corresponding new relations names.
Now that we have an intuitive base to process multiple TPs it is time to move on to our proposed decomposition methodology.
Stemming out DBRE, TPs theory takes roots deeper inside the field of Database Normalization
[
We preemptively create a singleton table based on the right-hand side of an inclusion dependency, then change that constraint to target the newly generated table. In the database schema made of ∶ (, ℎ, ) and ⊆︀( , ︀⌋( , ) decomposing into ′ makes ∶ (, ℎ, ) ∶ ( ) and ⊆︀( , ⌋︀( , ). In the cases of transitive inclusion dependencies or sets of inclusion dependencies sharing the same right-hand side, additional patterns are necessary, some illustrated in Figure. 4.
Vertical Decomposition (VD) is one of the core operations along with horizontal decompositions. Its principle is to project into a new table all attributes present in the join constraint and to drop its right-hand-side attributes from the source relation. This applies to either a functional dependency or a multivalued dependency and both have their kind of TPs, see Fig. 2 () for the latter. The TP defining the vertical decomposition of a relation ∶ (, , ), with regards to a join dependency we write as (︀ ︀⌋( , ), always generate 1 ∶ (, ), 2 ∶ (, ), a full inclusion between the tables =︀( 1, 2⌋︀( , ) and ends with this constraint (︀ ︀⌋( ) or (︀ ︀⌋( , ) for functional dependency or multivalued dependency, respectively, see Fig. 5. This figure also depicts the transformation done to our ongoing example.
In this scenario, no sequencing is required and both decomposition can be done independently from the other. Independent in this context means that a pair of constraints 1, 2 are in none of the three following combinations: shared RHS, transitive and critical.
Decomposing a set of overlapping constraints 1, 2, ..., of the form = (︀ ︀⌋( , ) such that 1 ∧ 2 ∧ ... ∧ ≠ ∅ require a TP which preserve the greatest common subset of attributes in the right-hand side at each step. To illustrate, the greatest common denominator for the set 1 = → , 2 = → , 3 = ↠ in the relation ∶ (, , , , , ) where we choose to start by projecting 1 is , whereas for 2 it would be . The decomposed schema for both scenarios are 1 ∶ (, , , , , ), 2 ∶ (, ) and 1′ ∶ (, , , , ), 2′ ∶ (, , , ) respectively.
Unlike the previous overlap, transitive overlaps do not require any new TPs. What they require however is an ordering of the decompositions. It is quite clear how, without any ordering, we lose information contained in ∶ (, , ), 1 = → , 2 = → by decomposing 1 ifrst ending on 1 ∶ (, ) 2 ∶ (, ) thus losing 2. The ordering we advocate is a relatively simple one in which, borrowing some tree terminology, all decompositions should start from the leaves then upward.
The last cases of overlap we have to detect are the critical ones. We borrow our definition of
critical constraints from [
Going further than most database normalization methodologies we propose the use of TPs, such as the one presented in Fig. 2, to express Horizontal Decomposition (HD) with for intent to remove null values from a database schema. We already introduced guard constraint in our example section and now expend on its condition . That latter is a conjunction of atomic conditions ⋀( ≠ NULL). As long as all guard constraints are independent of each other, the decomposition methodology is trivial and deterministic. To verify if this property also extends to overlapping guard constraints, we first need to define them.
Definition 6 (Guard Overlaps). In a relation ∶ ( ) onto which are applied two constraints =NULL ≠ ∅ and =NULL ≠ ∅ where, , ⊆ . We distinguish two types of overlap: • Containment: ⊂ • Non-Distinct: ∧ ≠ ∅, ⊂⇑ and ⊂⇑
We illustrate these two cases with an example: there be ∶ (, , , ) and three overlapping guard constraints 1 = =NULL ≠ ∅, 2 = =NULL ≠ ∅ and 3 = =NULL ≠ ∅. Both scenarios are shown with the pairs {1, 2} and {1, 3} clearly demonstrating the containment and non-distinct cases respectively. Focusing on the containment case, starting with an HD on 1 will result in two relations 1 ∶ (, , , ) and 2 ∶ (, ), one where no tuples satisfy = NULL and one where all does. The constraint propagation formula we presented in Section 3 dictates that 2 and 3 would hold in both relations which is impossible for 2. This is why we need two additional rules: • Guard Loss: 1 ≠ ∅ do not get propagated in ′ if ′ contains one of the following constraints 2 = ∅, 2 = for 2 ⊂ 1 and 1 ⊂ 2 respectively. • Guard Intuition: 1 ≠ ∅ get propagated in ′ even if 2 = holds, with 1 ⊂⇑ 2 and 1 ∧ 2 ≠ ∅.
The intuition behind the first rule is that a constraint can only get propagated if it is not directly contradicted by another. What the other rules allow is for nullable conditions to hold in a table where a subset of the attribute in said condition is non-existent. In our example, this permits 3 to be propagated to 2 even though this table is missing the column. Adding these rules to the one previously described leads to the following result: Lemma 1. All sequences of horizontal decompositions are lossless and their schema outputs are equivalents.
Proof 1. We want to show that for any binary relation HD( 1, 2) representing the sequential application of HD TPs 1 → 2, then HD is symmetric. Losslessness is already guaranteed by the TP formalism, so only the deterministic aspect is touched. This property is trivial when it comes to independent guard constraints so we test it on both kinds of overlaps. Using the same notation used in the definition, in the containment case starting with a decomposition on the subsumed constraints gives 1 ∶ ( ) and 2 ∶ ( ). The second decomposition here only afects 2 because of the guard loss property, giving a final decomposition of 1, 2 and 3 ∶ ( ). Starting from 2 would instead give us first 1′ ∶ ( ) and 2′ ∶ ( ) and 1 here only afect 1′ because of the guard loss property giving for final decomposition 1′, 2′ and 3′ ∶ ( ). Both decompositions are the same, thus demonstrating the symmetric property of HD in this scenario. A similar logic is applied for non-distinct guard overlaps and the same result, that is 1 ∶ ( ), 2 ∶ ( ), 3 ∶ ( ), 4 ∶ ( ( ⋃ )) is found in all sequences. ◻
Because all possible scenarios of overlap over guard constraints can be represented, our methodology for their decomposition is complete. We can mention a specific case where one or more overlapping guard constraints exist and the union of their set of attributes 1 ⋃ ... ⋃ = is the size of the attribute set in . In this case, the relation satisfying all guard constraints would just be an empty table ∅ with constraints of the form =NULL∅ = ∅. This is unnecessary and can be resolved by adding a last propagation rule: • Guard Total: 1 ≠ ∅ with 1 over gets propagated as 1 = ∅ in ′ if ⊆ .
A Conditional Function Dependency, defined in [ 15], is, within our formalism, a dependency (︀ ︀⌋( )( ) of type which only gets applied over tuples that satisfy . We return to our ongoing example, shorten this time as ∶ (, , ) onto which is applied a condition functional dependency 1 = (︀ ︀⌋( , )(, ≠ NULL). The functional dependency → holds only whenever and are both non-null. If only one CVD is applied we refer to the Fig. 6 instantiated with our recurring example. Otherwise, for any set of conditional dependencies, overlapping or not, we always start with all HDs followed by all VDs, respecting both methodologies for overlap along the way.
The final order is: IDE → VD → CVD → HD. What results is a pair of mapping patterns between an FOS schema and its equivalent 4NF decomposition, the latter shown in Fig. 7.
It is uncertain if a potential decomposition into 5NF and higher can be deterministic, meaning that any further process is likely to be semi-automatic. The end goal being a fully decomposed schema in 6NF which can easily be translated into a conceptual modeling language. Such process is prone to the arbitrary as is the nature of conceptual models. To illustrate, we argue for a new table _ ∶ (, ) to be added to our schema as it reflects better the relation between and and for the drop of in the workers tables. Taking inspiration from conceptual modeling operations, such as attribute generalization in this case, to create new TPs is something I already encouraged in [16]. Another challenges is to properly draw out concepts from our database schema, an action fitting for TPs turning database schema into their ARM equivalents.
With regards to the rest of the literature on DBRE [17], ignoring the aggregation of knowledge
from diferent sources and the type of output, the closest method to ours would be [ 18]. This
approach also emphasizes the preservation of information, but we believe that shifting to an
ontological formalism limits the kind of operations we can apply over the source database,
notably direct updates from any point in the framework. Several papers presented their own
interpretation to Hull’s information preservation criterion [
Throughout the literature provided so far, one common scenario outside of DBRE in which information preservation is desirable is in data integration [22]. Because most database transformations are written as mappings, ours included, it is quite intuitive to link them to the mappings used in data integration following either Global as View (GAV) or Local as View (LAV) paradigms. [23] notably proposed a framework based on sequences of simple operations to represent more complex transformations in a data integration context. Delving deeper into information preservation with regard to data integration can lead us to consider methodologies used in data exchange [24]. While the main focus of data exchange is the generation of a proper database instance from constraints, the problem of schema exchange introduced in [25] is closer to our ambitions. Mostly with regards to the grouping of similar schemas into templates making an automatic schema transformation possible.
We presented a case study for the application of the transformation pattern formalism. Showing ifrst how it can be applied to a database schema before asserting that it can serve as the base of a database decomposition process. Any database schema, once translated into FOS, can then be decomposed following a sequence of lossless transformations embodied by the TPs. What result is a pair of mapping patterns between the source database and its equivalent 4NF decomposition. The presented methodology places itself in the context of the SQL Semantic Transducer [26] in which the conceptual model of a database schema can act as its materialized view. Meaning that, once the jump from 6NF to any conceptual modeling language is done, queries and updates applied to the model would get propagated back to the source database. And so would the reverse, a property only guarantee because losslessness was preserved through the entire process. Upcoming works will therefore focus on transitions into both 6NF then to a conceptual model, likely going through an ARM schema in the process. Going further, we consider frameworks ensuring losslessness appealing to other database related fields such as data integration and data preparation. Both handle transformations where information loss is unavoidable, thus requiring both a definition of non-lossless, i.e. lossy, TPs and ways to enforce losslessness still, perhaps taking inspiration from the complementary view problem. [15] W. Fan, F. Geerts, X. Jia, A. Kementsietsidis, Conditional functional dependencies for capturing data inconsistencies, ACM Transactions on Database Systems 33 (2008) 1–48.
URL: https://dl.acm.org/doi/10.1145/1366102.1366103. doi:10.1145/1366102.1366103. [16] T. Abgrall, Formalization of Data Integration Transformations, in: S. Chiusano, T. Cerquitelli, R. Wrembel, K. Nørvåg, B. Catania, G. Vargas-Solar, E. Zumpano (Eds.), New Trends in Database and Information Systems, volume 1652, Springer International Publishing, Cham, 2022, pp. 615–622. URL: https://link.springer.com/10.1007/978-3-031-15743-1_ 56. doi:10.1007/978-3-031-15743-1_56, series Title: Communications in Computer and Information Science. [17] N. A. Mian, S. A. Khan, N. A. Zafar, Database Reverse Engineering Methods: What is
Missing? 2 (2013). [18] L. Lubyte, S. Tessaris, Automatic Extraction of Ontologies Wrapping Relational Data Sources, in: S. S. Bhowmick, J. Küng, R. Wagner (Eds.), Database and Expert Systems Applications, volume 5690, Springer Berlin Heidelberg, Berlin, Heidelberg, 2009, pp. 128–142. URL: http://link.springer.com/10.1007/978-3-642-03573-9_10. doi:10.1007/ 978-3-642-03573-9_10, series Title: Lecture Notes in Computer Science. [19] L. Ekenberg, P. Johannesson, Conflictfreeness as a basis for schema integration, in: International Conference on Information Systems and Management of Data, Springer, 1995, pp. 1–13. [20] P. McBrien, A. Poulovassilis, A formalisation of semantic schema integration, Information
Systems 23 (1998) 307–334. [21] I. Kobayashi, Losslessness and semantic correctness of database schema transformation: Another look of schema equivalence, Information Systems 11 (1986) 41–59. URL: https: //linkinghub.elsevier.com/retrieve/pii/0306437986900220. doi:10.1016/0306-4379(86) 90022-0. [22] A. Doan, A. Halevy, Z. Ives, Principles of data integration, Elsevier, 2012. [23] P. McBrien, A. Poulovassilis, Data integration by bi-directional schema transformation rules, in: Proceedings 19th International Conference on Data Engineering (Cat. No.03CH37405), IEEE, Bangalore, India, 2003, pp. 227–238. URL: http://ieeexplore.ieee.org/ document/1260795/. doi:10.1109/ICDE.2003.1260795. [24] R. Fagin, P. G. Kolaitis, R. J. Miller, L. Popa, Data exchange: semantics and query answering, Theoretical Computer Science 336 (2005) 89–124. URL: https://linkinghub.elsevier.com/ retrieve/pii/S030439750400725X. doi:10.1016/j.tcs.2004.10.033. [25] P. Papotti, R. Torlone, Schema exchange: Generic mappings for transforming data and metadata, Data & Knowledge Engineering 68 (2009) 665–682. URL: https://linkinghub. elsevier.com/retrieve/pii/S0169023X09000184. doi:10.1016/j.datak.2009.02.005. [26] T. Abgrall, E. Franconi, Understanding the sql semantic transducer, in: International Conference on Advanced Information Systems Engineering, Springer, 2024.