ER Diagram - Entities, Relationships, Cardinality (1:N, N:M)

▶

Steps

setup

Initialize empty B-tree

We start with an empty B-tree of order 3, ready to insert entities and relationships.

💡 Initialization sets the foundation for all subsequent insertions and structural changes.

Line:

b_tree = BTree(order=3)  # STEP 1

💡 The tree is empty and balanced, with no keys or children.

insert

Insert Entity 'Student'

Insert the entity 'Student' as a key into the root node.

💡 Entities are keys in the B-tree; inserting 'Student' starts building the schema.

Line:

b_tree.insert('Student')  # STEP 2

💡 Since the root is empty and a leaf, 'Student' is inserted directly without splitting.

insert

Insert Entity 'Course'

Insert the entity 'Course' into the root node, maintaining sorted order.

💡 Entities must be kept in sorted order within nodes for efficient search.

Line:

b_tree.insert('Course')  # STEP 3

💡 'Course' is inserted before 'Student' because 'Course' < 'Student' alphabetically, so keys reorder.

insert

Insert Relationship 'Enrolls' (1:N)

Insert the relationship 'Enrolls' representing 1:N cardinality between Student and Course.

💡 Relationships are keys too; 1:N relationships are inserted as keys linking entities.

Line:

b_tree.insert('Enrolls')  # STEP 4

💡 The root node is full after insertion; keys are ['Course', 'Enrolls', 'Student'] sorted alphabetically.

insert

Insert Relationship 'Teaches' (N:M) triggers split

Insert the relationship 'Teaches' representing N:M cardinality, causing the root node to split.

💡 When a node exceeds max keys, it splits to maintain B-tree properties.

Line:

b_tree.insert('Teaches')  # STEP 5

💡 The root splits into two nodes; middle key 'Enrolls' is promoted to new root.

traverse

Traverse to right child to insert 'Teaches'

Traverse from root to right child node to insert 'Teaches' key.

💡 Traversal finds correct leaf node for insertion, respecting key order.

Line:

b_tree.insert('Teaches') continued  # STEP 6

💡 Traversal ensures keys are inserted in correct subtree for order preservation.

insert

Insert 'Teaches' in leaf node

Insert 'Teaches' key into the right child leaf node, which has space.

💡 Insertion into leaf node without split shows normal insertion step.

Line:

b_tree.insert('Teaches') final  # STEP 7

💡 Keys remain sorted: ['Student', 'Teaches'] in leaf node.

traverse

Traverse to left child to verify 'Course'

Traverse to left child node to verify presence of 'Course' entity.

💡 Traversal helps confirm entities and relationships are correctly placed.

Line:

b_tree.search('Course')  # STEP 8

💡 Traversal path shows how keys guide search in B-tree.

compare

Confirm 'Course' found in leaf node

Compare keys in leaf node to confirm 'Course' entity is present.

💡 Comparison step verifies correctness of insertion and tree structure.

Line:

if 'Course' in node.keys:  # STEP 9

💡 Presence of 'Course' confirms entity correctly inserted and accessible.

traverse

Final B-tree representing ER diagram schema

The final B-tree structure shows entities and relationships with cardinalities represented as keys and balanced nodes.

💡 The final balanced B-tree reflects the ER diagram schema design with 1:N and N:M relationships.

Line:

b_tree.inorder_traversal()  # STEP 10

💡 Inorder traversal yields keys in sorted order, representing the schema components.

class BTreeNode:
    def __init__(self, order, is_leaf):
        self.order = order
        self.keys = []  # STEP 1
        self.children = [None] * (order + 1)
        self.is_leaf = is_leaf
        self.parent = None

class BTree:
    def __init__(self, order):
        self.order = order
        self.root = BTreeNode(order, True)  # STEP 1

    def insert(self, key):
        node = self.root
        if len(node.keys) == self.order:
            self._split_root()  # STEP 5
            node = self.root
        self._insert_non_full(node, key)  # STEP 2-7

    def _insert_non_full(self, node, key):
        if node.is_leaf:
            node.keys.append(key)  # STEP 2-7
            node.keys.sort()  # STEP 3
        else:
            i = 0
            while i < len(node.keys) and key > node.keys[i]:
                i += 1
            child = node.children[i]
            if len(child.keys) == self.order:
                self._split_child(node, i)  # STEP 5
                if key > node.keys[i]:
                    i += 1
            self._insert_non_full(node.children[i], key)  # STEP 6-7

    def _split_root(self):
        old_root = self.root
        mid = self.order // 2
        left = BTreeNode(self.order, old_root.is_leaf)
        right = BTreeNode(self.order, old_root.is_leaf)
        left.keys = old_root.keys[:mid]
        right.keys = old_root.keys[mid+1:]
        if not old_root.is_leaf:
            left.children = old_root.children[:mid+1]
            right.children = old_root.children[mid+1:]
        self.root = BTreeNode(self.order, False)
        self.root.keys = [old_root.keys[mid]]  # STEP 5
        self.root.children = [left, right]

    def inorder_traversal(self):
        result = []
        def traverse(node):
            if node is None:
                return
            for i in range(len(node.keys)):
                traverse(node.children[i])
                result.append(node.keys[i])
            traverse(node.children[len(node.keys)])
        traverse(self.root)  # STEP 10
        return result

# Usage
b_tree = BTree(order=3)  # STEP 1
b_tree.insert('Student')  # STEP 2
b_tree.insert('Course')   # STEP 3
b_tree.insert('Enrolls')  # STEP 4
b_tree.insert('Teaches') # STEP 5-7
keys_inorder = b_tree.inorder_traversal()  # STEP 10

📊

ER Diagram - Entities, Relationships, Cardinality (1:N, N:M) - Watch the Algorithm Execute, Step by Step

Watching this visualization helps you understand how ER diagram components map to a B-tree structure and how cardinality constraints affect schema design, which is difficult to grasp from static diagrams or code alone.

setup

leaf

Initialize empty B-tree with order 3.

insertKey: Student

Student

leaf

Inserted entity 'Student' into root node.

insertKey: Course

CourseStudent

leaf

Inserted entity 'Course' and reordered keys.

insertKey: Enrolls

CourseEnrollsStudent

leaf

Inserted relationship 'Enrolls' into root node.

splitKey: Teaches↑ promoted: Enrolls

Enrolls

Course

leaf

Student

leaf

Root node split; 'Enrolls' promoted to new root.

traverseKey: Teaches

Enrolls

Course

leaf

Student

leaf

Traverse to right child to insert 'Teaches'.

insertKey: Teaches

Enrolls

Course

leaf

StudentTeaches

leaf

Inserted 'Teaches' into right child leaf node.

traverseKey: Course

Enrolls

Course

leaf

StudentTeaches

leaf

Traverse to left child to verify 'Course'.

compareKey: Course

Enrolls

Course

leaf

StudentTeaches

leaf

'Course' found in left child leaf node.

traverse

Enrolls

Course

leaf

StudentTeaches

leaf

Final B-tree representing ER diagram schema with entities and relationships.

Key Takeaways

✓ Entities and relationships in an ER diagram can be represented as keys in a B-tree, preserving order and enabling efficient search.

This insight is hard to see from code alone because the mapping from ER concepts to B-tree keys is abstract and visualizing it clarifies the connection.

✓ Cardinality constraints (1:N, N:M) influence how relationships are inserted and how the B-tree splits and balances.

Seeing splits triggered by relationship insertions helps understand how schema complexity affects tree structure.

✓ Traversal and insertion decisions maintain the B-tree's sorted order and balance, ensuring efficient schema representation.

Watching traversal paths and insertion points reveals the dynamic decisions that keep the tree balanced, which is not obvious from static code.

Practice

1. When executing a range query on a B+ tree index, what sequence of steps occurs internally to retrieve all matching records?

easy

A. Perform a full table scan because B+ trees do not support range queries efficiently.

B. Hash the range boundaries to find corresponding buckets, then scan all buckets between them.

C. Traverse the tree to the root, then scan all leaf nodes in order regardless of the range.

D. Locate the first key in the range via tree traversal, then follow leaf node pointers sequentially until the range end is reached.

Solution

1. Step 1: Locate start key

   B+ trees use a balanced tree traversal to find the leaf node containing the first key in the range.

2. Step 2: Sequential leaf traversal

   Leaf nodes are linked, allowing sequential scanning of keys in order until the range end is reached.

3. Step 3: Evaluate distractors

   Hash the range boundaries to find corresponding buckets, then scan all buckets between them. incorrectly applies hashing to range queries. Traverse the tree to the root, then scan all leaf nodes in order regardless of the range. suggests scanning all leaves, which is inefficient. Perform a full table scan because B+ trees do not support range queries efficiently. falsely claims B+ trees do not support range queries.

4. Final Answer:

   Option D -> Option D

5. Quick Check:

   Range query -> locate start + sequential leaf scan [OK]

Hint: B+ tree range query = find start + linked leaf scan

Common Mistakes:

• Thinking hash indexes can handle range queries by scanning buckets
• Assuming full leaf scan is needed for range queries
• Believing B+ trees do not support range queries

2. Trace the visibility of a data row version in MVCC when a transaction T1 updates a row and transaction T2 concurrently reads it. What version does T2 see if it started before T1 committed?

easy

A. T2 sees the old version of the row as of its own transaction start time

B. T2 sees the new version created by T1 immediately after T1's update

C. T2 blocks until T1 commits and then sees the new version

D. T2 sees a merged version combining old and new data

Solution

1. Step 1: Understand snapshot isolation in MVCC

   Each transaction sees a consistent snapshot of the database as of its start time.

2. Step 2: Analyze T2's read behavior

   Since T2 started before T1 committed, it sees the old version, not the uncommitted or new version.

3. Step 3: Analyze uncommitted changes visibility

   T2 does not see uncommitted changes; MVCC prevents dirty reads.

4. Step 4: Analyze blocking behavior

   MVCC avoids blocking reads; T2 does not wait for T1 to commit.

5. Step 5: Analyze version merging

   No merging of versions occurs; versions are discrete snapshots.

6. Final Answer:

   Option A -> Option A

7. Quick Check:

   MVCC provides snapshot isolation based on transaction start time [OK]

Hint: Transactions see data as of their start snapshot, not uncommitted changes

Common Mistakes:

• Thinking reads block on writes
• Assuming reads see latest uncommitted data
• Believing versions merge automatically

3. Which of the following statements about explain plans and cardinality estimates is INCORRECT?

medium

A. Explain plans help identify inefficient operations by showing estimated costs and row counts

B. Cardinality estimates in explain plans are predictions, not guaranteed counts

C. Explain plans always show the exact number of rows that will be processed at each step during execution

D. Cardinality estimates influence the optimizer's choice of join algorithms and access paths

Solution

1. Step 1: Understand explain plan cardinality

   Explain plans show estimated--not actual--row counts before execution.

2. Step 2: Analyze options

   Explain plans always show the exact number of rows that will be processed at each step during execution: Incorrect because explain plans show estimates, not exact counts.
   Cardinality estimates in explain plans are predictions, not guaranteed counts: Correct--estimates can differ from actuals.
   Explain plans help identify inefficient operations by showing estimated costs and row counts: Correct--explain plans reveal cost and cardinality to spot inefficiencies.
   Cardinality estimates influence the optimizer's choice of join algorithms and access paths: Correct--cardinality guides join and access path choices.

3. Final Answer:

   Option C -> Option C

4. Quick Check:

   Explain plans provide estimates, not runtime exacts.

Hint: Explain plans show estimates, not exact execution metrics.

Common Mistakes:

• Confusing estimated cardinality with actual runtime row counts
• Assuming explain plans reflect real-time execution
• Ignoring the predictive nature of cost and cardinality

4. Which of the following is a common misconception about the trade-offs of sharding a database to improve performance?

medium

A. Sharding always improves write throughput linearly with the number of shards.

B. Sharding can increase complexity in query processing due to cross-shard joins.

C. Choosing a poor shard key can lead to data hotspots and uneven load distribution.

D. Sharding requires careful handling of transactions spanning multiple shards.

Solution

1. Step 1: Analyze write throughput scaling

   Sharding can improve write throughput, but it does not guarantee linear scaling because of coordination overhead and cross-shard operations.

2. Step 2: Understand query complexity

   Cross-shard joins increase query complexity and can degrade performance, so this is a true trade-off, not a misconception.

3. Step 3: Recognize shard key importance

   A poor shard key causes hotspots and uneven load, a well-known limitation.

4. Step 4: Consider transactional complexity

   Distributed transactions across shards require complex coordination, increasing system complexity.

5. Step 5: Identify misconception

   The misconception is that sharding always improves write throughput linearly, which is false due to overheads.

6. Final Answer:

   Option A -> Option A

7. Quick Check:

   Sharding improves throughput but not always linearly due to overheads.

Hint: Sharding ≠ guaranteed linear write scaling [OK]

Common Mistakes:

• Assuming perfect linear scaling with shards
• Ignoring cross-shard query overhead
• Underestimating transaction complexity

5. What is the time complexity of performing a nested loop join between two tables with sizes n and m respectively, assuming no indexes and a simple equality join condition?

medium

A. O(n + m), since each table is scanned once

B. O(n * m), because each row in the first table is compared to every row in the second

C. O(n log m), assuming the second table is sorted

D. O(n), if a hash map is used for lookups

Solution

1. Step 1: Analyze nested loops

   The outer loop runs n times, and for each iteration, the inner loop runs m times, leading to n * m comparisons.

2. Step 2: Confirm no indexing or hashing

   Since no hash map or index is used, no faster lookup is possible, so complexity remains O(n * m).

3. Final Answer:

   Option B -> Option B

4. Quick Check:

   Nested loops multiply iteration counts [OK]

Hint: Nested loops multiply table sizes for complexity [OK]

Common Mistakes:

• Assuming linear time due to scanning once
• Confusing sorting with hashing benefits