chapter 3 [ B ]

Question 1

horizontal fragmentation is defined by a selection operation on the _______ of a database schema.

Answer 1

owner relations

Question 2

A horizontal fragment Ri of relation R consists of all the tuples of R that satisfy a minterm predicate mi.

Answer 2

true

Question 3

given a set of minterm predicates M, how many horizontal fragments of relation R are there?

Answer 3

same number as the minterm predicates.

Question 4

set of horizontal fragments is aka _______ ?

Answer 4

minterm fragments.

Question 5

An important aspect of simple predicates is their _____ and ______ ?

Answer 5

completeness and their minimality

Question 6

Explain Completeness of predicates?

Answer 6

a set of predicates is considered complete if it can address all access patterns / queries under which tuples from the fragmented relations may need to be accessed.

Question 7

What is The reason completeness is a desired?

Answer 7

• Fragments are logically uniform
• Fragments are statistically homogeneous in the way applications access them.

Question 8

______ results in a balanced workload across all the fragments.

Answer 8

Completness

Question 9

Explain minimality.

Answer 9

means that we only include the essential predicates that impact how we break down a dataset into fragments.

• if a predicate causes a fragment f to be further fragmented into, say, fi and fj, then there should be at least one application that accesses fi and fj differently.

Question 10

If all the predicates of a set Pr are relevant, Pr is minimal

Answer 10

True

Question 11

_______ is An iterative algorithm that would generate a complete and minimal set of predicates Pr’ given a set of simple predicates Pr.

Answer 11

COM-MIN

Question 12

Write down COM-MIN algorithm.

Answer 12

• Input: Set of simple predicates Pr
• Output: Complete & minimal set of predicates Pr’

1. Initialize Pr’ as an empty set.
2. For each simple predicate p in Pr:
   a. Add p to Pr’.
3. For each pair of distinct minterm predicates mi, mj in Pr’a. Check if mi and mj are identical in their
   definitions except for one simple predicate pib. If pi is relevant, Keep both mi and mj in Pr’
   c. If pi is not relevant, Remove the less relevant
   predicate
4. Repeat steps 3 until no further changes can be made to Pr’.
5. Output Pr’ as the complete and minimal set of predicates.

Question 13

reduction of minterms can be achieved by _____ ?

Answer 13

eliminating minterms that might be contradictory to a set of implications I.

Question 14

Give an example of contradicting minterm elimination.

Answer 14

• We have an attribute ‘att’ that can take on values from a set {value_1, value_2}.

Implication
- i1: If ‘att’ is ‘value_1’, then it can’t be ‘value_2’.
- i2: If ‘att’ is not ‘value_1’, then it must be ‘value_2’.

minterms
- m1: (att = value_1) AND (att = value_2)
- m2: ¬(att = value_1) AND (att = value_2)
- m3: (att = value_1) AND ¬(att = value_2)
- m4: ¬(att = value_1) AND ¬(att = value_2)

—> minterm predicates m1 and m4 are contradictory to the implications I

Question 15

Explain the PHORIZONTAL Algorithm?

Answer 15

Input
- Relation R: Table to be horizontally fragmented.
- Pr: The set of simple predicates

Steps

1. Initialize empty set Fragments
2. For each simple predicate p in Pra. Create a fragment Fi
   - consists of the rows that satisfy the simple
   predicate p.
   - p is “age > 30,” Fi will contain all rows where
   the age is greater than 30.
3. Add Fi to the Fragments set
4. Repeat steps 2-3 for all predicates in Pr
5. Output Fragments

Question 16

Given these Scenarios:

• Employee records are managed in two places.
• One handles records of those with salaries less than or equal to $30,000.
• The other handles records of those who earn more than $30,000.

Workout the :
- Simple Predicates
- Application of COM_MIN Algorithm &
- Minterm Predicates

Answer 16

1. Simple Predicates
   - p1: Salary is less than or equal to $30,000.
   - p2: Salary is more than $30,000.
2. Application of COM_MIN Algorithm
   - Initial Set: Pr = {p1, p2}.
   - Iteration 1 (i=1): Applying COM_MIN with i=1 results
   in Pr’ = {p1}.
   This is complete and minimal since p2 would not
   partition f1 ( fragment due to p1 )
3. Minterm Predicates:
   - m1: Salary < $30,000.
   - m2: Salary > $30,000.

Question 17

Explain Derived Horizontal Fragmentation.

Answer 17

• Derived Horizontal Fragmentation is a way of dividing data based on a selection operation specified on the owner of a link.
• There’s a link (L), has an owner relation and a member relation

Question 18

Give Example of vertical fragmentation using Engineers’ Salaries.

Answer 18

• Consider a link L1 where owner(L1) = PAY and member(L1) = EMP.
• Group engineers into two categories based on salary: those making <= $30,000 and those making > $30,000.
• RESULT : 2 tables with column ENO, ENAME, TITLE

Question 19

a vertical fragmentation of a relation R, produces fragments that contain a subset of R’s attributes as well as the primary key of R.

Answer 19

True

Question 20

What is meant by an “optimal” fragmentation

Answer 20

Reducing the overall computational load since it :

• Helps in handling user queries with smaller relations, leading to fewer page accesses.
• Identifying and placing the most “active” sub- relations in a faster memory subsystem can enhance performance.

Question 21

What are the heuristic approaches [ rule of thumb ] for Vertical fragmentation?

Answer 21

1. Grouping
2. Splitting:

Question 21

Explain the Grouping heuristic approach for the vertical fragmentation

Answer 21

Initially assigns each attribute to one fragment then Joins fragments until certain criteria are met.

Question 21

_______ approach fits more naturally within the top-down design methodology

Answer 21

Grouping

Question 22

Explain the Splitting heuristic approach for the vertical fragmentation.

Answer 22

Starts with a relation and decides partitioning based on application access behavior

Question 22

When Splitting, the solution is probably closer to the full relation than to a set of fragments

Answer 22

False
- in grouping new

Question 23

_______ generates non-overlapping fragments whereas _______ results in overlapping fragments

Answer 23

Splitting , grouping

Question 23

______ is a characteristic of vertical fragmentation that allows the reconstruction of the global relation.

Answer 23

replication of the global relation’s key in the fragments.

Question 24

vertical fragmentation is about dividing a big table into smaller pieces by grouping attributes together or by splitting them.

Answer 24

True

Question 24

vertical fragmentation is about dividing a big table into smaller pieces by grouping attributes together or by splitting them.

Answer 24

True

Question 25

The major information required for vertical fragmentation is related to ________ ?

Answer 25

applications

Question 25

What is the notion of togetherness?

Answer 25

We want to know how closely related or connected certain attributes of data are.

Question 26

What is Access Frequeny?

Answer 26

• how often different parts of the data are queried
• For each application and each piece of data, we create a measure called “attribute usage value.”

Question 27

What is the The Allocation Problem?

Answer 27

• Assume we have fragments (f1…,fn) and Sites (s1…,sn) in our DDB network.
• The problem is deciding the best way to spread these fragments across the network, especially when different applications are happening.

Question 28

The optimality can be defined with respect to ________ and _______ ?

Answer 28

Minimal cost and Performance

Question 29

What does The cost function consists of?

Answer 29

– the cost of storing each Fi at a site Sj,
– the cost of querying Fi at site Sj ,
– the cost of updating Fi at all sites where it is stored,

Question 30

What are the Two well-known performance metrics?

Answer 30

• to minimize the response time
• to maximize the system throughput