Download Click Here
CS712 – Distributed DBMS Due date: 12-06-2015
Assignment 1
Instructions to Solve Assignments
The purpose of the assignments is to give you hands on practice. It is
expected that students will solve the assignments by themselves. Following
rules will apply during the evaluation of the assignment.
·
Cheating from any source will result in zero marks in the
assignment.
·
Any student found cheating in any two of the assignments
submitted during the course will be awarded "F" grade in the course.
·
No assignment after due date will be accepted.
Answer the following questions in your own words. Plagiarism will be
checked for each question. Marks will be awarded on the basis of answer and
plagiarism report.
Question 1 (5+15+10
= 30 marks)
Read the paper entitled “A New Technique for Database Fragmentation in Distributed Systems” and answer the
following questions.
a. What are the problems in traditional
techniques of fragmentation?
Solution: In traditional
techniques of fragmentation, following problems are in common:-
1. They use
frequency of queries,
minterm predicates’ affinity or
attribute affinity matrix (AAM) as a basis of fragmentation. These require
sufficient empirical data that are not available in most cases at the initial
stage.
2. Most of them
concentrate only fragmentation problem and overlooked allocation problem to
reduce complexity.
b. Elaborate the functionality of the proposed
solution with the help of a diagram.
Solution:
Relation: A relation in a database contains different types of attributes
those describe properties of the relation. But the important thing is that the
attributes of a relation do not have same importance with respect to
data distribution in different sites. According to above importance we can
calculate locality precedence of each attribute for each relation and construct
ALP table for the relations.
MCRUD: Constructed the MCRUD matrix
for requirement analysis phase.
Predicate Set: Predicate set was generated for the attribute with highest
locality precedence of Accounts relation.
Fragmented Sub-relations:
Using predicate set, keep relations fragmented.
Allocation:
Allocate fragments among the sites
of the distributed system.
c. Describe the role of ALP matrix and CURD
matrix in distributed environment.
Solution:
Role of ALP matrix in distributed environment:
- Attribute locality precedence (ALP) can be defined as the value of importance of an attribute with respect to sites of
distributed database.
- ALP table will be constructed by
database designer.
-ALP matrix is for each relation of a DDBMS at the time of designing the
database with the help of modified CRUD and Cost Function.
- ALP values of all the attributes of relations was computed from its MCRUD
matrix.
-The attribute with highest recedence value will be treated as most
important attribute for fragmentation.
Role of CURD matrix in distributed environment:
-Help in Requirement analysis phase
-Enable the functions: Create, Read, Update, Delete
- A table of which rows indicate attributes of the
entities of a relation and columns indicate different locations
of the applications.
- It is used by the system analysts and designers in the requirement
analysis phase of system development life cycle
for making decision of data mapping to
different locations.
- We have used MCRUD to generate ALP table for each relation.
Paper link: ijcaonline.org/volume5/number9/pxc3871318.pdf
Question 2
(10+10=20 marks)
Read the paper entitled “Fragment Allocation in Distributed Database Design” and answer the
following questions.
a. As database administrator what factors should be kept in mind to resolve
the issue of fragmentation allocation optimally?
Solution:
As a database
administrator, we should consideration following points to resolve the issue of
fragmentation allocation optimally:-
(1)
Data is stored close to where it is most frequently used.
(2)
Ensure about transaction can be divided into several sub
queries that operate on fragments.
(3)
Global relation should be fragmented.
(4)
Copies of a fragment should be replicated.
(5)
Fragments should be allocated to the
sites of the communication network.
(6)
selection of the
best execution strategy for request
transformation, and allocations of operations to sites.
(7)
Ensure security so that Data not required by local applications is not
stored, and consequently not available to unauthorized users.
b. Explain the difference between First and second heuristic algorithms in
details.
Solution:
Comparing two heuristic algorithms, we find that Algorithm-1 performed better
Than Algorithm-2 in most cases.
The major difference between Algorithm-1 and Algorithm-2 is the scanning method
used to remove a fragment copy from a site.
Algorithm-1 checks whether a fragment copy should be removed from a site in
a fragment-by-fragment order.
However, Algorithm-2 checks the removal based on how many data of a fragment
copy will be update data site; that is, the more data in a fragment copy is updated,
the earlier the fragment copy is removed from a site.
In general, the performance of Algorithm-1 was worse than that of Algorithm-2
only if the total amount of updated data in the fragments scanned later was
much more than that in the fragments scanned earlier.
However, this situation did not occur frequently, thus, Algorithm-1 was better
than Algorithm-2 most of the time.
From Experimental Results, Algorithm-1 performed better Than Algorithm-2 in
most cases.
Paper link:
www.iis.sinica.edu.tw/page/jise/2001/200105_08.pdf