Finding All Candidate Keys

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

def classify_attributes(all_attrs: set, fds: list[tuple[set, set]]) -> dict:
    """
    Classify all attributes based on FD appearance.
    
    Args:
        all_attrs: Complete set of attributes in the relation
        fds: List of functional dependencies as (lhs, rhs) tuples
    
    Returns:
        Dictionary with 'core', 'excluded', 'explore', and detailed categories
    """
    left_side = set()
    right_side = set()
    
    for lhs, rhs in fds:
        left_side.update(lhs)
        right_side.update(rhs)
    
    # The four categories
    l_only = left_side - right_side    # Only on left
    r_only = right_side - left_side    # Only on right
    both = left_side & right_side       # On both sides
    neither = all_attrs - left_side - right_side  # Not in any FD
    
    # Key-finding implications
    core = l_only | neither      # Must be in every key
    excluded = r_only            # Never in any key
    explore = both               # Need to try combinations
    
    return {
        'l_only': l_only,
        'r_only': r_only,
        'both': both,
        'neither': neither,
        'core': core,
        'excluded': excluded,
        'explore': explore
    }
 
 
def demonstrate_classification(name: str, all_attrs: set, fds: list):
    """Show classification results for a relation."""
    print(f"
{'='*60}")
    print(f"Relation: {name}")
    print(f"Attributes: {sorted(all_attrs)}")
    print(f"
Functional Dependencies:")
    for lhs, rhs in fds:
        print(f"  {sorted(lhs)} → {sorted(rhs)}")
    
    result = classify_attributes(all_attrs, fds)
    
    print(f"
Classification:")
    print(f"  L-only (must be in key):  {sorted(result['l_only'])}")
    print(f"  R-only (never in key):    {sorted(result['r_only'])}")
    print(f"  Both (explore):           {sorted(result['both'])}")
    print(f"  Neither (must be in key): {sorted(result['neither'])}")
    
    print(f"
Search Parameters:")
    print(f"  Core (definite): {sorted(result['core'])}")
    print(f"  Explore (try combinations of): {sorted(result['explore'])}")
    print(f"  Excluded (ignore): {sorted(result['excluded'])}")
    print(f"  Search space: 2^{len(result['explore'])} = {2**len(result['explore'])} combinations")
    print(f"{'='*60}")
 
 
# Examples
if __name__ == "__main__":
    # Example 1: Simple relation
    demonstrate_classification(
        "Employee(EmpID, Name, DeptID, Salary)",
        {"EmpID", "Name", "DeptID", "Salary"},
        [
            ({"EmpID"}, {"Name", "DeptID", "Salary"})
        ]
    )
    
    # Example 2: Multiple keys possible
    demonstrate_classification(
        "Student(SID, SSN, Email, Name, GPA)",
        {"SID", "SSN", "Email", "Name", "GPA"},
        [
            ({"SID"}, {"SSN", "Email", "Name", "GPA"}),
            ({"SSN"}, {"SID", "Email", "Name", "GPA"}),
            ({"Email"}, {"SID", "SSN", "Name", "GPA"})
        ]
    )
    
    # Example 3: Complex with explore attributes
    demonstrate_classification(
        "Enrollment(StudentID, CourseID, Semester, Grade, InstructorID)",
        {"StudentID", "CourseID", "Semester", "Grade", "InstructorID"},
        [
            ({"StudentID", "CourseID", "Semester"}, {"Grade", "InstructorID"}),
            ({"CourseID", "Semester"}, {"InstructorID"})
        ]
    )

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
137
138
139
140
141
142
143
144
145
146
147
148
149
150
151
152
153
154
155
156
157
158
159
160
161
162
163
164
165
166
167
168
169
170
171
172
173
174
175
176
177
178
179
180
181
182
183
184
185
186
187
188
189
190
191
192
193

from itertools import combinations
from functools import lru_cache
 
def compute_closure(attributes: frozenset, fds: tuple) -> frozenset:
    """
    Compute attribute closure with caching for efficiency.
    Uses immutable types for caching compatibility.
    """
    closure = set(attributes)
    changed = True
    
    while changed:
        changed = False
        for lhs, rhs in fds:
            if lhs.issubset(closure) and not rhs.issubset(closure):
                closure.update(rhs)
                changed = True
    
    return frozenset(closure)
 
 
def is_superkey(attrs: set, all_attrs: set, fds: list) -> bool:
    """Check if attribute set is a superkey."""
    fds_tuple = tuple((frozenset(lhs), frozenset(rhs)) for lhs, rhs in fds)
    closure = compute_closure(frozenset(attrs), fds_tuple)
    return set(closure) == all_attrs
 
 
def is_minimal_superkey(attrs: set, all_attrs: set, fds: list) -> bool:
    """Check if a superkey is minimal (i.e., a candidate key)."""
    if not is_superkey(attrs, all_attrs, fds):
        return False
    
    # Try removing each attribute
    for attr in attrs:
        subset = attrs - {attr}
        if subset and is_superkey(subset, all_attrs, fds):
            return False  # Not minimal
    
    return True
 
 
def find_all_candidate_keys(all_attrs: set, fds: list) -> list[set]:
    """
    Find ALL candidate keys for a relation.
    
    Uses attribute classification to minimize search space.
    Returns list of sets, each set being a candidate key.
    """
    # Step 1: Classify attributes
    classification = classify_attributes(all_attrs, fds)
    core = classification['core']
    explore = classification['explore']
    
    # Step 2: Check if core alone is sufficient
    if is_superkey(core, all_attrs, fds):
        # Core is a superkey; verify it's minimal
        if is_minimal_superkey(core, all_attrs, fds):
            return [core]
        else:
            # Shouldn't happen if classification is correct
            # But handle by reducing core
            pass
    
    # Handle edge case: empty core
    if not core:
        core = set()
    
    # Step 3: Try adding subsets of explore attributes
    candidate_keys = []
    
    # Start with smallest subsets for efficiency
    for size in range(len(explore) + 1):
        for subset in combinations(explore, size):
            candidate = core | set(subset)
            
            # Skip if we already have a proper subset that's a key
            is_superset_of_found_key = False
            for found_key in candidate_keys:
                if found_key < candidate:  # found_key is proper subset
                    is_superset_of_found_key = True
                    break
            
            if is_superset_of_found_key:
                continue
            
            # Check if this is a superkey
            if not is_superkey(candidate, all_attrs, fds):
                continue
            
            # Check if it's minimal
            if is_minimal_superkey(candidate, all_attrs, fds):
                candidate_keys.append(candidate)
    
    return candidate_keys if candidate_keys else [all_attrs]
 
 
def analyze_keys(name: str, all_attrs: set, fds: list):
    """Complete key analysis with detailed output."""
    print(f"
{'='*70}")
    print(f"CANDIDATE KEY ANALYSIS: {name}")
    print(f"{'='*70}")
    
    print(f"
Attributes: {sorted(all_attrs)}")
    print(f"
Functional Dependencies:")
    for lhs, rhs in fds:
        print(f"  {sorted(lhs)} → {sorted(rhs)}")
    
    # Classification
    classification = classify_attributes(all_attrs, fds)
    print(f"
Attribute Classification:")
    print(f"  Core (must be in key): {sorted(classification['core'])}")
    print(f"  Explore (may be in key): {sorted(classification['explore'])}")
    print(f"  Excluded (never in key): {sorted(classification['excluded'])}")
    
    # Find all candidate keys
    candidate_keys = find_all_candidate_keys(all_attrs, fds)
    
    print(f"
Candidate Keys Found: {len(candidate_keys)}")
    for i, key in enumerate(candidate_keys, 1):
        print(f"  Key {i}: {{{', '.join(sorted(key))}}}")
    
    # Verify each key
    print(f"
Verification:")
    for key in candidate_keys:
        fds_tuple = tuple((frozenset(lhs), frozenset(rhs)) for lhs, rhs in fds)
        closure = compute_closure(frozenset(key), fds_tuple)
        print(f"  {{{', '.join(sorted(key))}}}⁺ = {{{', '.join(sorted(closure))}}}")
    
    # Prime/Non-prime classification
    prime = set()
    for key in candidate_keys:
        prime.update(key)
    non_prime = all_attrs - prime
    
    print(f"
Attribute Status:")
    print(f"  Prime: {sorted(prime)}")
    print(f"  Non-prime: {sorted(non_prime)}")
    
    print(f"{'='*70}")
    
    return candidate_keys
 
 
# Comprehensive examples
if __name__ == "__main__":
    # Example 1: Single key
    analyze_keys(
        "Product(ProdID, Name, Category, Price)",
        {"ProdID", "Name", "Category", "Price"},
        [
            ({"ProdID"}, {"Name", "Category", "Price"})
        ]
    )
    
    # Example 2: Three equivalent keys
    analyze_keys(
        "Person(SSN, PassportNum, DriverLicense, Name, Address)",
        {"SSN", "PassportNum", "DriverLicense", "Name", "Address"},
        [
            ({"SSN"}, {"PassportNum", "DriverLicense", "Name", "Address"}),
            ({"PassportNum"}, {"SSN", "DriverLicense", "Name", "Address"}),
            ({"DriverLicense"}, {"SSN", "PassportNum", "Name", "Address"})
        ]
    )
    
    # Example 3: Cyclic dependencies
    analyze_keys(
        "Cycle(A, B, C, D, E)",
        {"A", "B", "C", "D", "E"},
        [
            ({"A"}, {"B"}),
            ({"B"}, {"C"}),
            ({"C"}, {"A"}),
            ({"D"}, {"E"})
        ]
    )
    
    # Example 4: Composite keys
    analyze_keys(
        "Enrollment(StudentID, CourseID, Semester, Grade)",
        {"StudentID", "CourseID", "Semester", "Grade"},
        [
            ({"StudentID", "CourseID", "Semester"}, {"Grade"})
        ]
    )

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

-- After discovering multiple candidate keys, 
-- implement them in the schema:
 
-- Example: Student table with three candidate keys
CREATE TABLE Student (
    -- Primary key: synthetic for stability
    StudentID INT PRIMARY KEY,
    
    -- Alternate key: government identifier
    SSN VARCHAR(11) NOT NULL UNIQUE,
    
    -- Alternate key: institutional identifier  
    Email VARCHAR(100) NOT NULL UNIQUE,
    
    -- Non-prime attributes
    Name VARCHAR(100) NOT NULL,
    Major VARCHAR(50),
    GPA DECIMAL(3,2),
    
    -- Document the key structure
    CONSTRAINT chk_ssn_format CHECK (SSN LIKE '___-__-____'),
    CONSTRAINT chk_email_format CHECK (Email LIKE '%@%.%')
);
 
-- Each UNIQUE constraint reflects a candidate key
-- and automatically creates an index
 
-- Reference can use any candidate key
CREATE TABLE Enrollment (
    EnrollmentID INT PRIMARY KEY,
    
    -- Could use any of these:
    StudentID INT REFERENCES Student(StudentID),
    -- OR: SSN VARCHAR(11) REFERENCES Student(SSN),
    -- OR: Email VARCHAR(100) REFERENCES Student(Email),
    
    CourseID INT NOT NULL,
    Semester VARCHAR(10) NOT NULL
);
 
-- Index all candidate keys for lookup efficiency
-- (UNIQUE constraints already create indexes, but explicit:)
-- CREATE INDEX idx_student_ssn ON Student(SSN);
-- CREATE INDEX idx_student_email ON Student(Email);