· 6 years ago · Sep 20, 2019, 12:40 PM
1{
2 "cells": [
3 {
4 "cell_type": "markdown",
5 "metadata": {},
6 "source": [
7 "# TP1 - Finding Keys using Functional Dependencies \n",
8 "--------------------------\n",
9 "\n",
10 "In this lab, we are going to learn \n",
11 "\n",
12 "- how to use Jupyter\n",
13 "- how to use SQLite\n",
14 "- how to discover keys in relations\n",
15 "\n",
16 "## How to use Jupyter\n",
17 "\n",
18 "To execute a cell, click on it, and then use SHIFT+ENTER (this will execute the contents of the cell, and move down to the next one!)\n",
19 "\n",
20 "To edit a cell, click on it. If the cell uses markdown code, then use ENTER to edit it.\n",
21 "\n",
22 "See the Help menu for other useful keyboard commands. You can always use the menu bar instead as well.\n"
23 ]
24 },
25 {
26 "cell_type": "code",
27 "execution_count": 1,
28 "metadata": {
29 "collapsed": false
30 },
31 "outputs": [
32 {
33 "name": "stdout",
34 "output_type": "stream",
35 "text": [
36 "Hello world!\n"
37 ]
38 }
39 ],
40 "source": [
41 "print(\"Hello world!\")"
42 ]
43 },
44 {
45 "cell_type": "markdown",
46 "metadata": {},
47 "source": [
48 "Another example:"
49 ]
50 },
51 {
52 "cell_type": "code",
53 "execution_count": 2,
54 "metadata": {
55 "collapsed": false
56 },
57 "outputs": [
58 {
59 "name": "stdout",
60 "output_type": "stream",
61 "text": [
62 "1\n",
63 "2\n",
64 "3\n",
65 "4\n",
66 "5\n",
67 "6\n",
68 "7\n",
69 "8\n",
70 "9\n"
71 ]
72 }
73 ],
74 "source": [
75 "for i in range(1,10):\n",
76 " print(i)"
77 ]
78 },
79 {
80 "cell_type": "markdown",
81 "metadata": {},
82 "source": [
83 "#### Exercise 1\n",
84 "\n",
85 "Print numbers 1 to 9 in reverse order"
86 ]
87 },
88 {
89 "cell_type": "code",
90 "execution_count": 1,
91 "metadata": {
92 "collapsed": false
93 },
94 "outputs": [
95 {
96 "name": "stdout",
97 "output_type": "stream",
98 "text": [
99 "9\n",
100 "8\n",
101 "7\n",
102 "6\n",
103 "5\n",
104 "4\n",
105 "3\n",
106 "2\n",
107 "1\n"
108 ]
109 }
110 ],
111 "source": [
112 "for i in range(1,10):\n",
113 " print(10-i)"
114 ]
115 },
116 {
117 "cell_type": "markdown",
118 "metadata": {},
119 "source": [
120 "## How to use SQLite\n",
121 "\n",
122 "To work with SQL easily in a notebook, we'll load the ipython-sql extension as follows:"
123 ]
124 },
125 {
126 "cell_type": "code",
127 "execution_count": 2,
128 "metadata": {
129 "collapsed": false
130 },
131 "outputs": [
132 {
133 "data": {
134 "text/plain": [
135 "'Connected: @None'"
136 ]
137 },
138 "execution_count": 2,
139 "metadata": {},
140 "output_type": "execute_result"
141 }
142 ],
143 "source": [
144 "%load_ext sql\n",
145 "%sql sqlite://"
146 ]
147 },
148 {
149 "cell_type": "markdown",
150 "metadata": {},
151 "source": [
152 "We are going to create a table:"
153 ]
154 },
155 {
156 "cell_type": "code",
157 "execution_count": 3,
158 "metadata": {
159 "collapsed": false
160 },
161 "outputs": [
162 {
163 "name": "stdout",
164 "output_type": "stream",
165 "text": [
166 " * sqlite://\n",
167 "Done.\n",
168 "Done.\n",
169 "1 rows affected.\n",
170 "1 rows affected.\n",
171 "1 rows affected.\n"
172 ]
173 },
174 {
175 "data": {
176 "text/plain": [
177 "[]"
178 ]
179 },
180 "execution_count": 3,
181 "metadata": {},
182 "output_type": "execute_result"
183 }
184 ],
185 "source": [
186 "%%sql DROP TABLE IF EXISTS T;\n",
187 "CREATE TABLE T(course VARCHAR, classroom INT, time INT);\n",
188 "INSERT INTO T VALUES ('CS 364', 132, 900);\n",
189 "INSERT INTO T VALUES ('CS 245', 140, 1000);\n",
190 "INSERT INTO T VALUES ('EE 101', 210, 900);"
191 ]
192 },
193 {
194 "cell_type": "markdown",
195 "metadata": {},
196 "source": [
197 "Let's run our first SQL query:"
198 ]
199 },
200 {
201 "cell_type": "code",
202 "execution_count": 4,
203 "metadata": {
204 "collapsed": false
205 },
206 "outputs": [
207 {
208 "name": "stdout",
209 "output_type": "stream",
210 "text": [
211 " * sqlite://\n",
212 "Done.\n"
213 ]
214 },
215 {
216 "data": {
217 "text/html": [
218 "<table>\n",
219 " <tr>\n",
220 " <th>course</th>\n",
221 " <th>classroom</th>\n",
222 " <th>time</th>\n",
223 " </tr>\n",
224 " <tr>\n",
225 " <td>CS 364</td>\n",
226 " <td>132</td>\n",
227 " <td>900</td>\n",
228 " </tr>\n",
229 " <tr>\n",
230 " <td>CS 245</td>\n",
231 " <td>140</td>\n",
232 " <td>1000</td>\n",
233 " </tr>\n",
234 " <tr>\n",
235 " <td>EE 101</td>\n",
236 " <td>210</td>\n",
237 " <td>900</td>\n",
238 " </tr>\n",
239 "</table>"
240 ],
241 "text/plain": [
242 "[(u'CS 364', 132, 900), (u'CS 245', 140, 1000), (u'EE 101', 210, 900)]"
243 ]
244 },
245 "execution_count": 4,
246 "metadata": {},
247 "output_type": "execute_result"
248 }
249 ],
250 "source": [
251 "%sql SELECT * FROM T;"
252 ]
253 },
254 {
255 "cell_type": "markdown",
256 "metadata": {},
257 "source": [
258 "#### Exercise 2\n",
259 "\n",
260 "List the name of the courses with time less than 950"
261 ]
262 },
263 {
264 "cell_type": "code",
265 "execution_count": 5,
266 "metadata": {
267 "collapsed": false
268 },
269 "outputs": [
270 {
271 "name": "stdout",
272 "output_type": "stream",
273 "text": [
274 " * sqlite://\n",
275 "Done.\n"
276 ]
277 },
278 {
279 "data": {
280 "text/html": [
281 "<table>\n",
282 " <tr>\n",
283 " <th>course</th>\n",
284 " </tr>\n",
285 " <tr>\n",
286 " <td>CS 364</td>\n",
287 " </tr>\n",
288 " <tr>\n",
289 " <td>EE 101</td>\n",
290 " </tr>\n",
291 "</table>"
292 ],
293 "text/plain": [
294 "[(u'CS 364',), (u'EE 101',)]"
295 ]
296 },
297 "execution_count": 5,
298 "metadata": {},
299 "output_type": "execute_result"
300 }
301 ],
302 "source": [
303 "%sql SELECT course FROM T WHERE time<=950;"
304 ]
305 },
306 {
307 "cell_type": "markdown",
308 "metadata": {},
309 "source": [
310 "## How to discover keys in relations\n",
311 "\n",
312 "Now, we are going to work with functional dependencies, keys and closures. Our final goal is going to build a method to find keys in a relation.\n",
313 "\n",
314 "### Functional Dependencies\n",
315 "\n",
316 "Recall that given a set of attributes $\\{A_1, \\dots, A_n\\}$ and a set of FDs $\\Gamma$\n",
317 "\n",
318 "The closure, denoted $\\{A_1, \\dots, A_n\\}^+$, is defined to be the largest set of attributes B s.t. $$A_1,\\dots,A_n \\rightarrow B \\text{ using } \\Gamma.$$\n",
319 "\n",
320 "We're going to use some functions to compute the closure of a set of attributes and other such operations (_from CS145 Stanford_)"
321 ]
322 },
323 {
324 "cell_type": "code",
325 "execution_count": 6,
326 "metadata": {
327 "collapsed": true
328 },
329 "outputs": [],
330 "source": [
331 "# Source code\n",
332 "\n",
333 "def to_set(x):\n",
334 " \"\"\"Convert input int, string, list, tuple, set -> set\"\"\"\n",
335 " if type(x) == set:\n",
336 " return x\n",
337 " elif type(x) in [list, set]:\n",
338 " return set(x)\n",
339 " elif type(x) in [str, int]:\n",
340 " return set([x])\n",
341 " else:\n",
342 " raise Exception(\"Unrecognized type.\")\n",
343 "\n",
344 "def fd_to_str(lr_tuple):\n",
345 " lhs = lr_tuple[0]\n",
346 " rhs = lr_tuple[1]\n",
347 " return \",\".join(to_set(lhs)) + \" -> \" + \",\".join(to_set(rhs))\n",
348 "\n",
349 "def fds_to_str(fds): return \"\\n\\t\".join(map(fd_to_str, fds))\n",
350 "\n",
351 "def set_to_str(x): return \"{\" + \",\".join(x) + \"}\"\n",
352 "\n",
353 "def fd_applies_to(fd, x): \n",
354 " lhs, rhs = map(to_set, fd)\n",
355 " return lhs.issubset(x)\n",
356 "\n",
357 "def print_setup(A, fds):\n",
358 " print(\"Attributes = \" + set_to_str(A))\n",
359 " print(\"FDs = \\t\" + fds_to_str(fds))\n",
360 "\n",
361 "def print_fds(fds):\n",
362 " print(\"FDs = \\t\" + fds_to_str(fds)) \n"
363 ]
364 },
365 {
366 "cell_type": "markdown",
367 "metadata": {},
368 "source": [
369 "Now, let's look at a concrete example. For example, the code for\n",
370 "\n",
371 "attributes = { name, category, color, department, price}\n",
372 "\n",
373 "and functional dependencies:\n",
374 "\n",
375 "name $\\rightarrow$ color\n",
376 "\n",
377 "category $\\rightarrow$ department\n",
378 "\n",
379 "color, category $\\rightarrow$ price\n",
380 "\n",
381 "is the following:"
382 ]
383 },
384 {
385 "cell_type": "code",
386 "execution_count": 7,
387 "metadata": {
388 "collapsed": false
389 },
390 "outputs": [
391 {
392 "name": "stdout",
393 "output_type": "stream",
394 "text": [
395 "Attributes = {category,color,price,department,name}\n",
396 "FDs = \tname -> color\n",
397 "\tcategory -> department\n",
398 "\tcolor,category -> price\n"
399 ]
400 }
401 ],
402 "source": [
403 "attributes = set([\"name\", \"category\", \"color\", \"department\", \"price\"]) # These are the attribute set.\n",
404 "fds = [(set([\"name\"]),\"color\"),\n",
405 " (set([\"category\"]), \"department\"),\n",
406 " (set([\"color\", \"category\"]), \"price\")]\n",
407 "\n",
408 "print_setup(attributes, fds)"
409 ]
410 },
411 {
412 "cell_type": "markdown",
413 "metadata": {},
414 "source": [
415 "### Closure of a set of Attributes\n",
416 "\n",
417 "Let's implement the algorithm for obtaining the closure of a set of attributes:"
418 ]
419 },
420 {
421 "cell_type": "code",
422 "execution_count": 8,
423 "metadata": {
424 "collapsed": true
425 },
426 "outputs": [],
427 "source": [
428 "def compute_closure(x, fds, verbose=False):\n",
429 " bChanged = True # We will repeat until there are no changes.\n",
430 " x_ret = x.copy() # Make a copy of the input to hold x^{+}\n",
431 " while bChanged:\n",
432 " bChanged = False # Must change on each iteration\n",
433 " for fd in fds: # loop through all the FDs.\n",
434 " (lhs, rhs) = map(to_set, fd) # recall: lhs -> rhs\n",
435 " if fd_applies_to(fd, x_ret) and not rhs.issubset(x_ret):\n",
436 " x_ret = x_ret.union(rhs)\n",
437 " if verbose:\n",
438 " print(\"Using FD \" + fd_to_str(fd))\n",
439 " print(\"\\t Updated x to \" + set_to_str(x_ret))\n",
440 " bChanged = True\n",
441 " return x_ret"
442 ]
443 },
444 {
445 "cell_type": "markdown",
446 "metadata": {},
447 "source": [
448 "As an example, let's compute the closure for the attribute \"name\":"
449 ]
450 },
451 {
452 "cell_type": "code",
453 "execution_count": 9,
454 "metadata": {
455 "collapsed": false
456 },
457 "outputs": [
458 {
459 "name": "stdout",
460 "output_type": "stream",
461 "text": [
462 "Using FD name -> color\n",
463 "\t Updated x to {color,name}\n"
464 ]
465 },
466 {
467 "data": {
468 "text/plain": [
469 "{'color', 'name'}"
470 ]
471 },
472 "execution_count": 9,
473 "metadata": {},
474 "output_type": "execute_result"
475 }
476 ],
477 "source": [
478 "A = set([\"name\"])\n",
479 "compute_closure(A,fds, True)"
480 ]
481 },
482 {
483 "cell_type": "markdown",
484 "metadata": {},
485 "source": [
486 "#### Exercise 3\n",
487 "\n",
488 "Is the attribute \"name\" a superkey for this relation? Why?"
489 ]
490 },
491 {
492 "cell_type": "raw",
493 "metadata": {},
494 "source": [
495 "No because the closure of \"name\" is not equal to all the attributes."
496 ]
497 },
498 {
499 "cell_type": "markdown",
500 "metadata": {},
501 "source": [
502 "### Keys and Superkeys\n",
503 "\n",
504 "Next, we'll add some new functions now for finding superkeys and keys. Recall:\n",
505 "* A _superkey_ for a relation $R(B_1,\\dots,B_m)$ is a set of attributes $\\{A_1,\\dots,A_n\\}$ s.t.\n",
506 "$$ \\{A_1,\\dots,A_n\\} \\rightarrow B_{j} \\text{ for all } j=1,\\dots m$$\n",
507 "* A _key_ is a minimal (setwise) _superkey_\n",
508 "\n",
509 "The algorithm to determine if a set of attributes $A$ is a superkey for $X$ is actually very simple (check if $A^+=X$):"
510 ]
511 },
512 {
513 "cell_type": "code",
514 "execution_count": 10,
515 "metadata": {
516 "collapsed": true
517 },
518 "outputs": [],
519 "source": [
520 "def is_superkey_for(A, X, fds, verbose=False): \n",
521 " return X.issubset(compute_closure(A, fds, verbose=verbose))"
522 ]
523 },
524 {
525 "cell_type": "markdown",
526 "metadata": {},
527 "source": [
528 "Is \"name\" a superkey of the relation?"
529 ]
530 },
531 {
532 "cell_type": "code",
533 "execution_count": 11,
534 "metadata": {
535 "collapsed": false
536 },
537 "outputs": [
538 {
539 "data": {
540 "text/plain": [
541 "False"
542 ]
543 },
544 "execution_count": 11,
545 "metadata": {},
546 "output_type": "execute_result"
547 }
548 ],
549 "source": [
550 "is_superkey_for(A, attributes, fds)"
551 ]
552 },
553 {
554 "cell_type": "markdown",
555 "metadata": {},
556 "source": [
557 "Then, to check if $A$ is a key for $X$, we just confirm that:\n",
558 "* (a) it is a superkey\n",
559 "* (b) there are no smaller superkeys (_Note that we only need to check for superkeys of one size smaller_)"
560 ]
561 },
562 {
563 "cell_type": "code",
564 "execution_count": 13,
565 "metadata": {
566 "collapsed": true
567 },
568 "outputs": [],
569 "source": [
570 "import itertools\n",
571 "def is_key_for(A, X, fds, verbose=False):\n",
572 " subsets = set(itertools.combinations(A, len(A)-1))\n",
573 " return is_superkey_for(A, X, fds) and \\\n",
574 " all([not is_superkey_for(set(SA), X, fds) for SA in subsets])"
575 ]
576 },
577 {
578 "cell_type": "markdown",
579 "metadata": {},
580 "source": [
581 "Now, let's look at another example:\n",
582 "\n",
583 "attributes = { cru, type, client, remise}\n",
584 "\n",
585 "and functional dependencies:\n",
586 "\n",
587 "cru $\\rightarrow$ type\n",
588 "\n",
589 "type, client $\\rightarrow$ remise\n",
590 "\n",
591 "#### Exercise 4\n",
592 "\n",
593 "Is \"cru\" and \"client\" a key of the relation? Why?"
594 ]
595 },
596 {
597 "cell_type": "code",
598 "execution_count": 14,
599 "metadata": {
600 "collapsed": false
601 },
602 "outputs": [
603 {
604 "name": "stdout",
605 "output_type": "stream",
606 "text": [
607 "True\n"
608 ]
609 }
610 ],
611 "source": [
612 "attributes = set([\"cru\", \"type\", \"client\", \"remise\"]) # These are the attribute set.\n",
613 "fds = [(set([\"cru\"]),\"type\"),\n",
614 " (set([\"type\", \"client\"]), \"remise\")]\n",
615 "A = set([\"cru\",\"client\"])\n",
616 "print(is_key_for(A,attributes,fds,verbose=False))\n"
617 ]
618 },
619 {
620 "cell_type": "markdown",
621 "metadata": {},
622 "source": [
623 "Because it's a superkey and it is minimal. There is no superkey of size one. {clu, client} is a superkey of size two so it is a key."
624 ]
625 },
626 {
627 "cell_type": "markdown",
628 "metadata": {},
629 "source": [
630 "### Closure of a set of functional dependencies\n",
631 "\n",
632 "The algorithm to find the closure of a set of functional dependencies is the following:"
633 ]
634 },
635 {
636 "cell_type": "code",
637 "execution_count": 15,
638 "metadata": {
639 "collapsed": true
640 },
641 "outputs": [],
642 "source": [
643 "import itertools\n",
644 "def findsubsets(S,m):\n",
645 " return set(itertools.combinations(S, m))\n",
646 "def closure(X, fds, verbose=False):\n",
647 " c = []\n",
648 " for size in range(1, len(X)):\n",
649 " subsets = findsubsets(X, size) \n",
650 " for SA in subsets: # loop through all the subsets.\n",
651 " cl = compute_closure(set(SA), fds, verbose)\n",
652 " if len(cl.difference(SA)) > 0: \n",
653 " c.extend([(set(SA), cl.difference(SA))])\n",
654 " return c"
655 ]
656 },
657 {
658 "cell_type": "markdown",
659 "metadata": {},
660 "source": [
661 "Let's see some examples of how to use it:"
662 ]
663 },
664 {
665 "cell_type": "code",
666 "execution_count": 16,
667 "metadata": {
668 "collapsed": false
669 },
670 "outputs": [
671 {
672 "name": "stdout",
673 "output_type": "stream",
674 "text": [
675 "FDs = \tB -> D\n",
676 "\tC,B -> D\n",
677 "\tA,D -> C,B\n",
678 "\tA,B -> C,D\n",
679 "\tA,C,B -> D\n",
680 "\tA,B,D -> C\n",
681 "\tA,C,D -> B\n"
682 ]
683 }
684 ],
685 "source": [
686 "attributes1 = set(['A', 'B', 'C', 'D'])\n",
687 "fds1 = [(set(['A', 'B']), 'C'),\n",
688 " (set(['A', 'D']), 'B'),\n",
689 " (set(['B']), 'D')]\n",
690 "print_fds(closure(attributes1, fds1))\n"
691 ]
692 },
693 {
694 "cell_type": "code",
695 "execution_count": 17,
696 "metadata": {
697 "collapsed": false
698 },
699 "outputs": [
700 {
701 "name": "stdout",
702 "output_type": "stream",
703 "text": [
704 "FDs = \tCRU -> TYPE\n",
705 "\tCLIENT,TYPE -> REMISE\n",
706 "\tCLIENT,CRU -> REMISE,TYPE\n",
707 "\tCRU,REMISE -> TYPE\n",
708 "\tCLIENT,CRU,REMISE -> TYPE\n",
709 "\tCLIENT,TYPE,CRU -> REMISE\n"
710 ]
711 }
712 ],
713 "source": [
714 "attributes2 = set (['CRU', 'TYPE', 'CLIENT', 'REMISE'])\n",
715 "fds2 = [(set(['CRU']), 'TYPE'),\n",
716 " (set(['TYPE', 'CLIENT']), 'REMISE')]\n",
717 "print_fds(closure(attributes2, fds2))"
718 ]
719 },
720 {
721 "cell_type": "code",
722 "execution_count": 23,
723 "metadata": {
724 "collapsed": false
725 },
726 "outputs": [
727 {
728 "name": "stdout",
729 "output_type": "stream",
730 "text": [
731 "FDs = \tN VEH -> COULEUR,MARQUE,TYPE,PUISSANCE\n",
732 "\tTYPE -> PUISSANCE,MARQUE\n",
733 "\tMARQUE,TYPE -> PUISSANCE\n",
734 "\tPUISSANCE,TYPE -> MARQUE\n",
735 "\tN VEH,TYPE -> PUISSANCE,MARQUE,COULEUR\n",
736 "\tMARQUE,N VEH -> PUISSANCE,COULEUR,TYPE\n",
737 "\tCOULEUR,TYPE -> PUISSANCE,MARQUE\n",
738 "\tPUISSANCE,N VEH -> MARQUE,COULEUR,TYPE\n",
739 "\tCOULEUR,N VEH -> PUISSANCE,MARQUE,TYPE\n",
740 "\tPUISSANCE,N VEH,TYPE -> MARQUE,COULEUR\n",
741 "\tMARQUE,N VEH,TYPE -> PUISSANCE,COULEUR\n",
742 "\tCOULEUR,MARQUE,TYPE -> PUISSANCE\n",
743 "\tPUISSANCE,MARQUE,N VEH -> COULEUR,TYPE\n",
744 "\tCOULEUR,PUISSANCE,N VEH -> MARQUE,TYPE\n",
745 "\tCOULEUR,N VEH,TYPE -> PUISSANCE,MARQUE\n",
746 "\tCOULEUR,MARQUE,N VEH -> PUISSANCE,TYPE\n",
747 "\tCOULEUR,PUISSANCE,TYPE -> MARQUE\n",
748 "\tCOULEUR,MARQUE,N VEH,TYPE -> PUISSANCE\n",
749 "\tPUISSANCE,MARQUE,N VEH,TYPE -> COULEUR\n",
750 "\tCOULEUR,MARQUE,N VEH,PUISSANCE -> TYPE\n",
751 "\tCOULEUR,PUISSANCE,N VEH,TYPE -> MARQUE\n"
752 ]
753 }
754 ],
755 "source": [
756 "attributes3 = set( ['N VEH', 'TYPE', 'COULEUR', 'MARQUE', 'PUISSANCE'])\n",
757 "fds3 = [(set(['N VEH']), 'TYPE'), \n",
758 " (set(['N VEH']), 'COULEUR'),\n",
759 " (set(['TYPE']), 'MARQUE'),\n",
760 " (set(['TYPE']), 'PUISSANCE')]\n",
761 "print_fds(closure(attributes3,fds3))"
762 ]
763 },
764 {
765 "cell_type": "markdown",
766 "metadata": {},
767 "source": [
768 "Now, let's write a method to find superkeys of the relations:\n"
769 ]
770 },
771 {
772 "cell_type": "code",
773 "execution_count": 24,
774 "metadata": {
775 "collapsed": true
776 },
777 "outputs": [],
778 "source": [
779 "def superkeys(X, fds, verbose=False):\n",
780 " c = []\n",
781 " for size in range(1, len(X)):\n",
782 " subsets = findsubsets(X, size)\n",
783 " for SA in subsets:\n",
784 " cl = compute_closure(set(SA), fds, verbose)\n",
785 " if cl == X and len(cl.difference(SA)) > 0: ## cl = X\n",
786 " c.extend([SA])\n",
787 " return c"
788 ]
789 },
790 {
791 "cell_type": "code",
792 "execution_count": 25,
793 "metadata": {
794 "collapsed": false
795 },
796 "outputs": [
797 {
798 "data": {
799 "text/plain": [
800 "[('A', 'D'), ('A', 'B'), ('A', 'C', 'B'), ('A', 'B', 'D'), ('A', 'C', 'D')]"
801 ]
802 },
803 "execution_count": 25,
804 "metadata": {},
805 "output_type": "execute_result"
806 }
807 ],
808 "source": [
809 "superkeys(attributes1, fds1)\n"
810 ]
811 },
812 {
813 "cell_type": "markdown",
814 "metadata": {},
815 "source": [
816 "Let's see some examples:"
817 ]
818 },
819 {
820 "cell_type": "code",
821 "execution_count": 26,
822 "metadata": {
823 "collapsed": false
824 },
825 "outputs": [
826 {
827 "data": {
828 "text/plain": [
829 "[('CLIENT', 'CRU'), ('REMISE', 'CLIENT', 'CRU'), ('CLIENT', 'TYPE', 'CRU')]"
830 ]
831 },
832 "execution_count": 26,
833 "metadata": {},
834 "output_type": "execute_result"
835 }
836 ],
837 "source": [
838 "superkeys(attributes2, fds2)\n"
839 ]
840 },
841 {
842 "cell_type": "code",
843 "execution_count": 27,
844 "metadata": {
845 "collapsed": false
846 },
847 "outputs": [
848 {
849 "data": {
850 "text/plain": [
851 "[('N VEH',),\n",
852 " ('N VEH', 'TYPE'),\n",
853 " ('MARQUE', 'N VEH'),\n",
854 " ('N VEH', 'PUISSANCE'),\n",
855 " ('COULEUR', 'N VEH'),\n",
856 " ('N VEH', 'TYPE', 'PUISSANCE'),\n",
857 " ('MARQUE', 'N VEH', 'TYPE'),\n",
858 " ('MARQUE', 'N VEH', 'PUISSANCE'),\n",
859 " ('COULEUR', 'N VEH', 'PUISSANCE'),\n",
860 " ('COULEUR', 'N VEH', 'TYPE'),\n",
861 " ('COULEUR', 'MARQUE', 'N VEH'),\n",
862 " ('COULEUR', 'MARQUE', 'N VEH', 'TYPE'),\n",
863 " ('MARQUE', 'N VEH', 'TYPE', 'PUISSANCE'),\n",
864 " ('COULEUR', 'MARQUE', 'N VEH', 'PUISSANCE'),\n",
865 " ('COULEUR', 'N VEH', 'TYPE', 'PUISSANCE')]"
866 ]
867 },
868 "execution_count": 27,
869 "metadata": {},
870 "output_type": "execute_result"
871 }
872 ],
873 "source": [
874 "superkeys(attributes3, fds3)\n"
875 ]
876 },
877 {
878 "cell_type": "markdown",
879 "metadata": {},
880 "source": [
881 "#### Exercise 5\n",
882 "\n",
883 "Implement a `keys` method to find keys of a relation.\n",
884 "\n",
885 "**Note**: If there exist multiple keys of a relation, the `keys` method should return at least one of them."
886 ]
887 },
888 {
889 "cell_type": "code",
890 "execution_count": 42,
891 "metadata": {
892 "collapsed": false
893 },
894 "outputs": [],
895 "source": [
896 "def keys(attributes, fds):\n",
897 " l=superkeys(attributes, fds)\n",
898 " size=len(l[0])\n",
899 " result = l[0]\n",
900 " for superkey in l:\n",
901 " if len(superkey)<size:\n",
902 " result= superkey\n",
903 " size=len(superkey)\n",
904 " return result\n",
905 " \n"
906 ]
907 },
908 {
909 "cell_type": "markdown",
910 "metadata": {},
911 "source": [
912 "Test it "
913 ]
914 },
915 {
916 "cell_type": "code",
917 "execution_count": 43,
918 "metadata": {
919 "collapsed": false
920 },
921 "outputs": [
922 {
923 "data": {
924 "text/plain": [
925 "('A', 'D')"
926 ]
927 },
928 "execution_count": 43,
929 "metadata": {},
930 "output_type": "execute_result"
931 }
932 ],
933 "source": [
934 "keys(attributes1, fds1)"
935 ]
936 },
937 {
938 "cell_type": "code",
939 "execution_count": 44,
940 "metadata": {
941 "collapsed": false
942 },
943 "outputs": [
944 {
945 "data": {
946 "text/plain": [
947 "('CLIENT', 'CRU')"
948 ]
949 },
950 "execution_count": 44,
951 "metadata": {},
952 "output_type": "execute_result"
953 }
954 ],
955 "source": [
956 "keys(attributes2, fds2)"
957 ]
958 },
959 {
960 "cell_type": "code",
961 "execution_count": 45,
962 "metadata": {
963 "collapsed": false
964 },
965 "outputs": [
966 {
967 "data": {
968 "text/plain": [
969 "('N VEH',)"
970 ]
971 },
972 "execution_count": 45,
973 "metadata": {},
974 "output_type": "execute_result"
975 }
976 ],
977 "source": [
978 "keys(attributes3, fds3)"
979 ]
980 },
981 {
982 "cell_type": "code",
983 "execution_count": null,
984 "metadata": {
985 "collapsed": true
986 },
987 "outputs": [],
988 "source": []
989 }
990 ],
991 "metadata": {
992 "anaconda-cloud": {},
993 "kernelspec": {
994 "display_name": "Python 2",
995 "language": "python",
996 "name": "python2"
997 },
998 "language_info": {
999 "codemirror_mode": {
1000 "name": "ipython",
1001 "version": 2
1002 },
1003 "file_extension": ".py",
1004 "mimetype": "text/x-python",
1005 "name": "python",
1006 "nbconvert_exporter": "python",
1007 "pygments_lexer": "ipython2",
1008 "version": "2.7.13"
1009 }
1010 },
1011 "nbformat": 4,
1012 "nbformat_minor": 2
1013}