Advertisements
Home > distributed database, Information Technology > Distributed Database System: Exercise 2

Distributed Database System: Exercise 2

Exercise 2.1: Discussion

Please answer briefly

1. Please define fragmentation and allocation.

2. What does it mean if fragmentation violates the completeness rule?

3. Why is the disjointness rule important?

4. When deciding for a good fragmentation and allocation, which criteria should be optimized?

5. What are the disadvantages and advantages of replication? Is it a good idea to use full replication? If yes, in which cases?

 

Exercise 2.2: Optimal automatic horizontal fragmentation

A company has three divisions: games (G), tools (T), and rental (R). All departments are assigned to one of these divisions:

departments 100 . . . 250: games,

departments 251 . . . 400: tools,

and departments 401 . . . 499: rental.

The analysis of applications used in these departments resulted in the following access ranges on relation Departments:

• A1 : Access to tuples in division (G)

• A2 : Access to tuples in division (T)

• A3 : Access to tuples in division (R)

• A4 : Access to tuples with department number DepN o ∈ [100 . . . 150]

• A5 : Access to tuples with department number DepN o ∈ [151 . . . 299]

• A6 : Access to tuples with department number DepN o ∈ [300 . . . 499]

with Departments(depNo, depName, division, budget) Please apply the “optimal automatic horizontal fragmentation” algorithm. For simplicity, interpret the term “clear improvement” as “there is a change in the obtained fragmentation”and ignore the fragmentation’s relevance in terms of fragment size and access frequency.

 

Exercise 2.3: Derived horizontal fragmentation

Given the following fragmentation of relation Supplier which splits the relation in internal and external suppliers:

• Supplier1 : σcode= internal (Supplier)

• Supplier2 : σcode= internal (Supplier)

with Supplier(supNo, supName, code, city)

Please determine a derived horizontal fragmentation for relation Parts(partNo, partName,supNo, price) with supNo being a foreign key in Parts referencing Supplier.supNo. Please comment on the correctness of your solution by describing why the correctness rules are met.

Draw the join graph and decide on the “goodness” of the obtained fragmentation.

 

Exercise 2.4: Hybrid fragmentation

Please fragment relation Parts(partNo, partName, supNo, price) into two relations by separat-ing attribute partName. The obtained relation with all the other attributes is to be fragmentedinto cheap (≤ 10 EUR) and expensive (> 10 EUR) parts. The expensive parts shall once againbe partitioned into those supplied by internal and those supplied by external suppliers (seeExercise 2.3).

Please provide the algebra expressions necessary to partition relation Parts. Please indicate which kind of fragmentation is used.

 

Solution

 

Exercise 2.1: Discussion

1.Fragmentation: An act of decomposing one or more Relations into smaller, disjunctive fragments.

Allocation: The distribution of the fragments into several nodes.

2. Completeness rule means that when we join all the fragments up to the last fragments, it will contain all the data before it is fragmented into smaller, disjunctive fragments.

3. Disjointness rule is very important to avoid redundancy of data. If the data is overlap one another between fragments than the data is no longer genuine.

4. The criteria that should be optimized when doing fragmentation & allocation are:

  • Storage cost
  • Transfer cost

5. Advantages of performing full replication are:

  • No fragmentation/ allocation strategy necessary.
  • No distributed query processing which means faster performance in retrieving data.
  • Disadvantages of performing full replication are:
  • High storage space consumption as you need to store all global relation on every node.
  • High update costs since you perform all updates on all of the nodes.

It is not a good idea to do a full replication since not all nodes are prone to failures or access frequently. It is better to use partial replication, in which only the nodes that are failure-prone and have a frequent update or query task are being replicated.

 

Exercise 2.2: Optimal automatic horizontal fragmentation

A1 : Access to tuples in division (G) ∈ [100 . . . 250]

A2 : Access to tuples in division (T) ∈ [251 . . . 400]

A3 : Access to tuples in division (R) ∈ [401 . . . 499]

A4 : Access to tuples with department number DepN o ∈ [100 . . . 150]

A5 : Access to tuples with department number DepN o ∈ [151 . . . 299]

A6 : Access to tuples with department number DepN o ∈ [300 . . . 499]

First combinations (Yellow highlight shows dependant predicates):

A1 ^ A4, A1 ^ A5.

A2 ^A5, A2 ^ A6.

A3 ^ A6.

Access (A1 ^ A5) = 100, Fragment Size (A1 ^ A5) = 251 => relevancy = 0.4

Access (A2 ^ A5) = 49, Fragment Size (A2 ^ A5) = 150 => relevancy = 0.33

Access (A2 ^ A6) = 101, Fragment Size (A2 ^ A6) = 249 => relevancy = 0.4

Access (A3 ^ A6) = 99, Fragment Size (A3 ^ A6) = 100 => relevancy = 0.99

Therefore the optimal horizontal fragmentation would be:

Fragment 1: Data from DepNo ∈ [100 . . . 299]

Fragment 2: Data from DepNo ∈ [300 . . . 499]

 

Exercise 2.3: Derived horizontal fragmentation

Supplier1 : σcode= internal (Supplier)

Supplier2 : σcode!= internal (Supplier)

πpartNo, partName, supNo,price σSUPPLIER.code=internal ∧SUPPLIER.supNo=PARTS.supNo SUPPLIER × PARTS

πpartNo, partName, supNo,price σSUPPLIER.code!=internal ∧SUPPLIER.supNo=PARTS.supNo SUPPLIER × PARTS

The correctness rule apply perfectly on this fragmentation since you only have two conditions which will not overlap and all the data are perfectly coped with the conditions (either the supplier code is internal or not).

 

Exercise 2.4: Hybrid Fragmentation

Parts1 = πpartNo, partName (Parts) => Vertical Fragmentation

Parts2 = πpartNo, supNo, price (Parts) => Vertical Fragmentation

Parts2.1 = σprice <= 10 (Parts) => Horizontal Fragmentation

Parts2.2 = σprice > 10 (Parts) => Horizontal Fragmentation

Parts2.2.1 =  σSUPPLIER.code=internal ∧SUPPLIER.supNo=PARTS.supNo SUPPLIER x PART => Horizontal Fragmentation

Parts2.2.2 =  σSUPPLIER.code!=internal ∧SUPPLIER.supNo=PARTS.supNo SUPPLIER x PART => Horizontal Fragmentation

Advertisements
  1. December 20, 2010 at 5:22 am

    “The obtained relation with all the other attributes is to be fragmentedinto cheap (? 10 EUR) and expensive (> 10 EUR) parts. The expensive parts shall once againbe partitioned into those supplied by internal and those supplied by external suppliers (seeExercise 2.3).”
    Intresting. I would like details!

  1. No trackbacks yet.

Leave a Reply

Fill in your details below or click an icon to log in:

WordPress.com Logo

You are commenting using your WordPress.com account. Log Out /  Change )

Google+ photo

You are commenting using your Google+ account. Log Out /  Change )

Twitter picture

You are commenting using your Twitter account. Log Out /  Change )

Facebook photo

You are commenting using your Facebook account. Log Out /  Change )

w

Connecting to %s

%d bloggers like this: