Attribute Closure

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101

from itertools import combinations
from typing import Set, List, Tuple, FrozenSet
 
def find_all_candidate_keys(
    R: Set[str], 
    F: List[Tuple[Set[str], Set[str]]]
) -> List[FrozenSet[str]]:
    """
    Find all candidate keys of relation R under FDs F.
    
    Returns list of candidate keys (each as frozenset for immutability).
    """
    # Step 1: Categorize attributes
    left_attrs = set()
    right_attrs = set()
    for det, dep in F:
        left_attrs |= det
        right_attrs |= dep
    
    L = left_attrs - right_attrs       # Left-only: MUST be in every key
    R_only = right_attrs - left_attrs  # Right-only: NEVER in any key
    B = left_attrs & right_attrs       # Both: MAY be in key
    N = R - (left_attrs | right_attrs) # Neither: MUST be in every key
    
    # Step 2: Compute mandatory base
    Must = L | N
    May = B
    
    # Step 3: Check if Must alone is sufficient
    if compute_closure(Must, F) == R:
        return [frozenset(Must)]
    
    # Step 4 & 5: Search for minimal supersets of Must
    candidate_keys = []
    May_list = sorted(May)  # Sort for deterministic order
    
    # Level-wise search: smallest subsets first
    for size in range(1, len(May) + 1):
        for subset in combinations(May_list, size):
            candidate = Must | set(subset)
            
            # Pruning: skip if superset of known candidate key
            candidate_frozen = frozenset(candidate)
            is_superset = any(
                ck < candidate_frozen  # strict subset
                for ck in candidate_keys
            )
            if is_superset:
                continue
            
            # Check if this is a superkey
            if compute_closure(candidate, F) == R:
                candidate_keys.append(candidate_frozen)
    
    return candidate_keys
 
 
def compute_closure(X: Set[str], F: List[Tuple[Set[str], Set[str]]]) -> Set[str]:
    """Compute attribute closure X⁺ under F."""
    result = set(X)
    changed = True
    while changed:
        changed = False
        for det, dep in F:
            if det <= result and not dep <= result:
                result |= dep
                changed = True
    return result
 
 
# ============ EXAMPLE USAGE ============
if __name__ == "__main__":
    # Example: R(A,B,C,D,E) with cyclic dependencies
    R = {'A', 'B', 'C', 'D', 'E'}
    F = [
        ({'A', 'B'}, {'C'}),   # AB → C
        ({'C'}, {'D'}),         # C → D
        ({'D'}, {'E'}),         # D → E
        ({'E'}, {'A'}),         # E → A  (creates cycle)
    ]
    
    keys = find_all_candidate_keys(R, F)
    print("Candidate Keys:")
    for k in keys:
        print(f"  {set(k)}")
    
    # Analysis:
    # L = {B} (B only on left)
    # R_only = {} (all right attrs also on left somewhere)
    # B = {A, C, D, E} (all appear on both sides)
    # N = {} 
    # Must = {B}
    #
    # {B}⁺ = {B} ≠ R, so we need to add from {A,C,D,E}
    # Due to cycle E→A, AB→C, C→D, D→E:
    # {B,A}⁺ = {A,B,C,D,E} ✓
    # {B,C}⁺ = {B,C,D,E,A} ✓
    # {B,D}⁺ = {B,D,E,A,C} ✓ (wait, need to verify)
    # {B,E}⁺ = {B,E,A,C,D} ✓
    #
    # All four are candidate keys: {AB}, {BC}, {BD}, {BE}

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54

def is_candidate_key(K: set, R: set, F: list) -> bool:
    """
    Verify if K is a candidate key (minimal superkey).
    
    Args:
        K: Proposed candidate key
        R: All attributes
        F: Functional dependencies
    
    Returns:
        True if K is a candidate key, False otherwise
    """
    # Step 1: Must be a superkey
    if compute_closure(K, F) != R:
        return False
    
    # Step 2: Check minimality
    for attr in K:
        K_minus_attr = K - {attr}
        if compute_closure(K_minus_attr, F) == R:
            # Found a smaller superkey!
            return False
    
    return True
 
 
def find_minimal_superkey(K: set, R: set, F: list) -> set:
    """
    Given a superkey K, find a minimal subset that's still a superkey.
    Useful for reducing a known superkey to a candidate key.
    """
    if compute_closure(K, F) != R:
        raise ValueError("K is not a superkey")
    
    minimal = set(K)
    for attr in list(K):  # Iterate over copy since we modify
        if attr in minimal:
            test = minimal - {attr}
            if compute_closure(test, F) == R:
                minimal = test
    
    return minimal
 
 
# Example
R = {'A', 'B', 'C', 'D'}
F = [({'A'}, {'B'}), ({'C'}, {'D'})]
 
K = {'A', 'B', 'C'}
print(f"{K} is candidate key: {is_candidate_key(K, R, F)}")  # False
 
minimal = find_minimal_superkey(K, R, F)
print(f"Minimal superkey from {K}: {minimal}")  # {A, C}
print(f"{minimal} is candidate key: {is_candidate_key(minimal, R, F)}")  # True

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
128
129
130
131
132
133
134
135
136

from itertools import combinations
from dataclasses import dataclass
from typing import Set, List, Tuple, FrozenSet
 
@dataclass
class KeyAnalysisResult:
    """Complete analysis of a relation's key structure."""
    candidate_keys: List[FrozenSet[str]]
    prime_attributes: Set[str]
    non_prime_attributes: Set[str]
    must_include: Set[str]  # L ∪ N
    never_include: Set[str]  # R
    optional: Set[str]  # B
    
    def summary(self) -> str:
        lines = [
            "=== Key Analysis Result ===",
            f"Candidate Keys: {len(self.candidate_keys)}",
        ]
        for i, key in enumerate(self.candidate_keys, 1):
            lines.append(f"  {i}. {set(key)}")
        lines.extend([
            f"Prime Attributes: {self.prime_attributes}",
            f"Non-Prime Attributes: {self.non_prime_attributes}",
            f"Must be in every key: {self.must_include}",
            f"Never in any key: {self.never_include}",
        ])
        return "\n".join(lines)
 
 
def analyze_keys(
    R: Set[str], 
    F: List[Tuple[Set[str], Set[str]]]
) -> KeyAnalysisResult:
    """
    Complete key analysis: find all candidate keys and classify attributes.
    """
    # Categorize attributes
    left_attrs = set()
    right_attrs = set()
    for det, dep in F:
        left_attrs |= det
        right_attrs |= dep
    
    L = left_attrs - right_attrs
    R_only = right_attrs - left_attrs
    B = left_attrs & right_attrs
    N = R - (left_attrs | right_attrs)
    
    Must = L | N
    
    # Find candidate keys
    candidate_keys = _find_keys(R, F, Must, B)
    
    # Compute prime/non-prime attributes
    prime = set()
    for key in candidate_keys:
        prime |= key
    non_prime = R - prime
    
    return KeyAnalysisResult(
        candidate_keys=candidate_keys,
        prime_attributes=prime,
        non_prime_attributes=non_prime,
        must_include=Must,
        never_include=R_only,
        optional=B
    )
 
 
def _find_keys(
    R: Set[str], 
    F: List[Tuple[Set[str], Set[str]]],
    Must: Set[str],
    May: Set[str]
) -> List[FrozenSet[str]]:
    """Internal: find all candidate keys given Must and May sets."""
    
    # Check if Must alone works
    if compute_closure(Must, F) == R:
        return [frozenset(Must)]
    
    candidate_keys = []
    May_list = sorted(May)
    
    # Level-wise search
    for size in range(1, len(May) + 1):
        for subset in combinations(May_list, size):
            candidate = Must | set(subset)
            candidate_frozen = frozenset(candidate)
            
            # Prune: skip supersets of found keys
            if any(ck < candidate_frozen for ck in candidate_keys):
                continue
            
            if compute_closure(candidate, F) == R:
                candidate_keys.append(candidate_frozen)
    
    return candidate_keys
 
 
def compute_closure(X: Set[str], F: List[Tuple[Set[str], Set[str]]]) -> Set[str]:
    """Compute X⁺ under F."""
    result = set(X)
    changed = True
    while changed:
        changed = False
        for det, dep in F:
            if det <= result and not dep <= result:
                result |= dep
                changed = True
    return result
 
 
# ============ DEMONSTRATION ============
if __name__ == "__main__":
    print("Example 1: Employee Relation")
    R1 = {'E', 'S', 'M', 'N', 'D', 'T'}
    F1 = [
        ({'E'}, {'S', 'M', 'N', 'D'}),
        ({'S'}, {'E'}),
        ({'M'}, {'E'}),
        ({'D'}, {'T'}),
    ]
    result1 = analyze_keys(R1, F1)
    print(result1.summary())
    print()
    
    print("Example 2: Cyclic Dependencies")
    R2 = {'A', 'B', 'C', 'D'}
    F2 = [
        ({'A'}, {'B'}), ({'B'}, {'A'}),
        ({'C'}, {'D'}), ({'D'}, {'C'}),
    ]
    result2 = analyze_keys(R2, F2)
    print(result2.summary())