Data and Process Modelling 6. Schema Transformations Marco Montali KRDB Research Centre for Knowledge and Data Faculty of Computer Science Free University of Bozen-Bolzano A.Y. 2013/2014 Marco Montali (unibz) DPM - 6.Transformations A.Y. 2013/2014 1 / 29 One Schema, Many Schemas • The same domain may be mirrored in many (equivalent) conceptual schemas. I Equivalence means having the same intended models. • The same conceptual schema may be mapped to different logical schemas. • The same logical schema may be physically realized in different ways. Questions How to transform a conceptual schema into an equivalent conceptual schema? How to choose the “optimal” representation, considering in particular efficiency of database access? Example: Persons and their Vices (on the whiteboard). Marco Montali (unibz) DPM - 6.Transformations A.Y. 2013/2014 2 / 29 Predicate Specialization/Generalization The transformation of a conceptual schema into an equivalent schema that substitutes a predicate with a more specific/general predicate, still preserving the key constraints. Applied when the predicate has a finite number of cases, i.e.: • is subject to a value constraint, or • is subject to a frequency constraint. Marco Montali (unibz) DPM - 6.Transformations A.Y. 2013/2014 3 / 29 Predicate Specialization/Generalization 1 PSG1 S1 {b1,...,bn} A1 Am B R ... A1 Am Sn • m≥1 • Si corresponds to R with B instantiated with bi Constraints have to be suitably translated as well. See following corollaries (shown with ternary fact types, but they hold for any arity). Marco Montali (unibz) DPM - 6.Transformations A.Y. 2013/2014 4 / 29 Predicate Specialization/Generalization 1 UC over B’s role (and others). PSG1 - Corollary 1 S1 {b1,...,bn} A1 A2 B R Marco Montali (unibz) ... A1 A2 Sn DPM - 6.Transformations A.Y. 2013/2014 5 / 29 Predicate Specialization/Generalization 1 UC over all roles but B’s. PSG1 - Corollary 2 {b1,...,bn} A1 A2 S1 B R Marco Montali (unibz) ... A1 A2 Sn DPM - 6.Transformations A.Y. 2013/2014 6 / 29 Predicate Specialization/Generalization 1 Mandatory participation of an entity type. PSG1 - Corollary 3 S1 {b1,...,bn} A1 A2 B R ... A1 A2 Sn Works also for a mandatory role disjunction of an entity type. • Remember that the same entity type can play multiple roles in the same fact type. Marco Montali (unibz) DPM - 6.Transformations A.Y. 2013/2014 7 / 29 Predicate Specialization/Generalization 1 Optional participation with frequency constraint. PSG1 - Corollary 4 S1 {b1,...,bn} A1 A2 B n R Marco Montali (unibz) ... A1 A2 Sn DPM - 6.Transformations A.Y. 2013/2014 8 / 29 Predicate Specialization/Generalization 1 Mandatory participation with frequency constraint. PSG1 - Corollary 5 S1 {b1,...,bn} A1 A2 B n R Marco Montali (unibz) ... A1 A2 Sn DPM - 6.Transformations A.Y. 2013/2014 9 / 29 Predicate Specialization/Generalization 2 PSG2 {b1,...,bn} S1 T B ... A A C C R Sn • Si corresponds to R where T is restricted to instance bi of B. Marco Montali (unibz) DPM - 6.Transformations A.Y. 2013/2014 10 / 29 Predicate Specialization/Generalization 2 Mandatory roles of A. PSG2 - Corollary 1 {b1,...,bn} S1 T B ... A A C C R Marco Montali (unibz) Sn DPM - 6.Transformations A.Y. 2013/2014 11 / 29 Predicate Specialization/Generalization 2 External UC over B and C. PSG1 - Corollary 2 {b1,...,bn} S1 T B ... A A C C R Marco Montali (unibz) Sn DPM - 6.Transformations A.Y. 2013/2014 12 / 29 Predicate Specialization/Generalization 2 Mandatory participation of C. PSG1 - Corollary 3 {b1,...,bn} S1 T B ... A A C C R Marco Montali (unibz) Sn DPM - 6.Transformations A.Y. 2013/2014 13 / 29 Predicate Specialization/Generalization 3 A non-equivalent transformation. • From left to right: weakening. • From right to left: strengthening. PSG3 S1 ... A <n A B R B Sn • Each Si corresponds to one instance of R. Marco Montali (unibz) DPM - 6.Transformations A.Y. 2013/2014 14 / 29 Predicate Specialization/Generalization 3 Equality constraint on A’s roles. PSG3 - Corollary 1 S1 ... A n A B R B Sn Marco Montali (unibz) DPM - 6.Transformations A.Y. 2013/2014 15 / 29 Nested/Flat Predicates N.B.: we already saw the correspondence between nesting and co-reference. N/F T B C A A R S C B where Rabc if and only if (a,b)T c. Marco Montali (unibz) DPM - 6.Transformations A.Y. 2013/2014 16 / 29 Nested/Flat Predicates UC over nested roles. N/F - Corollary 1 T B C A A R Marco Montali (unibz) DPM - 6.Transformations S C B A.Y. 2013/2014 17 / 29 Nested/Flat Predicates UC over a nested and non-nested role. N/F - Corollary 2 T B C A A R T C A R Marco Montali (unibz) B S B DPM - 6.Transformations A S C C B A.Y. 2013/2014 18 / 29 Nested/Flat Predicates - Extended Ext. N/F R A A C U B S C T V D D B where: • Rabc if and only if (a,b)U c. • Sabc if and only if (a,b)V c. • T = R[a,b] ∪ S[a,b]. Marco Montali (unibz) DPM - 6.Transformations A.Y. 2013/2014 19 / 29 Nested/Flat Predicates - Extended UC just over nested roles. Ext. N/F - Corollary 1 R A A C B S U C T V D D B R A S A C B U C T V D D B Marco Montali (unibz) DPM - 6.Transformations A.Y. 2013/2014 20 / 29 Nested/Flat Predicates - Extended Pair-subset constraint. Ext. N/F - Corollary 2 R A S A C B U C T V D D B Marco Montali (unibz) DPM - 6.Transformations A.Y. 2013/2014 21 / 29 Nested/Flat Predicates - Extended Pair-equality constraint. Ext. N/F - Corollary 3 R A S A C B U C T V D D B Marco Montali (unibz) DPM - 6.Transformations A.Y. 2013/2014 22 / 29 Nested/Flat Predicates - Extended Pair-exclusion constraint. Ext. N/F - Corollary 4 R A S A C B U C T V D D B Marco Montali (unibz) DPM - 6.Transformations A.Y. 2013/2014 23 / 29 Overlap Algorithm Guides nesting when two or more fact types contain compatible role sequences (of at least two roles), with (possible) overlapping tuples. The algorithm has two parameters: 1. Amount of overlapping: one subset of the others, total overlapping, no overlapping, possible overlapping. I Determined by the constraint attached to the role sequence 2. Role sequences cover the entire relation (whole relation) vs they are just a projection of larger relations (partial relation). Marco Montali (unibz) DPM - 6.Transformations A.Y. 2013/2014 24 / 29 Overlap Algorithm - Case 1 Q B A P 1. Objectify Q. 2. If Q is partial Then 2.1 Attach rest of its predicate via mandatory extra role. 3. If P is partial Then 3.1 Attach rest of its predicate via mandatory extra role. Else 3.2 Attach optional unary role “is-P”. Marco Montali (unibz) DPM - 6.Transformations A.Y. 2013/2014 25 / 29 Overlap Algorithm - Case 2 Q B A P 1. If P or Q is partial Then 1.1 Objectify the single predicate “P and Q”. 1.2 Attach rest of their predicates via mandatory extra role(s). Else 1.3 Replace both P and Q with a single binary predicate “P and Q”. Marco Montali (unibz) DPM - 6.Transformations A.Y. 2013/2014 26 / 29 Overlap Algorithm - Case 3 Q B A P 1. Objectify “P or Q”. 2. If P is partial Then 2.1 Attach rest of its predicate via optional extra role. Else 2.2 Attach unary role “is-P”. 3. Do the same with Q. 4. Mark the attached roles with an exclusive and disjunctively mandatory constraint. Marco Montali (unibz) DPM - 6.Transformations A.Y. 2013/2014 27 / 29 Overlap Algorithm - Case 4 Q B A P 1. Objectify “P or Q”. 2. If P is partial Then 2.1 Attach rest of its predicate via optional extra role. Else 2.2 Attach unary role “is-P”. 3. Do the same with Q. 4. Mark the attached roles with a disjunctively mandatory constraint. Marco Montali (unibz) DPM - 6.Transformations A.Y. 2013/2014 28 / 29 Schema Optimization The transformation of a conceptual schema into an alternative conceptual schema that maps more efficiently to a relational schema. Four factors are involved: 1. Target system (which technology used to deploy the system). 2. Query pattern (which questions the system must be able to answer). 3. Update pattern (which expected insertions, deletions, modifications). 4. Clarity (to which extent the obtained relational schema is understandable). Two main steps: 1. Reduce the number of mapped tables. 2. Simplify individual tables. Example On the whiteboard! Marco Montali (unibz) DPM - 6.Transformations A.Y. 2013/2014 29 / 29

Scarica
# Data and Process Modelling - 6. Schema Transformations