Types of DBMS Fragmentation (TDF)

AVAILABLE:    5

There are two main types of fragmentation: horizontal and vertical, but there are also two additional types: mixed and derived fragmentation.

1. Horizontal Fragmentation

This type of fragmentation involves dividing a relation into subsets of tuples. A horizontal fragmentation is generated by specifying a predicate based on certain constraints applied to the tuples in a relation. It is defined using the SELECT operation from relational algebra.

The SELECT operation gathers tuples that share a common property. For instance, tuples related to the same application or located at the same site. Given a relation ( R ), a horizontal fragmentation is defined as:

σP​(R)

Where ( P ) is a predicate based on one or more attributes of the relation.

Example: Assume there are only two types of properties: houses and flats. Horizontal fragmentation of properties for rent based on property type can be represented as:

P1:σtype=’House’​(PropertyForRent)

$P2: \sigma_{\text{type='Flat'}}(\text{PropertyForRent})$

Fragment P1

Pno	Street	Area	City	Pcode	Type	Rooms	Rent	Cno	Sno	Bno
PA14	16 Holl	Dee	Aber	AB75S	House	6	650	CO46	SA9	B7
PG21	18 Dell	Hynd	Glas	G12	House	4	500	CO87	SG37	B3

Fragment P2

Pno	Street	Area	City	Pcode	Type	Rooms	Rent	Cno	Sno	Bno
PL94	6 Arg	Dee	Aber	AB74S	Flat	4	450	CO67	SL41	B5
PG4	8 Law	Hynd	Glas	G50	Flat	4	400	CO70	SG14	B3
PG16	2 Man	Part	Glas	G67	Flat	3	300	CO90	SG14	B3

This fragmentation is beneficial when transactions involve different applications, such as for houses or flats.

Correctness Rules:

1. Completeness: Every tuple in the relation must appear in either ( P1 ) or ( P2 ).
2. Reconstruction: The original relation can be reconstructed using the UNION operation:
   ( P1 \cup P2 = \text{PropertyForRent} ).
3. Disjointness: No tuple should belong to more than one fragment.

Horizontal fragmentation strategies may sometimes be straightforward. In other cases, detailed analysis of the application, including predicate evaluation, is required.

2. Vertical Fragmentation

Vertical fragmentation involves splitting a relation into subsets of attributes. This fragmentation groups attributes that are frequently used together by applications. It is defined using the PROJECT operation in relational algebra. For a relation ( R ), a vertical fragmentation is represented as:

[ \pi_{a1,a2,...,an}(R) ]

Where ( a1, a2, ..., an ) are attributes of ( R ).

Example: In a company called Dream Home, the Payroll application requires attributes ( Sno, \text{Position}, \text{Sex}, \text{DOB}, \text{Salary}, \text{NIN} ), while the HR department requires ( Sno, \text{Fname}, \text{Lname}, \text{Address}, \text{Tel_no}, \text{Bno} ). The vertical fragmentation is as follows:

• ( S1 = \pi_{\text{Sno,Position,Sex,DOB,Salary,NIN}}(\text{Staff}) )
• ( S2 = \pi_{\text{Sno,Fname,Lname,Address,Tel_no,Bno}}(\text{Staff}) )

Fragment S1

Sno	Position	Sex	DOB	Salary	NIN
SL21	Manager	M	1-Oct-60	300000	WK44201B
SG37	Snr Ass	F	10-Nov-65	150000	WL43251C
SG14	Deputy	M	24-Mar-70	100000	WL22065B
SA9	Assistant	F	20-Jan-70	90000	WM53218D

Fragment S2

Sno	Fname	Lname	Address	Tel_no	Bno
SL21	John	White	19 Taylor London	0171-884-5112	B5
SG37	Ann	Beech	81 George Glasgow	0141-848-3345	B3
SG14	David	Ford	63 Ashby Glasgow	0141-339-2177	B3
SA9	Marie	Howe	2 Elm Aberdeen		B7

3. Mixed Fragmentation

Mixed fragmentation applies both horizontal and vertical fragmentation sequentially. It combines the SELECT and PROJECT operations. For example:

σP​(πa1,a2,...,an​(R))

$\pi_{a1,a2,...,an}(\sigma_P(R))$

4. Derived Horizontal Fragmentation

Derived fragmentation creates fragments of a "child" relation based on the fragmentation of its "parent" relation. It ensures related fragments are stored at the same site.

5. No Fragmentation

This strategy involves storing the entire relation without fragmentation. It is useful when updates are infrequent and the relation is small.

6. Fragmentation Rules

1. Completeness: All data from the original relation must appear in at least one fragment.
2. Reconstruction: The original relation must be reconstructable using fragments.
3. Disjointness: Data items should not appear in multiple fragments (except for primary keys in vertical fragmentation).