Functional Dependencies - Armstrong's Axioms

▶

Steps

setup

Initialize Attributes and Dependencies

We start by defining the entities representing attributes A, B, and C, and the initial functional dependencies A -> B and B -> C as relationships.

💡 Setting up the schema entities and known dependencies is essential to apply Armstrong's axioms systematically.

Line:

attributes = {'A', 'B', 'C'}
fd_set = {('A', 'B'), ('B', 'C')}

💡 Initial known dependencies form the base for inference.

expand

Apply Reflexivity Axiom: A -> A

We apply reflexivity by adding trivial dependencies where each attribute functionally determines itself, starting with A -> A.

💡 Reflexivity states every attribute determines itself, which is foundational for closure computations.

Line:

fd_set.add(('A', 'A'))

💡 Trivial dependencies are always true and must be included.

expand

Apply Reflexivity Axiom: B -> B

Next, reflexivity adds the trivial dependency B -> B for attribute B.

💡 Each attribute must be recognized as functionally determining itself.

Line:

fd_set.add(('B', 'B'))

💡 Trivial dependencies are systematically added for all attributes.

expand

Apply Reflexivity Axiom: C -> C

Finally, reflexivity adds the trivial dependency C -> C for attribute C.

💡 Completing reflexivity for all attributes ensures closure completeness.

Line:

fd_set.add(('C', 'C'))

💡 All attributes have trivial dependencies included.

expand

Apply Augmentation Axiom: Augment A->B with C

We apply augmentation by adding attribute C to both sides of A->B, creating AC->BC.

💡 Augmentation allows extending dependencies by adding attributes to both sides, preserving dependency validity.

Line:

fd_set.add(('AC', 'BC'))

💡 Augmentation generates new dependencies from existing ones by attribute extension.

expand

Apply Transitivity Axiom: Derive A -> C

Using A->B and B->C, transitivity infers A->C, adding this new dependency.

💡 Transitivity allows chaining dependencies to infer new ones, critical for closure computation.

Line:

if ('A', 'B') in fd_set and ('B', 'C') in fd_set:
    fd_set.add(('A', 'C'))

💡 Transitivity derives new dependencies by chaining existing ones.

compare

Check for Further Inferences

We check if any new dependencies can be derived from the updated set, verifying closure completeness.

💡 Repeated checks ensure all possible dependencies are found, confirming closure.

Line:

new_fds = infer_new_dependencies(fd_set)
if not new_fds:
    done = True

💡 Closure is reached when no new dependencies can be inferred.

reconstruct

Finalize Closure Set

We finalize the closure set of functional dependencies including all trivial, original, augmented, and inferred dependencies.

💡 Finalizing closure confirms all dependencies are accounted for and ready for use in normalization.

Line:

closure = fd_set

💡 Closure contains all dependencies logically implied by the initial set.

reconstruct

Read Final Answer: Closure Includes A->C

We highlight the key inferred dependency A->C as the main output of Armstrong's axioms application.

💡 Identifying inferred dependencies like A->C shows the power of Armstrong's axioms in normalization.

Line:

print('Closure includes:', closure)

💡 The closure reveals all dependencies implied by the initial set.

reconstruct

End of Algorithm

The algorithm terminates after closure is complete and all dependencies are identified.

💡 Termination confirms no further dependencies can be inferred, ensuring completeness.

Line:

return closure

💡 Algorithm ends with a complete set of functional dependencies.

📊

Functional Dependencies - Armstrong's Axioms - Watch the Algorithm Execute, Step by Step

Watching the algorithm apply each axiom one at a time reveals how new dependencies are logically inferred, making the abstract rules concrete and understandable.

Initial attributes and dependencies

A

B

C

A →(1:1)→ BB →(1:1)→ C

Setup of attributes and initial functional dependencies

Reflexivity on A

A

B

C

A →(1:1)→ BB →(1:1)→ CA →(1:1)→ A

Added trivial dependency A->A by reflexivity

Reflexivity on B

A

B

C

A →(1:1)→ BB →(1:1)→ CB →(1:1)→ B

Added trivial dependency B->B by reflexivity

Reflexivity on C

A

B

C

A →(1:1)→ BB →(1:1)→ CC →(1:1)→ C

Added trivial dependency C->C by reflexivity

Augmentation of A->B with C

A

B

C

AC

BC

A →(1:1)→ BB →(1:1)→ CAC →(M:M)→ BC

Added augmented dependency AC->BC

Transitivity deriving A->C

A

B

C

A →(1:1)→ BB →(1:1)→ CA →(1:1)→ C

Derived new dependency A->C by transitivity

Closure completeness check

A

B

C

A →(1:1)→ BB →(1:1)→ CA →(1:1)→ C

No further dependencies inferred; closure complete

Final closure set

A

B

C

AC

BC

A →(1:1)→ BB →(1:1)→ CA →(1:1)→ CA →(1:1)→ AB →(1:1)→ BC →(1:1)→ C

Complete closure of functional dependencies

Key inferred dependency A->C

A

B

C

A →(1:1)→ C

Final answer highlighting inferred dependency A->C

Algorithm termination

A

B

C

AC

BC

A →(1:1)→ BB →(1:1)→ CA →(1:1)→ CA →(1:1)→ AB →(1:1)→ BC →(1:1)→ C

Algorithm completed with full closure

Key Takeaways

✓ Armstrong's three axioms - Reflexivity, Augmentation, and Transitivity - are complete and sound: any functional dependency derivable from a set F can be proven using only these three rules.

Reflexivity gives trivial FDs (A → A). Augmentation adds attributes to both sides (A→B becomes AC→BC). Transitivity chains FDs (A→B and B→C gives A→C).

✓ Transitivity is the most powerful axiom - it lets you derive non-obvious dependencies. Starting from A→B and B→C, you can prove A→C without any new data.

Think of it as a chain: if knowing A tells you B, and knowing B tells you C, then knowing A must tell you C.

✓ The closure of a set of FDs (F+) is all FDs derivable from F using Armstrong's axioms. Computing attribute closure (X+) is the practical tool to find all attributes determined by X.

In the trace: starting with {A→B, B→C}, applying transitivity gives A→C. The full closure F+ includes all original, trivial, augmented, and transitive dependencies.

Practice

1. Which of the following statements about B+ Trees is INCORRECT?

medium

A. All keys appear in the leaf nodes, and internal nodes only store keys to guide searches.

B. Leaf nodes are linked sequentially to facilitate efficient range queries.

C. Data records can be stored in both internal and leaf nodes to speed up point queries.

D. Insertion and deletion operations may cause splitting or merging of leaf and internal nodes.

Solution

1. Step 1: Recall B+ Tree data storage rules

   Data records are stored only in leaf nodes; internal nodes store keys for navigation.

2. Step 2: Verify leaf node linkage

   Leaf nodes are linked sequentially to optimize range queries.

3. Step 3: Understand insertion/deletion effects

   Splitting and merging can occur in both leaf and internal nodes to maintain tree properties.

4. Step 4: Identify incorrect statement

   Data records can be stored in both internal and leaf nodes to speed up point queries. incorrectly states data records are stored in internal nodes, which contradicts B+ Tree design.

5. Final Answer:

   Option C -> Option C

6. Quick Check:

   Data only in leaves; internal nodes are index-only.

Hint: B+ Tree data only in leaves; internal nodes are keys only

Common Mistakes:

• Believing data can be stored in internal nodes
• Confusing B+ Tree with B-Tree data placement
• Ignoring leaf node linkage importance

2. Why is it generally discouraged to directly implement many-to-many (N:M) relationships in a relational database without an associative (junction) table?

medium

A. Because direct N:M relationships cause data redundancy and complicate enforcing referential integrity.

B. Because relational databases do not support multiple foreign keys in a single table.

C. Because N:M relationships require storing duplicate primary keys in both tables.

D. Because N:M relationships can only be represented using triggers.

Solution

1. Step 1: Understand N:M relationship representation

   Direct N:M relationships are not supported as foreign keys in relational tables.

2. Step 2: Identify issues with direct implementation

   Trying to store multiple foreign keys in one table leads to redundancy and integrity problems.

3. Step 3: Use associative table to resolve

   Associative (junction) tables break N:M into two 1:N relationships, maintaining normalization and integrity.

4. Step 4: Evaluate other options

   Because relational databases do not support multiple foreign keys in a single table is false; tables can have multiple foreign keys. Because N:M relationships require storing duplicate primary keys in both tables is incorrect; primary keys are not duplicated but referenced. Because N:M relationships can only be represented using triggers is false; triggers are not required for N:M representation.

5. Final Answer:

   Option A -> Option A

6. Quick Check:

   Associative tables prevent redundancy and maintain referential integrity in N:M relationships.

Hint: N:M relationships require a junction table to avoid redundancy and maintain integrity.

Common Mistakes:

• Believing multiple foreign keys in one table can represent N:M directly
• Confusing primary key duplication with foreign key referencing

3. What is a key trade-off or limitation of MVCC in terms of storage and performance?

medium

A. MVCC requires maintaining multiple versions, increasing storage and cleanup complexity

B. MVCC guarantees serializable isolation without any anomalies

C. MVCC eliminates all locking overhead, resulting in zero contention

D. MVCC reduces write amplification by avoiding version creation

Solution

1. Step 1: Understand MVCC version management

   MVCC stores multiple versions of rows to provide snapshot isolation, which increases storage usage and requires vacuuming or cleanup.

2. Step 2: Analyze locking overhead

   MVCC reduces locking but does not eliminate all contention, especially for writes.

3. Step 3: Analyze isolation guarantees

   MVCC typically provides snapshot isolation, which can allow anomalies; serializability requires additional mechanisms.

4. Step 4: Analyze write amplification

   MVCC increases write amplification due to version creation, not reduces it.

5. Final Answer:

   Option A -> Option A

6. Quick Check:

   MVCC trades off storage and cleanup overhead for concurrency benefits [OK]

Hint: MVCC trades storage and cleanup overhead for non-blocking reads

Common Mistakes:

• Assuming MVCC removes all contention
• Confusing snapshot isolation with serializability
• Believing MVCC reduces write amplification

4. If a database system needs to support very high-frequency insertions and deletions along with range queries, how does the B+ Tree structure help maintain performance, and what challenges might arise?

hard

A. B+ Tree stores data in internal nodes to reduce tree height, minimizing disk I/O during updates.

B. B+ Tree's linked leaf nodes allow efficient range queries, but frequent splits and merges can cause fragmentation and increased disk I/O.

C. B+ Tree avoids node splitting by always merging nodes during insertions and deletions, ensuring stable performance.

D. B+ Tree uses a fixed node size that prevents fragmentation, so performance remains constant regardless of update frequency.

Solution

1. Step 1: Understand B+ Tree leaf linkage benefits

   Linked leaf nodes enable efficient sequential access for range queries.

2. Step 2: Consider update overhead

   High-frequency insertions/deletions cause node splits and merges, which can fragment data and increase disk I/O.

3. Step 3: Analyze incorrect options

   B+ Tree stores data in internal nodes to reduce tree height, minimizing disk I/O during updates. is false; B+ Tree stores data only in leaves. B+ Tree avoids node splitting by always merging nodes during insertions and deletions, ensuring stable performance. is incorrect because merges alone cannot avoid splits. B+ Tree uses a fixed node size that prevents fragmentation, so performance remains constant regardless of update frequency. is wrong; fixed node size does not prevent fragmentation from splits/merges.

4. Final Answer:

   Option B -> Option B

5. Quick Check:

   B+ Tree balances efficient range queries with update overhead due to structural changes.

Hint: Linked leaves -> fast range queries; splits/merges -> update overhead

Common Mistakes:

• Assuming B+ Tree stores data in internal nodes
• Believing merges prevent splits entirely
• Thinking fixed node size eliminates fragmentation

5. In a distributed NoSQL database that uses optimistic concurrency control with version vectors, what challenge arises when multiple clients concurrently update the same document offline and then synchronize later?

hard

A. Conflicts may require manual resolution because version vectors detect but do not resolve conflicts

B. Pessimistic locking can be used to prevent conflicts in offline mode

C. Automatic conflict resolution always merges changes without data loss

D. The system rejects all concurrent updates to maintain consistency

Solution

1. Step 1: Understand optimistic concurrency with version vectors

   Version vectors track causality and detect conflicting updates.

2. Step 2: Analyze offline concurrent updates

   Clients updating offline create divergent versions that version vectors identify as conflicts upon sync.

3. Step 3: Conflict resolution implications

   Version vectors detect conflicts but do not automatically merge them; manual or application-level resolution is often needed.

4. Step 4: Evaluate other options

   A is false: automatic merges are not guaranteed. B is false: pessimistic locking is impractical offline. D is false: rejecting all concurrent updates is not typical in NoSQL systems.

5. Final Answer:

   Option A -> Option A

6. Quick Check:

   Version vectors help detect but do not solve conflicts automatically in distributed offline scenarios.

Hint: Version vectors detect conflicts; resolution is often manual or app-specific.

Common Mistakes:

• Assuming automatic conflict merges always happen
• Thinking pessimistic locking works offline
• Believing all concurrent updates are rejected