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