{
 "cells": [
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "활동 3NF\n",
    "------------\n",
    "\n",
    "이 번 활동에, 지난 시간까지 사용한 Python 도구를 사용하자:"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 2,
   "metadata": {
    "collapsed": true
   },
   "outputs": [],
   "source": [
    "def to_set(x):\n",
    "    if type(x) == set:\n",
    "        return x\n",
    "    elif type(x) in [list, set]:\n",
    "        return set(x)\n",
    "    elif type(x) in [str, int]:\n",
    "        return set([x])\n",
    "    else:\n",
    "        raise Exception(\"Unrecognized type.\")\n",
    "def fd_to_str(lhs,rhs): return \",\".join(to_set(lhs)) + \" -> \" + \",\".join(to_set(rhs))\n",
    "def fds_to_str(fds): return \"\\n\\t\".join(map(fd_to_str, fds))\n",
    "def set_to_str(x): return \"{\" + \",\".join(x) + \"}\"\n",
    "def fd_applies_to(fd, x): \n",
    "    lhs, rhs = map(to_set, fd)\n",
    "    return lhs.issubset(x)\n",
    "def compute_closure(x, fds, verbose=False):\n",
    "    bChanged = True        # We will repeat until there are no changes.\n",
    "    x_ret    = to_set(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\n",
    "def is_superkey_for(A, X, fds, verbose=False): \n",
    "    return X.issubset(compute_closure(A, fds, verbose=verbose))\n",
    "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) and \\\n",
    "        all([not is_superkey_for(set(SA), X, fds) for SA in subsets])"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "문제 1\n",
    "----------\n",
    "\n",
    "아래와 같이 속성이 주어졌다고 가정하고 위에서 제공한 도구를 사용하여 작성한 결과를 검사하고 검증해보자. 단, 아래 제시된 $A$의 속성을 활용하여 _BCNF가 아닌 3NF가 되도록_ 만드는 최소한의 FD를 찾아보자:"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 4,
   "metadata": {
    "collapsed": true
   },
   "outputs": [],
   "source": [
    "A = set(['A','B','C'])"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 5,
   "metadata": {
    "collapsed": true
   },
   "outputs": [],
   "source": [
    "F = [(set(['B']), 'C'), (set(['A','C']), 'B')]"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "문제 2\n",
    "----------\n",
    "\n",
    "릴레이션 $R$의 속성을 $A$의 속성들과 FD $F$들로 분해 할 수 있을지 위의 도구를 사용하여 실험해보고 검증해보자:"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {
    "collapsed": true
   },
   "outputs": [],
   "source": [
    "A = set(['A','B','C','D','E'])\n",
    "F = [(set(['B','C']), 'D'),\n",
    "     (set(['D']), 'E'),\n",
    "     (set(['E']), 'C'),\n",
    "     (set(['E']), 'A')]"
   ]
  }
 ],
 "metadata": {
  "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.6.5"
  }
 },
 "nbformat": 4,
 "nbformat_minor": 2
}