First, we will consider these two types of fragmentation separately and then consider the more complex fragmentation that can be obtained by applying a combination of these two types.
In all types of fragmentation, a fragment can be specified by an expression in a relational database language (here, we will use relational algebra) that takes global relations as operands and produces a fragment as the result. For example, if a global relation NV contains data for employees, a fragment containing only data for employees with the title “Department Manager” can be specified by a selection operation on the global relation CV= “Department Manager” (NV) ).
In data normalization, we have some rules to ensure consistency.
of the database. It is important to note that data fragmentation for data distribution (especially vertical fragmentation) is similar to normalization of relations. Therefore, we can define fragmentation rules similar to the principles of data normalization. Data fragmentation must satisfy the following three rules to ensure that the database does not change semantically during fragmentation. These rules are called correctness conditions.
2.1.1. Correct conditions for data fragmentation
1) Complete conditions
If a relation R is decomposed into fragments R 1 , R 2 , …, R n , each data item can be found in one or more fragments R i . This property is similar to the lossless decompostion property of data normalization and is also important in fragmentation, because it ensures that the data in a global relation is mapped into the fragments without loss.
- Item data in:
+ horizontal fragmentation is a tuple
+ vertical fragmentation is a property
- Condition:
+ Horizontal fragmentation:
u R , i [1 , n ]: u R i
+ Vertical fragmentation:
A Attr(R), i [1,n]: A Attr(R i ) with Attr(R) being the set of attributes of R.
2) Reconstruction condition
If a relation R is decomposed into fragments R 1 , R 2 , …, R n , it is always possible to define a relational operation so that:
R = R i , R i F R
Math will be different for each different type of fragmentation; however, it is important that it be defined. In the case of horizontal fragmentation, the
is the union ( ), in the case of vertical fragmentation, the operation ( ) is the connection ( ).
- Horizontal fragmentation:
R = R 1 R 2 … R n
- Vertical fragmentation:
R = R 1 R 2 …R n
The reconstructability of a relation from its fragments ensures that data dependency constraints are preserved. In practice, only fragments are stored in a distributed database, and the global relation must be reconstructed using the operation.this, if necessary.
3) Disjointness condition
If a relation R is horizontally fragmented into fragments R 1 , R 2 ,…, R n and a data item d i is present in R i then it is not present in any other fragment R k (k i). This condition ensures that the horizontal fragments are distinct. that is:
i k and i , k [1,n]: R i R k = .
If relation R is vertically fragmented, typically the primary key attributes are present in all its fragments; this condition is often violated. The disjoint condition ensures that data replication can be explicitly controlled at the allocation level.
2.1.2. Horizontal fragmentation
1) Main horizontal fragmentation
Primary horizontal fragmentation is the division of tuples of a global relation into subsets based on the attributes of this relation, each subset is called a horizontal fragment.
Obviously, this is useful in distributed databases, where each subset can contain data that has common properties.
- Main horizontal fragmentation representation:
F (R)
where: F is the selection condition
R is a global relation.
- Predicate:
+ We call the selection condition in a selection a predicate.
+ We call the predicate defined in the selection to determine a piece a qualification predicate.
+ Convention: q i = F i
Example 2.1: Consider the project management system of a software development company in Example 1.5. Suppose the company has offices in Nam Dinh, Hanoi.
SKIN
Set
MADA | TENDA | NS | VT | |
u 1 | D1 | Building payroll management software | 20000 | Nam Dinh |
u 2 | D2 | Website design for sale | 12000 | Hanoi |
u 3 | D3 | Network upgrade | 28000 | Hanoi |
u 4 | D4 | Building score management software | 25000 | Nam Dinh |
u 5 | D5 | Building a financial management system | 30000 | Hanoi |
Maybe you are interested!
-
Table of Data Converted to Logarithm Base E -
Comparison of Geographical Conditions, Structure of Culture and Tourism Activities -
Summary Table of Data Illustrating the Contents of the Thesis -
Summary of Sem Linear Structural Model Data -
Basic Conditions for Implementing Solutions
a) For application 1, the main horizontal fragmentation of the global relation DA is determined as follows:
DA 1 = VT = “Nam Dinh” (DA)
DA 2 = VT = “Hanoi” (DA)
Therefore, the qualitative predicates are:
q 1 : VT = “Nam Dinh” q 2 : VT = “Hanoi”
Result of the pieces:
DA 1
MADA
TENDA | NS | VT | |
D1 | Building payroll management software | 20000 | Nam Dinh |
D4 | Building score management software | 25000 | Nam Dinh |
DA 2
MADA
TENDA | NS | VT | |
D2 | Website design for sale | 12000 | Hanoi |
D3 | Network upgrade | 28000 | Hanoi |
D5 | Building a financial management system | 30000 | Hanoi |
Consider the correct conditions for primary horizontal fragmentation:
- Full conditions
+ u 1 DA: u 1 DA 1
+ u 2 DA: u 2 DA 2
+ u 3 DA: u 3 DA 2
+ u 4 DA: u 4 DA 1
+ u 5 DA: u 5 DA 2
Therefore full conditions are guaranteed.
- Regeneration conditions
DA = DA 1 DA 2
Therefore, the regeneration conditions are guaranteed.
- Condition for separating DA 1 DA 2 =
Thus the condition of separation is guaranteed.
b) For application 1 and application 2, the main horizontal fragmentation of the global relation DA is determined as follows:
DA 1 = (VT = “Nam Dinh”) (NS >20000) (DA)
DA 2 = (VT = “Nam Dinh”) (NS ≤ 20000) (DA) DA 3 = (VT = “Hanoi”) (NS >20000) (DA) DA 4 = (VT = “Hanoi”) (NS ≤ 20000) (DA)
Therefore, the qualitative predicates are:
q 1 : VT = “Nam Dinh” NS >20000
q 2 : VT = “Nam Dinh” NS ≤ 20000 q 3 : VT = “Hanoi” NS >20000
q 4 : VT = “Hanoi” NS ≤ 20000
Result of the pieces:
DA 1
MADA
TENDA | NS | VT | |
D4 | Building score management software | 25000 | Nam Dinh |
DA 2
MADA
TENDA | NS | VT | |
D1 | Building payroll management software | 20000 | Nam Dinh |
DA 3
MADA
TENDA | NS | VT | |
D3 | Network upgrade | 28000 | Hanoi |
D5 | Building a financial management system | 30000 | Hanoi |
DA 4
MADA
TENDA | NS | VT | |
D2 | Website design for sale | 12000 | Hanoi |
Consider the correct conditions for primary horizontal fragmentation:
- Full conditions
+ u 1 DA: u 1 DA 2
+ u 2 DA: u 2 DA 4
+ u 3 DA: u 3 DA 3
+ u 4 DA: u 4 DA 1
+ u 5 DA: u 5 DA 3
Therefore full conditions are guaranteed.
- Regeneration conditions
DA = DA 1 DA 2 DA 3 DA 4
Therefore, regeneration conditions are guaranteed.
- Separation conditions
+ DA 1 DA 2 = DA 2 DA 3 =
+ DA 1 DA 3 = DA 2 DA 4 =
+ DA 1 DA 4 = DA 3 DA 4 =
Thus the condition of separation is guaranteed.
Example 2.2: Consider the project management system of a software development company in example 1.5. Suppose the company has offices in Nam Dinh, Hanoi, and Can Tho.
SKIN
Set
MADA | TENDA | NS | VT | |
u 1 | D1 | Building payroll management software | 20000 | Nam Dinh |
u 2 | D2 | Website design for sale | 12000 | Hanoi |
u 3 | D3 | Network upgrade | 28000 | Hanoi |
u 4 | D4 | Building score management software | 25000 | Nam Dinh |
u 5 | D5 | Building a financial management system | 30000 | Hanoi |
u 6 | D6 | Credit system development | 10000 | Can Tho |
Suppose the global relation DA is fragmented as follows:
DA 1 = VT = “Can Tho” (DA) DA 2 = VT = “Hanoi” (DA)
Therefore, the qualitative predicates are:
q 1 : VT = “Can Tho” q 2 : VT = “Hanoi”
Result of the pieces:
DA 1
MADA
TENDA | NS | VT | |
D6 | Credit system development | 10000 | Can Tho |
DA 2
MADA
TENDA | NS | VT | |
D2 | Website design for sale | 12000 | Hanoi |
D3 | Network upgrade | 28000 | Hanoi |
D5 | Building a financial management system | 30000 | Hanoi |
The completeness condition is violated because u 1 DA but u 1 DA 1 , u 1 DA 2 . Therefore, the correctness condition for primary horizontal fragmentation is not satisfied.
We can generalize from the above example as follows:
- To satisfy the completeness condition, the set of qualitative predicates of all fragments must be complete, at least for the set of allowed values.
- The regeneration condition is always satisfied through union.
- To satisfy the separate condition, the qualitative predicates must be mutually exclusive.
2) Derived horizontal fragmentation
Derived horizontal fragmentation is the partitioning of tuples of a global relation into subsets (called horizontal fragments) based on the horizontal fragmentation of another relation (called the master relation).
- How to determine a piece: Use a semi-join operation R A B S (= Attr(R) (R A B S))
In there:
+ R is a globally fragmented relation derived from the globally fragmented relation S
+ A R, B S are two attributes that can be compared with each other by the operator
+ ={=, , , , , }
- Qualitative predicates of derived horizontal fragments include:
+ Connection conditions
+ Qualitative predicate of the corresponding main horizontal piece
When a global relation R is horizontally fragmented, the qualitative predicates of its fragments cannot be expressed by predicates using only the properties of R; furthermore, the condition for a tuple t to belong to a given fragment R i of R is that there must exist a tuple t‟ (in which some fragment S i‟ of S) such that t and t‟ satisfy the semijoin condition of the derived horizontal fragmentation.
Example 2.3: Consider the project management system of a software development company in Example 1.5. Suppose the company has offices in Nam Dinh, Hanoi.
Suppose the global relation DA is horizontally fragmented as in Example 2.1. Suppose the global relation HS has the following tuples:
HS
Set
MANV | MADA | NV | TG | |
u 1 | A1 | D1 | Manage | 12 |
u 2 | A2 | D1 | Analysis | 34 |
u 3 | A2 | D2 | Analysis | 6 |
u 4 | A3 | D3 | Technique | 12 |
u 5 | A3 | D4 | Programming | 10 |
u 6 | A4 | D2 | Manage | 6 |
u 7 | A5 | D2 | Manage | 20 |
u 8 | A6 | D4 | Technique | 36 |
u 9 | A7 | D3 | Manage | 48 |
u 10 | A8 | D5 | Programming | 15 |
a) For application 1, the main horizontal fragmentation derived from the HS relation is determined as follows:
HS 1 = HS
HS 2 = HS
Therefore, the qualitative predicates are:
HS.MaDA= DA.MaDA DA 1 HS.MaDA= DA.MaDA DA 2
q 1 : VT = “Nam Dinh” HS.MaDA= DA.MaDA q 2 : VT = “Hanoi” HS.MaDA= DA.MaDA
Results of the derived horizontal fragments:
HS 1
MANV
MADA | NV | TG | |
A1 | D1 | Manage | 12 |
A2 | D1 | Analysis | 34 |
A3 | D4 | Programming | 10 |
A6 | D4 | Technique | 36 |
HS 2
MANV
MADA | NV | TG | |
A2 | D2 | Analysis | 6 |
A3 | D3 | Technique | 12 |
A4 | D2 | Manage | 6 |
A5 | D2 | Manage | 20 |
A7 | D3 | Manage | 48 |
A8 | D5 | Programming | 15 |
Consider the correct condition for derived horizontal fragmentation:
- Full conditions
+ u 1 HS: u 1 HS 1 u 6 HS: u 6 HS 2
+ u 2 HS: u 2 HS 1 u 7 HS: u 7 HS 2
+ u 3 HS: u 3 HS 2 u 8 HS: u 8 HS 1
+ u 4 HS: u 4 HS 2 u 9 HS: u 9 HS 2
+ u 5 HS: u 5 HS 1 u 10 HS: u 10 HS 2
Therefore full conditions are guaranteed.
- Regeneration conditions
HS = HS 1 HS 2
Therefore, the regeneration conditions are guaranteed.
- Conditions for separating HS 1 HS 2 =
Thus the condition of separation is guaranteed.
b) For application 1 and application 2, the main horizontal fragmentation derived from the HS relation is determined as follows:
HS 1 = HS
HS 2 = HS HS 3 = HS HS 4 = HS
Therefore, the qualitative predicates are:
HS.MaDA= DA.MaDA DA 1 HS.MaDA= DA.MaDA DA 2 HS.MaDA= DA.MaDA DA 3 HS.MaDA= DA.MaDA DA 4
q 1 : VT = “Nam Dinh” NS > 20000 HS.MaDA= DA.MaDA q 2 : VT = “Nam Dinh” NS ≤ 20000 HS.MaDA= DA.MaDA q 3 : VT = “Ha Noi” NS >20000 HS.MaDA= DA.MaDA
q 4 : VT = “Hanoi” NS ≤ 20000 HS.MaDA= DA.MaDA
Results of the derived horizontal fragments: