1"""
2Functional Dependencies and Armstrong's Axioms
3
4Demonstrates key concepts in functional dependency theory:
5- Functional dependencies (FDs): X → Y
6- Armstrong's axioms: reflexivity, augmentation, transitivity
7- Derived rules: union, decomposition, pseudotransitivity
8- Attribute closure: F+(X) - all attributes determined by X
9- Closure of FD set: F+ - all FDs implied by F
10- Candidate key finding
11- Minimal/Canonical cover of FDs
12
13Theory:
14- FD X → Y holds if whenever two tuples agree on X, they agree on Y
15- Armstrong's axioms are sound (only derive valid FDs) and complete (can derive all valid FDs)
16- Attribute closure is used to find keys and test FD membership
17- Minimal cover removes redundant FDs and extraneous attributes
18"""
19
20import sqlite3
21from typing import Set, List, Tuple, FrozenSet
22
23
24class FunctionalDependency:
25 """Represents a functional dependency X → Y."""
26
27 def __init__(self, lhs: Set[str], rhs: Set[str]):
28 """
29 Args:
30 lhs: Left-hand side (determinant) attributes
31 rhs: Right-hand side (dependent) attributes
32 """
33 self.lhs = frozenset(lhs)
34 self.rhs = frozenset(rhs)
35
36 def __repr__(self):
37 lhs_str = ''.join(sorted(self.lhs))
38 rhs_str = ''.join(sorted(self.rhs))
39 return f"{lhs_str} → {rhs_str}"
40
41 def __eq__(self, other):
42 return self.lhs == other.lhs and self.rhs == other.rhs
43
44 def __hash__(self):
45 return hash((self.lhs, self.rhs))
46
47
48def demonstrate_armstrong_axioms():
49 """Demonstrate Armstrong's axioms."""
50 print("=" * 60)
51 print("ARMSTRONG'S AXIOMS")
52 print("=" * 60)
53 print()
54
55 # Example: R(A, B, C, D) with FD: AB → C
56 print("Given: R(A, B, C, D) and FD: AB → C")
57 print()
58
59 # Axiom 1: Reflexivity
60 print("1. REFLEXIVITY: If Y ⊆ X, then X → Y")
61 print("-" * 60)
62 print(" AB → A (trivial)")
63 print(" AB → B (trivial)")
64 print(" AB → AB (trivial)")
65 print(" (These hold by definition)\n")
66
67 # Axiom 2: Augmentation
68 print("2. AUGMENTATION: If X → Y, then XZ → YZ")
69 print("-" * 60)
70 print(" Given: AB → C")
71 print(" Add D to both sides: ABD → CD")
72 print(" (If AB determines C, then AB with D also determines C and D)\n")
73
74 # Axiom 3: Transitivity
75 print("3. TRANSITIVITY: If X → Y and Y → Z, then X → Z")
76 print("-" * 60)
77 print(" Example chain:")
78 print(" If AB → C and C → D, then AB → D")
79 print(" (Dependencies chain together)\n")
80
81 print("=" * 60)
82 print("DERIVED RULES")
83 print("=" * 60)
84 print()
85
86 # Union rule
87 print("4. UNION: If X → Y and X → Z, then X → YZ")
88 print("-" * 60)
89 print(" Derived from augmentation + transitivity")
90 print(" If AB → C and AB → D, then AB → CD\n")
91
92 # Decomposition rule
93 print("5. DECOMPOSITION: If X → YZ, then X → Y and X → Z")
94 print("-" * 60)
95 print(" Derived from reflexivity + transitivity")
96 print(" If AB → CD, then AB → C and AB → D\n")
97
98 # Pseudotransitivity
99 print("6. PSEUDOTRANSITIVITY: If X → Y and YW → Z, then XW → Z")
100 print("-" * 60)
101 print(" Derived from augmentation + transitivity")
102 print(" If A → B and BC → D, then AC → D\n")
103
104
105def compute_closure(attributes: Set[str], fds: Set[FunctionalDependency]) -> Set[str]:
106 """
107 Compute attribute closure: X+ under F.
108
109 Algorithm:
110 1. Start with result = X
111 2. Repeat until no change:
112 - For each FD Y → Z in F:
113 - If Y ⊆ result, add Z to result
114 3. Return result
115
116 Args:
117 attributes: Set of attributes to close
118 fds: Set of functional dependencies
119
120 Returns:
121 Closure of attributes (all attributes determined by input)
122 """
123 closure = set(attributes)
124 changed = True
125
126 while changed:
127 changed = False
128 for fd in fds:
129 # If LHS is subset of current closure, add RHS
130 if fd.lhs.issubset(closure):
131 before_size = len(closure)
132 closure.update(fd.rhs)
133 if len(closure) > before_size:
134 changed = True
135
136 return closure
137
138
139def demonstrate_attribute_closure():
140 """Demonstrate attribute closure computation."""
141 print("=" * 60)
142 print("ATTRIBUTE CLOSURE")
143 print("=" * 60)
144 print()
145
146 # Example from database theory textbook
147 print("Given: R(A, B, C, D, E, F)")
148 print("FDs: {A → BC, B → E, CD → F}")
149 print()
150
151 fds = {
152 FunctionalDependency({'A'}, {'B', 'C'}),
153 FunctionalDependency({'B'}, {'E'}),
154 FunctionalDependency({'C', 'D'}, {'F'})
155 }
156
157 # Compute {A}+
158 print("Computing {A}+:")
159 print("-" * 60)
160 closure = compute_closure({'A'}, fds)
161 print(f" Start with: {{A}}")
162 print(f" A → BC applies: {{A, B, C}}")
163 print(f" B → E applies: {{A, B, C, E}}")
164 print(f" CD → F doesn't apply (no D)")
165 print(f" Final: {A}+ = {{{', '.join(sorted(closure))}}}\n")
166
167 # Compute {A, D}+
168 print("Computing {AD}+:")
169 print("-" * 60)
170 closure = compute_closure({'A', 'D'}, fds)
171 print(f" Start with: {{A, D}}")
172 print(f" A → BC applies: {{A, B, C, D}}")
173 print(f" B → E applies: {{A, B, C, D, E}}")
174 print(f" CD → F applies: {{A, B, C, D, E, F}}")
175 print(f" Final: {{AD}}+ = {{{', '.join(sorted(closure))}}}")
176 print(f" ✓ AD is a superkey (determines all attributes)\n")
177
178 # Compute {B}+
179 print("Computing {B}+:")
180 print("-" * 60)
181 closure = compute_closure({'B'}, fds)
182 print(f" Start with: {{B}}")
183 print(f" B → E applies: {{B, E}}")
184 print(f" No other FDs apply")
185 print(f" Final: {{B}}+ = {{{', '.join(sorted(closure))}}}")
186 print(f" ✗ B is not a superkey\n")
187
188
189def find_candidate_keys(all_attrs: Set[str], fds: Set[FunctionalDependency]) -> List[FrozenSet[str]]:
190 """
191 Find all candidate keys for a relation.
192
193 Algorithm:
194 1. Find attributes that never appear on RHS (must be in every key)
195 2. Check if these alone form a key
196 3. If not, systematically add other attributes
197 4. Remove supersets (keep only minimal keys)
198
199 Args:
200 all_attrs: All attributes in the relation
201 fds: Set of functional dependencies
202
203 Returns:
204 List of candidate keys (minimal superkeys)
205 """
206 # Attributes that never appear on RHS must be in every key
207 rhs_attrs = set()
208 for fd in fds:
209 rhs_attrs.update(fd.rhs)
210 must_include = all_attrs - rhs_attrs
211
212 # Check if must_include alone is a key
213 if compute_closure(must_include, fds) == all_attrs:
214 return [frozenset(must_include)]
215
216 # Try adding other attributes
217 candidate_keys = []
218 other_attrs = list(all_attrs - must_include)
219
220 # Generate all possible combinations
221 from itertools import combinations
222 for size in range(1, len(other_attrs) + 1):
223 for combo in combinations(other_attrs, size):
224 candidate = must_include | set(combo)
225 if compute_closure(candidate, fds) == all_attrs:
226 # Check if it's minimal (no proper subset is also a key)
227 is_minimal = True
228 for attr in combo:
229 subset = candidate - {attr}
230 if compute_closure(subset, fds) == all_attrs:
231 is_minimal = False
232 break
233 if is_minimal:
234 candidate_keys.append(frozenset(candidate))
235
236 return candidate_keys if candidate_keys else [frozenset(must_include)]
237
238
239def demonstrate_candidate_keys():
240 """Demonstrate finding candidate keys."""
241 print("=" * 60)
242 print("FINDING CANDIDATE KEYS")
243 print("=" * 60)
244 print()
245
246 print("Example 1: R(A, B, C, D)")
247 print("FDs: {A → B, B → C, C → D}")
248 print("-" * 60)
249
250 fds1 = {
251 FunctionalDependency({'A'}, {'B'}),
252 FunctionalDependency({'B'}, {'C'}),
253 FunctionalDependency({'C'}, {'D'})
254 }
255
256 keys1 = find_candidate_keys({'A', 'B', 'C', 'D'}, fds1)
257 print(f"Candidate keys: {['{' + ''.join(sorted(k)) + '}' for k in keys1]}")
258 print(f"Explanation: A doesn't appear on RHS, so it must be in every key")
259 print(f" A+ = {{A,B,C,D}}, so {{A}} is the only candidate key\n")
260
261 print("Example 2: R(A, B, C, D)")
262 print("FDs: {AB → C, C → D, D → A}")
263 print("-" * 60)
264
265 fds2 = {
266 FunctionalDependency({'A', 'B'}, {'C'}),
267 FunctionalDependency({'C'}, {'D'}),
268 FunctionalDependency({'D'}, {'A'})
269 }
270
271 keys2 = find_candidate_keys({'A', 'B', 'C', 'D'}, fds2)
272 print(f"Candidate keys: {['{' + ''.join(sorted(k)) + '}' for k in keys2]}")
273 print(f"Explanation: B doesn't appear on RHS, so it must be in every key")
274 print(f" {AB}+ = {{A,B,C,D}}, so {{AB}} is a candidate key")
275 print(f" {BC}+ = {{A,B,C,D}}, so {{BC}} is a candidate key")
276 print(f" {BD}+ = {{A,B,C,D}}, so {{BD}} is a candidate key\n")
277
278
279def compute_minimal_cover(fds: Set[FunctionalDependency]) -> Set[FunctionalDependency]:
280 """
281 Compute minimal (canonical) cover of FDs.
282
283 Algorithm:
284 1. Decompose RHS to single attributes (F → {A→B, A→C} instead of A→BC)
285 2. Remove extraneous attributes from LHS
286 3. Remove redundant FDs
287
288 Args:
289 fds: Set of functional dependencies
290
291 Returns:
292 Minimal cover of FDs
293 """
294 # Step 1: Decompose RHS to single attributes
295 decomposed = set()
296 for fd in fds:
297 for attr in fd.rhs:
298 decomposed.add(FunctionalDependency(fd.lhs, {attr}))
299
300 # Step 2: Remove extraneous attributes from LHS
301 result = set(decomposed)
302 changed = True
303 while changed:
304 changed = False
305 for fd in list(result):
306 if len(fd.lhs) > 1:
307 # Try removing each attribute from LHS
308 for attr in fd.lhs:
309 reduced_lhs = fd.lhs - {attr}
310 # Check if fd is still implied
311 other_fds = result - {fd}
312 closure = compute_closure(reduced_lhs, other_fds)
313 if fd.rhs.issubset(closure):
314 # attr is extraneous
315 result.remove(fd)
316 result.add(FunctionalDependency(reduced_lhs, fd.rhs))
317 changed = True
318 break
319 if changed:
320 break
321
322 # Step 3: Remove redundant FDs
323 final = set()
324 for fd in result:
325 # Check if fd is implied by others
326 other_fds = result - {fd}
327 closure = compute_closure(fd.lhs, other_fds)
328 if not fd.rhs.issubset(closure):
329 # fd is not redundant
330 final.add(fd)
331
332 return final
333
334
335def demonstrate_minimal_cover():
336 """Demonstrate computing minimal cover."""
337 print("=" * 60)
338 print("MINIMAL (CANONICAL) COVER")
339 print("=" * 60)
340 print()
341
342 print("Given FDs:")
343 print("-" * 60)
344 fds = {
345 FunctionalDependency({'A', 'B'}, {'C'}),
346 FunctionalDependency({'A'}, {'B', 'C'}),
347 FunctionalDependency({'B'}, {'C'}),
348 FunctionalDependency({'A'}, {'B'})
349 }
350 for fd in sorted(fds, key=str):
351 print(f" {fd}")
352
353 print("\nComputing minimal cover:")
354 print("-" * 60)
355
356 # Step 1: Decompose
357 print("Step 1: Decompose RHS to single attributes")
358 decomposed = set()
359 for fd in fds:
360 for attr in fd.rhs:
361 decomposed.add(FunctionalDependency(fd.lhs, {attr}))
362 for fd in sorted(decomposed, key=str):
363 print(f" {fd}")
364
365 # Compute minimal cover
366 minimal = compute_minimal_cover(fds)
367
368 print("\nStep 2-3: Remove extraneous attributes and redundant FDs")
369 print("Final minimal cover:")
370 for fd in sorted(minimal, key=str):
371 print(f" {fd}")
372
373 print("\nExplanation:")
374 print(" - A → BC decomposed to A → B and A → C")
375 print(" - AB → C is redundant (A → C already exists)")
376 print(" - B → C is redundant (implied by A → B and A → C)")
377 print(" - A → C is redundant (implied by A → B and B → C)")
378 print(" - Result: {A → B, B → C}\n")
379
380
381if __name__ == "__main__":
382 print("""
383╔══════════════════════════════════════════════════════════════╗
384║ FUNCTIONAL DEPENDENCIES THEORY ║
385║ Armstrong's Axioms, Closure, Keys, Minimal Cover ║
386╚══════════════════════════════════════════════════════════════╝
387""")
388
389 demonstrate_armstrong_axioms()
390 demonstrate_attribute_closure()
391 demonstrate_candidate_keys()
392 demonstrate_minimal_cover()
393
394 print("=" * 60)
395 print("SUMMARY")
396 print("=" * 60)
397 print("Armstrong's Axioms (sound and complete):")
398 print(" - Reflexivity: Y ⊆ X ⟹ X → Y")
399 print(" - Augmentation: X → Y ⟹ XZ → YZ")
400 print(" - Transitivity: X → Y, Y → Z ⟹ X → Z")
401 print()
402 print("Key algorithms:")
403 print(" - Attribute closure: Find X+ to test superkeys")
404 print(" - Candidate keys: Minimal superkeys")
405 print(" - Minimal cover: Remove redundancy in FD set")
406 print("=" * 60)