DB-TP1.ipynb

{
 "cells": [
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "# TP1 - Finding Keys using Functional Dependencies \n",
    "--------------------------\n",
    "\n",
    "In this lab, we are going to learn \n",
    "\n",
    "- how to use Jupyter\n",
    "- how to use SQLite\n",
    "- how to discover keys in relations\n",
    "\n",
    "## How to use Jupyter\n",
    "\n",
    "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",
    "\n",
    "To edit a cell, click on it. If the cell uses markdown code, then use ENTER to edit it.\n",
    "\n",
    "See the Help menu for other useful keyboard commands. You can always use the menu bar instead as well.\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 53,
   "metadata": {},
   "outputs": [
    {
     "name": "stdout",
     "output_type": "stream",
     "text": [
      "Hello world!\n"
     ]
    }
   ],
   "source": [
    "print(\"Hello world!\")"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Another example:"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 54,
   "metadata": {},
   "outputs": [
    {
     "name": "stdout",
     "output_type": "stream",
     "text": [
      "1\n",
      "2\n",
      "3\n",
      "4\n",
      "5\n",
      "6\n",
      "7\n",
      "8\n",
      "9\n"
     ]
    }
   ],
   "source": [
    "for i in range(1,10):\n",
    "    print(i)"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "#### Exercise 1\n",
    "\n",
    "Print numbers 1 to 9 in reverse order"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 55,
   "metadata": {},
   "outputs": [
    {
     "name": "stdout",
     "output_type": "stream",
     "text": [
      "9\n",
      "8\n",
      "7\n",
      "6\n",
      "5\n",
      "4\n",
      "3\n",
      "2\n",
      "1\n"
     ]
    }
   ],
   "source": [
    "for i in range(1,10):\n",
    "    print(10-i)"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "## How to use SQLite\n",
    "\n",
    "To work with SQL easily in a notebook, we'll load the ipython-sql extension as follows:"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 56,
   "metadata": {},
   "outputs": [
    {
     "name": "stdout",
     "output_type": "stream",
     "text": [
      "The sql extension is already loaded. To reload it, use:\n",
      "  %reload_ext sql\n"
     ]
    },
    {
     "data": {
      "text/plain": [
       "'Connected: @None'"
      ]
     },
     "execution_count": 56,
     "metadata": {},
     "output_type": "execute_result"
    }
   ],
   "source": [
    "%load_ext sql\n",
    "%sql sqlite://"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "We are going to create a table:"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 57,
   "metadata": {},
   "outputs": [
    {
     "name": "stdout",
     "output_type": "stream",
     "text": [
      " * sqlite://\n",
      "Done.\n",
      "Done.\n",
      "1 rows affected.\n",
      "1 rows affected.\n",
      "1 rows affected.\n"
     ]
    },
    {
     "data": {
      "text/plain": [
       "[]"
      ]
     },
     "execution_count": 57,
     "metadata": {},
     "output_type": "execute_result"
    }
   ],
   "source": [
    "%%sql DROP TABLE IF EXISTS T;\n",
    "CREATE TABLE T(course VARCHAR, classroom INT, time INT);\n",
    "INSERT INTO T VALUES ('CS 364', 132, 900);\n",
    "INSERT INTO T VALUES ('CS 245', 140, 1000);\n",
    "INSERT INTO T VALUES ('EE 101', 210, 900);"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Let's run our first SQL query:"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 58,
   "metadata": {},
   "outputs": [
    {
     "name": "stdout",
     "output_type": "stream",
     "text": [
      " * sqlite://\n",
      "Done.\n"
     ]
    },
    {
     "data": {
      "text/html": [
       "<table>\n",
       "    <tr>\n",
       "        <th>course</th>\n",
       "        <th>classroom</th>\n",
       "        <th>time</th>\n",
       "    </tr>\n",
       "    <tr>\n",
       "        <td>CS 364</td>\n",
       "        <td>132</td>\n",
       "        <td>900</td>\n",
       "    </tr>\n",
       "    <tr>\n",
       "        <td>CS 245</td>\n",
       "        <td>140</td>\n",
       "        <td>1000</td>\n",
       "    </tr>\n",
       "    <tr>\n",
       "        <td>EE 101</td>\n",
       "        <td>210</td>\n",
       "        <td>900</td>\n",
       "    </tr>\n",
       "</table>"
      ],
      "text/plain": [
       "[('CS 364', 132, 900), ('CS 245', 140, 1000), ('EE 101', 210, 900)]"
      ]
     },
     "execution_count": 58,
     "metadata": {},
     "output_type": "execute_result"
    }
   ],
   "source": [
    "%sql SELECT * FROM T;"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "#### Exercise 2\n",
    "\n",
    "List the name of the courses with time less than 950"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 59,
   "metadata": {},
   "outputs": [
    {
     "name": "stdout",
     "output_type": "stream",
     "text": [
      " * sqlite://\n",
      "Done.\n"
     ]
    },
    {
     "data": {
      "text/html": [
       "<table>\n",
       "    <tr>\n",
       "        <th>course</th>\n",
       "    </tr>\n",
       "    <tr>\n",
       "        <td>CS 364</td>\n",
       "    </tr>\n",
       "    <tr>\n",
       "        <td>EE 101</td>\n",
       "    </tr>\n",
       "</table>"
      ],
      "text/plain": [
       "[('CS 364',), ('EE 101',)]"
      ]
     },
     "execution_count": 59,
     "metadata": {},
     "output_type": "execute_result"
    }
   ],
   "source": [
    "%sql SELECT course FROM T WHERE(time<950)"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "## How to discover keys in relations\n",
    "\n",
    "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",
    "\n",
    "### Functional Dependencies\n",
    "\n",
    "Recall that given a set of attributes  $\\{A_1, \\dots, A_n\\}$ and a set of FDs $\\Gamma$\n",
    "\n",
    "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",
    "\n",
    "We're going to use some functions to compute the closure of a set of attributes and other such operations (_from CS145 Stanford_)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 60,
   "metadata": {},
   "outputs": [],
   "source": [
    "# Source code\n",
    "\n",
    "def to_set(x):\n",
    "  \"\"\"Convert input int, string, list, tuple, set -> set\"\"\"\n",
    "  if type(x) == set:\n",
    "    return x\n",
    "  elif type(x) in [list, tuple]:\n",
    "    return set(x)\n",
    "  elif type(x) in [str, int]:\n",
    "    return set([x])\n",
    "  else:\n",
    "    raise Exception(\"Unrecognized type.\")\n",
    "\n",
    "def fd_to_str(lr_tuple):\n",
    "    lhs = lr_tuple[0]\n",
    "    rhs = lr_tuple[1]\n",
    "    return \",\".join(to_set(lhs)) + \" -> \" + \",\".join(to_set(rhs))\n",
    "\n",
    "def fds_to_str(fds): return \"\\n\\t\".join(map(fd_to_str, fds))\n",
    "\n",
    "def set_to_str(x): return \"{\" + \",\".join(x) + \"}\"\n",
    "\n",
    "def fd_applies_to(fd, x): \n",
    "  lhs, rhs = map(to_set, fd)\n",
    "  return lhs.issubset(x)\n",
    "\n",
    "def print_setup(A, fds):\n",
    "  print(\"Attributes = \" + set_to_str(A))\n",
    "  print(\"FDs = \\t\" + fds_to_str(fds))\n",
    "\n",
    "def print_fds(fds):\n",
    "  print(\"FDs = \\t\" + fds_to_str(fds))    \n"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Now, let's look at a concrete example. For example, the code for\n",
    "\n",
    "attributes = { name, category, color, department, price}\n",
    "\n",
    "and functional dependencies:\n",
    "\n",
    "name $\\rightarrow$ color\n",
    "\n",
    "category $\\rightarrow$ department\n",
    "\n",
    "color, category $\\rightarrow$ price\n",
    "\n",
    "is the following:"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 61,
   "metadata": {},
   "outputs": [
    {
     "name": "stdout",
     "output_type": "stream",
     "text": [
      "Attributes = {color,price,name,department,category}\n",
      "FDs = \tname -> color\n",
      "\tcategory -> department\n",
      "\tcolor,category -> price\n"
     ]
    }
   ],
   "source": [
    "attributes  = set([\"name\", \"category\", \"color\", \"department\", \"price\"]) # These are the attribute set.\n",
    "fds = [(set([\"name\"]),\"color\"),\n",
    "         (set([\"category\"]), \"department\"),\n",
    "         (set([\"color\", \"category\"]), \"price\")]\n",
    "\n",
    "print_setup(attributes, fds)"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "### Closure of a set of Attributes\n",
    "\n",
    "Let's implement the algorithm for obtaining the closure of a set of attributes:"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 62,
   "metadata": {},
   "outputs": [],
   "source": [
    "def compute_closure(x, fds, verbose=False):\n",
    "    bChanged = True        # We will repeat until there are no changes.\n",
    "    x_ret    = x.copy()    # Make a copy of the input to hold x^{+}\n",
    "    while bChanged:\n",
    "        bChanged = False   # Must change on each iteration\n",
    "        for fd in fds:     # loop through all the FDs.\n",
    "            (lhs, rhs) = map(to_set, fd) # recall: lhs -> rhs\n",
    "            if fd_applies_to(fd, x_ret) and not rhs.issubset(x_ret):\n",
    "                x_ret = x_ret.union(rhs)\n",
    "                if verbose:\n",
    "                    print(\"Using FD \" + fd_to_str(fd))\n",
    "                    print(\"\\t Updated x to \" + set_to_str(x_ret))\n",
    "                bChanged = True\n",
    "    return x_ret"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "As an example, let's compute the closure for the attribute \"name\":"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 63,
   "metadata": {},
   "outputs": [
    {
     "name": "stdout",
     "output_type": "stream",
     "text": [
      "Using FD name -> color\n",
      "\t Updated x to {name,color}\n"
     ]
    },
    {
     "data": {
      "text/plain": [
       "{'color', 'name'}"
      ]
     },
     "execution_count": 63,
     "metadata": {},
     "output_type": "execute_result"
    }
   ],
   "source": [
    "A = set([\"name\"])\n",
    "compute_closure(A,fds, True)"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "#### Exercise 3\n",
    "\n",
    "Is the attribute \"name\" a superkey for this relation? Why?"
   ]
  },
  {
   "cell_type": "raw",
   "metadata": {},
   "source": [
    "No, name is not a super key because if it were, it's closure would be the whole attributes and here there is only name and color ==>{'color', name'}"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "### Keys and Superkeys\n",
    "\n",
    "Next, we'll add some new functions now for finding superkeys and keys.  Recall:\n",
    "* A _superkey_ for a relation $R(B_1,\\dots,B_m)$ is a set of attributes $\\{A_1,\\dots,A_n\\}$ s.t.\n",
    "$$ \\{A_1,\\dots,A_n\\} \\rightarrow B_{j} \\text{ for all } j=1,\\dots m$$\n",
    "* A _key_ is a minimal (setwise) _superkey_\n",
    "\n",
    "The algorithm to determine if a set of attributes $A$ is a superkey for $X$ is actually very simple (check if $A^+=X$):"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 64,
   "metadata": {},
   "outputs": [],
   "source": [
    "def is_superkey_for(A, X, fds, verbose=False): \n",
    "    return X.issubset(compute_closure(A, fds, verbose=verbose))"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Is \"name\" a superkey of the relation?"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 65,
   "metadata": {},
   "outputs": [
    {
     "data": {
      "text/plain": [
       "False"
      ]
     },
     "execution_count": 65,
     "metadata": {},
     "output_type": "execute_result"
    }
   ],
   "source": [
    "is_superkey_for(A, attributes, fds)"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Then, to check if $A$ is a key for $X$, we just confirm that:\n",
    "* (a) it is a superkey\n",
    "* (b) there are no smaller superkeys (_Note that we only need to check for superkeys of one size smaller_)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 66,
   "metadata": {},
   "outputs": [],
   "source": [
    "import itertools\n",
    "def is_key_for(A, X, fds, verbose=False):\n",
    "    subsets = set(itertools.combinations(A, len(A)-1))\n",
    "    return is_superkey_for(A, X, fds, verbose=verbose) and \\\n",
    "        all([not is_superkey_for(set(SA), X, fds) for SA in subsets])"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Now, let's look at another example:\n",
    "\n",
    "attributes = { cru, type, client, remise}\n",
    "\n",
    "and functional dependencies:\n",
    "\n",
    "cru $\\rightarrow$ type\n",
    "\n",
    "type, client $\\rightarrow$ remise\n",
    "\n",
    "#### Exercise 4\n",
    "\n",
    "Is \"cru\" and \"client\" a key of the relation? Why?"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 67,
   "metadata": {},
   "outputs": [
    {
     "name": "stdout",
     "output_type": "stream",
     "text": [
      "Using FD cru -> type\n",
      "\t Updated x to {cru,client,type}\n",
      "Using FD client,type -> remise\n",
      "\t Updated x to {cru,client,type,remise}\n"
     ]
    },
    {
     "data": {
      "text/plain": [
       "True"
      ]
     },
     "execution_count": 67,
     "metadata": {},
     "output_type": "execute_result"
    }
   ],
   "source": [
    "attributes  = set([\"cru\", \"type\", \"client\", \"remise\"]) # These are the attribute set.\n",
    "fds = [(set([\"cru\"]),\"type\"),\n",
    "         (set([\"type\", \"client\"]), \"remise\")]#These are the functional dependancies\n",
    "A=set([\"cru\", \"client\"])\n",
    "\n",
    "is_key_for(A, attributes, fds, verbose=True)"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Because it's a superkey and it is minimal. "
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "### Closure of a set of functional dependencies\n",
    "\n",
    "The algorithm to find the closure of a set of functional dependencies is the following:"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 68,
   "metadata": {},
   "outputs": [],
   "source": [
    "import itertools\n",
    "def findsubsets(S,m):\n",
    "    return set(itertools.combinations(S, m))\n",
    "def closure(X, fds, verbose=False):\n",
    "    c = []\n",
    "    for size in range(1, len(X)):\n",
    "        subsets = findsubsets(X, size) \n",
    "        for SA in subsets:      # loop through all the subsets.\n",
    "            cl = compute_closure(set(SA), fds, verbose)\n",
    "            if len(cl.difference(SA)) > 0: \n",
    "                c.extend([(set(SA), cl.difference(SA))])\n",
    "    return c"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Let's see some examples of how to use it:"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 31,
   "metadata": {},
   "outputs": [
    {
     "name": "stdout",
     "output_type": "stream",
     "text": [
      "FDs = \tB -> D\n",
      "\tA,B -> C,D\n",
      "\tC,B -> D\n",
      "\tA,D -> B,C\n",
      "\tC,A,D -> B\n",
      "\tB,A,D -> C\n",
      "\tC,A,B -> D\n"
     ]
    }
   ],
   "source": [
    "attributes1 = set(['A', 'B', 'C', 'D'])\n",
    "fds1 = [(set(['A', 'B']), 'C'),\n",
    "     (set(['A', 'D']), 'B'),\n",
    "     (set(['B']), 'D')]\n",
    "print_fds(closure(attributes1, fds1))\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 30,
   "metadata": {},
   "outputs": [
    {
     "name": "stdout",
     "output_type": "stream",
     "text": [
      "FDs = \tCRU -> TYPE\n",
      "\tCRU,REMISE -> TYPE\n",
      "\tCRU,CLIENT -> REMISE,TYPE\n",
      "\tTYPE,CLIENT -> REMISE\n",
      "\tCRU,REMISE,CLIENT -> TYPE\n",
      "\tCRU,TYPE,CLIENT -> REMISE\n"
     ]
    }
   ],
   "source": [
    "attributes2 = set (['CRU', 'TYPE', 'CLIENT', 'REMISE'])\n",
    "fds2 = [(set(['CRU']), 'TYPE'),\n",
    "     (set(['TYPE', 'CLIENT']), 'REMISE')]\n",
    "print_fds(closure(attributes2, fds2))"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 32,
   "metadata": {},
   "outputs": [
    {
     "name": "stdout",
     "output_type": "stream",
     "text": [
      "FDs = \tN VEH -> PUISSANCE,COULEUR,TYPE,MARQUE\n",
      "\tTYPE -> PUISSANCE,MARQUE\n",
      "\tTYPE,MARQUE -> PUISSANCE\n",
      "\tCOULEUR,N VEH -> PUISSANCE,TYPE,MARQUE\n",
      "\tCOULEUR,TYPE -> PUISSANCE,MARQUE\n",
      "\tTYPE,N VEH -> PUISSANCE,COULEUR,MARQUE\n",
      "\tPUISSANCE,N VEH -> COULEUR,TYPE,MARQUE\n",
      "\tPUISSANCE,TYPE -> MARQUE\n",
      "\tMARQUE,N VEH -> PUISSANCE,COULEUR,TYPE\n",
      "\tPUISSANCE,MARQUE,N VEH -> COULEUR,TYPE\n",
      "\tCOULEUR,TYPE,N VEH -> PUISSANCE,MARQUE\n",
      "\tPUISSANCE,COULEUR,TYPE -> MARQUE\n",
      "\tCOULEUR,TYPE,MARQUE -> PUISSANCE\n",
      "\tCOULEUR,MARQUE,N VEH -> PUISSANCE,TYPE\n",
      "\tTYPE,MARQUE,N VEH -> PUISSANCE,COULEUR\n",
      "\tPUISSANCE,TYPE,N VEH -> COULEUR,MARQUE\n",
      "\tPUISSANCE,COULEUR,N VEH -> TYPE,MARQUE\n",
      "\tPUISSANCE,COULEUR,TYPE,N VEH -> MARQUE\n",
      "\tPUISSANCE,TYPE,MARQUE,N VEH -> COULEUR\n",
      "\tPUISSANCE,COULEUR,MARQUE,N VEH -> TYPE\n",
      "\tCOULEUR,TYPE,MARQUE,N VEH -> PUISSANCE\n"
     ]
    }
   ],
   "source": [
    "attributes3 = set( ['N VEH', 'TYPE', 'COULEUR', 'MARQUE', 'PUISSANCE'])\n",
    "fds3 = [(set(['N VEH']), 'TYPE'), \n",
    "      (set(['N VEH']), 'COULEUR'),\n",
    "      (set(['TYPE']), 'MARQUE'),\n",
    "      (set(['TYPE']), 'PUISSANCE')]\n",
    "print_fds(closure(attributes3,fds3))"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Now, let's write a method to find superkeys of the relations:\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 34,
   "metadata": {},
   "outputs": [],
   "source": [
    "def superkeys(X, fds, verbose=False):\n",
    "    c = []\n",
    "    for size in range(1, len(X)):\n",
    "        subsets = findsubsets(X, size)\n",
    "        for SA in subsets:\n",
    "            cl = compute_closure(set(SA), fds, verbose)\n",
    "            if cl == X and len(cl.difference(SA)) > 0: ## cl = X\n",
    "                c.extend([SA])\n",
    "    return c"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 35,
   "metadata": {},
   "outputs": [
    {
     "data": {
      "text/plain": [
       "[('A', 'B'), ('A', 'D'), ('C', 'A', 'D'), ('A', 'D', 'B'), ('C', 'A', 'B')]"
      ]
     },
     "execution_count": 35,
     "metadata": {},
     "output_type": "execute_result"
    }
   ],
   "source": [
    "superkeys(attributes1, fds1)\n"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Let's see some examples:"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 36,
   "metadata": {},
   "outputs": [
    {
     "data": {
      "text/plain": [
       "[('CRU', 'CLIENT'), ('CRU', 'REMISE', 'CLIENT'), ('CRU', 'TYPE', 'CLIENT')]"
      ]
     },
     "execution_count": 36,
     "metadata": {},
     "output_type": "execute_result"
    }
   ],
   "source": [
    "superkeys(attributes2, fds2)\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 37,
   "metadata": {},
   "outputs": [
    {
     "data": {
      "text/plain": [
       "[('N VEH',),\n",
       " ('COULEUR', 'N VEH'),\n",
       " ('TYPE', 'N VEH'),\n",
       " ('PUISSANCE', 'N VEH'),\n",
       " ('MARQUE', 'N VEH'),\n",
       " ('PUISSANCE', 'MARQUE', 'N VEH'),\n",
       " ('COULEUR', 'TYPE', 'N VEH'),\n",
       " ('COULEUR', 'MARQUE', 'N VEH'),\n",
       " ('TYPE', 'MARQUE', 'N VEH'),\n",
       " ('PUISSANCE', 'TYPE', 'N VEH'),\n",
       " ('PUISSANCE', 'COULEUR', 'N VEH'),\n",
       " ('PUISSANCE', 'COULEUR', 'TYPE', 'N VEH'),\n",
       " ('PUISSANCE', 'TYPE', 'MARQUE', 'N VEH'),\n",
       " ('PUISSANCE', 'COULEUR', 'MARQUE', 'N VEH'),\n",
       " ('COULEUR', 'TYPE', 'MARQUE', 'N VEH')]"
      ]
     },
     "execution_count": 37,
     "metadata": {},
     "output_type": "execute_result"
    }
   ],
   "source": [
    "superkeys(attributes3, fds3)"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "#### Exercise 5\n",
    "\n",
    "Implement a `keys` method to find keys of a relation.\n",
    "\n",
    "**Note**: If there exist multiple keys of a relation, the `keys` method should return at least one of them."
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 46,
   "metadata": {},
   "outputs": [],
   "source": [
    "def min(L)\n",
    "    x=L[0]\n",
    "    for i in range (len(L)-1):       ##these function helps me to find the minimumof the \n",
    "        if (len(L[i+1])<len(L[i])):\n",
    "            x=L[i+1]\n",
    "    return x\n",
    "def keys (attributes, fds):\n",
    "    L=superkeys(attributes, fds)\n",
    "    if (len(L)==0):\n",
    "        return (\"il n'y a pas de superkey si ce n'est la table entière\")\n",
    "    else:\n",
    "        return min(L)\n",
    "        \n",
    "    "
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Test it "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 52,
   "metadata": {},
   "outputs": [
    {
     "data": {
      "text/plain": [
       "('A', 'B')"
      ]
     },
     "execution_count": 52,
     "metadata": {},
     "output_type": "execute_result"
    }
   ],
   "source": [
    "keys(attributes1, fds1)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 51,
   "metadata": {},
   "outputs": [
    {
     "data": {
      "text/plain": [
       "('CRU', 'CLIENT')"
      ]
     },
     "execution_count": 51,
     "metadata": {},
     "output_type": "execute_result"
    }
   ],
   "source": [
    "keys(attributes2, fds2)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 50,
   "metadata": {},
   "outputs": [
    {
     "data": {
      "text/plain": [
       "('N VEH',)"
      ]
     },
     "execution_count": 50,
     "metadata": {},
     "output_type": "execute_result"
    }
   ],
   "source": [
    "keys(attributes3, fds3)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": []
  }
 ],
 "metadata": {
  "anaconda-cloud": {},
  "kernelspec": {
   "display_name": "Python 3",
   "language": "python",
   "name": "python3"
  },
  "language_info": {
   "codemirror_mode": {
    "name": "ipython",
    "version": 3
   },
   "file_extension": ".py",
   "mimetype": "text/x-python",
   "name": "python",
   "nbconvert_exporter": "python",
   "pygments_lexer": "ipython3",
   "version": "3.5.3"
  }
 },
 "nbformat": 4,
 "nbformat_minor": 2
}