Databases Test 2

Concept:

A functional dependency A -> B is true in a relation R(A, B) if

1) There is different value for attribute A for all the tuples.

2) If two values are same in A, then their corresponding value in B must also be same.

Explanation:

Given relation R (A, B, C) with the tuples (2, 3, 4) (4, 1, 2) (5, 2, 2) (1, 3, 2)

These are represented in the form of table as:

Consider all the options one by one:

1. B -> C

Here, B has two values equal i.e. 3. Their corresponding in value must be same in C but it is different here. One value for 3 is 4 and other is 2. So, it is not correct.

2. A -> B

This one has all different value for A. So, this functional dependency holds true.

3. AC -> B

All value for AC are different. So, functional dependency is true.

4) BC -> A

Same with this, All the values in BC are different. So, it holds true.

ACID Properties:

A transaction in a database system must maintain Atomicity, Consistency, Isolation, and Durability − commonly known as ACID properties − in order to ensure accuracy, completeness, and data integrity.

Atomicity − This property states that a transaction must be treated as an atomic unit, that is, either all its operations are executed or none.

Consistency − The database must remain in a consistent state after any transaction. No transaction should have any adverse effect on the data residing in the database.

Isolation − In a database system where more than one transaction is being executed simultaneously and in parallel, the property of isolation states that all the transactions will be carried out and executed as if it is the only transaction in the system.

Durability − The database should be durable enough to hold all its latest updates even if the system fails or restarts.

Therefore, Duration and Independent are not a part of the ACID properties of database transactions?

T1 → \({{\rm{\Pi }}_{id,name}}\left( {{\sigma _{age > 13 \wedge age < 16}}\left( {STU} \right)} \right)\)

Output: 

Number of rows: 5

T2 → \({{\rm{\Pi }}_{id,name}}\left( {{\sigma _{marks > 55 \wedge marks < 66}}\left( {STU} \right)} \right)\)

Output:

Number of rows: 3

T → T2 - T1

Output:

T contains 1 row:

Concept:

Safe expression: A safe expression is one that is guaranteed to yield a finite number of tuples in the result.

Unsafe expression: An expression which result in infinite number of tuples or which does not guarantee about finite number of tuples is an unsafe expression tuple relational calculus.

Explanation:

Tuple relational calculus provides the description of query but does not provide methods to solve it.

An expression {t | P(t)} means set of all the tuples such that predicate P(t) is true for t.

Here in this question,

(i) {T |~Tϵ Account}

It means, all who does not belongs to the relation account. There may be infinite number of tuples for this. So, it is an unsafe expression.

(ii) {T | Tϵ Account}

This results in finite number of tuples. So, it is a safe expression.

Primary index:

It is defined on an ordered data file and the data file is ordered on a key field. The key field is generally the primary key of the relation.

Clustering Index:

It is defined on an ordered data file. The data file is ordered on a non-key field.

Secondary index:

It may be generated from a field which is a candidate key and has a unique value in every record, or a non-key with duplicate values only dense ordering in the non-clustered index (Secondary index) as sparse ordering is not possible because data is not physically organized accordingly.

Attribute of X is referring to attribute of Y:

If a row is deleted from X, no violation, since X is a referring relation and hence no violation

But if a row is inserted into X, since X is referring to Y, X may contain value outside the domain of primary key of Y.

If a row is inserted into Y, no violation, since Y is not referring to any other table and hence no violation

But if a row is deleted from Y, since Y is being referred by X, referred value may be deleted which leads to violation.

Hence Insert into Y and Delete from X doesn’t cause violation but insert into X causes violation.

Total number of schedule possible = \(\frac{{\left( {T_{1} + T_{2} + T_{3}+ T_{4}} \right)!}}{{T_{1}!\times T_{2}!\times T_{3} ! +T_4!}} \)

Total number of schedule possible = \(\frac{{\left( {5 + 4 + 3+ 2} \right)!}}{{5!\times 4! \times 3! \times2!}} =2522520\)

Total number of serial schedule possible = \(n!\)

where n is the total number of transaction

Total number of serial schedules = 4! = 24

Total number of non-serial schedules =2522520 - 24 = 2522496

A transaction read a data item after it has been written by an uncommitted transaction leads to an irrecoverable error in a database system.

∴ statement I false

Time stamp ordering protocol ensures freedom from deadlock

∴ statement II false

In the ACID property, the durability property makes changes successfully in the database in case of:

Power failure, dish crash or operating system crash

∴ statement III false

Therefore, X → Y and W → Z are preserved, after the decomposition.

There is no common attribute of T1 and T2, therefore decomposition is lossy.

The decomposition of R into T1(X, Y) and T2(Z, W) is dependency preserving but not lossless join

In R1(DEF),

D+ = {D, E, F}

E+ = {E, F, D}

F+ = {F, D, E}

Therefore D, E and F are candidate key

Number of super keys:

n(D U E U F) = n(D) + n (E) + n(F) – n(DE) – n(DF) – n(EF) + (DEF)

= 23 – 1 + 23 – 1 + 23 – 1 - 23 – 2 - 23 – 2 - 23 – 2 + 23 – 3

= 4 + 4 + 4 – 2 – 2 – 2 + 1

= 7

Therefore option 1 and 4 are correct.

Tips and Tricks:

Since every key is candidate key then every possible key is a super key except Φ

Check: R ⊇ S

X⁺ = {Y, Z, E}

∴ X → YZ

W⁺ = {W, X, Z, Y}

W → XY

Hence R is covering S, that is, R ⊇ S

Check: S ⊇ R

X⁺ = {X, Y, Z}

∴ X → Y

(XY)⁺ = {X, Y, Z}

∴ XY → Z

W⁺ = {W, X, Y, Z}

∴ W → XZ

Z⁺ = {Z}

Z → W, it cannot be determined by S

and hence, S cannot cover R, that is, S ⊇ R is false

A relation schema R is in BCNF, only if in every non-trivial functional dependency 

X → Y 

X is a superkey

R(ABC)

(AB)+ = {A, B, C}

(AC)+ = {A, B, C}

(BC)+ = {C, B, A}

Candidate key: AB, AC and BC

BCNF is the strongest form.

Since R is in BCNF. Therefore it is also in 1NF, 2NF and 3NF

A:

B:

A NATURAL JOIN B

SELECT count(*) FROM A NATURAL JOIN B

Without "having" clause query calculates the average age (where age >= 18) and groups by ratings so table returned is:

After applying "having" clause table returned is:.

Concept:

Conflict serializable schedule: A schedule is conflict serializable if we can convert it into a serial schedule after swapping of non conflicting operations. If there is no loop in the precedence graph, then schedule is conflict serializable.

Recoverable schedule: If some transaction T_j is reading value update by T_i, then commit of T_j must occur

After the commit of T_i.

Cascadeless schedule: A transactionT_j can only read the value updated by T₁ after the commit of T₁.

Explanation:

Following schedule of transactions can be represented in the form of table as :

(i) As, all the operations are non- conflicting here. So, schedule is conflict serializable.

(ii) here, T4 is reading the value update by T1. So, commit of T1 must be before T4. Also, T4 is reading

The value updated by T2 and commit of T2 is before T4. So, schedule is recoverable.

(iii) This schedule is not cascaseless. Because T4 is reading the value update by T1. But commit of T1 is not before the read of T4. 

In R(ABCDEFGH), left-hand side of FD has attributes: {G, B, C, F, H, A, E, G}

Since it doesn't contain D we cannot derive it unless it is the present right-hand side. 

(AD)⁺ =  {A,D, B, C, F, H, G, E } 

Since all the 8 attributes are present, AD is a candidate key

(BD)+ =  {B, D, C, F, H, G, E, A } 

Since all the 8 attributes are present, BD is a candidate key

(ED)+ =  {E, D, A, B, C, F, H, G } 

Since all the 8 attributes are present, ED is a candidate key

(FD)+ =  {F, D, E, G, A, B, C, H } 

Since all the 8 attributes are present, FD is a candidate key

Therefore there are total 4 candidate keys.

Given:

Data block size = 10² bytes

Disk capacity = 100 × 10⁴ B

Entries in file allocation table \( = \frac{{disk\;capacity}}{{block\;size}} = \frac{{{{10}^6}}}{{{{10}^2}}} = {10^4}\;\)

Overhead for each entry in FAT = 2 Bytes

So, total capacity of File allocation table =  10⁴ × 2 Bytes

Maximum file size that can be stored on disk = 100 × 10⁴ – 2 ×10⁴

= 98 × 10⁴ Bytes

T1 ← ∏_Y (σ _{X = A3} (T))

T1:

T2 ← T ÷ T1

Therefore, relation T2 contains 2 rows:

Tips and Tricks:

In the case of M:N, there is a need for a separate table for relationship and hence option 1 is correct

In the case of I:M and 1:1, there is no need for a separate table for relationships. It can be combined with M side in 1:M case and with any side in 1:1. Hence option 2 is incorrect 

In the case of a multi-valued attribute separated table is needed. Hence option 3 is correct

Also, the Cardinality ratio is applicable for only binary relationships, option 4 is correct

Concept:

Two schedules are said to be conflict equivalent if the order of any two conflicting operations is the same in both the schedules. A schedule S is said to be conflict serializable if it is conflict equivalent to some serial schedule S’.

Explanation:

There can be two cases possible for above given transaction:

1) T₁ is followed by T₂

In this, read (x) for T₁ is executed before write (x) of T₂.

2) If T₂ is followed by T₁

then read(y) of T₂ is executed before write (y) of T₁.

In both the cases, if we try to make any non-serial schedule, then there will be conflict from both T₁ -> T₂ and T₂ -> T₁. Precedence graph will contain cycle.

Consider we are taking Schedule S: r₁(x) r₂(y) r₁(y) w₂(x) w₂(y) w₁(y).