{
 "cells": [
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "활동 5a\n",
    "------------\n",
    "\n",
    "## Section 2: FDs & Closures\n",
    "\n",
    "속성 $\\{A_1, \\dots, A_n\\}$과 FD의 집합 $\\Gamma$가 있다고 하자.\n",
    "\n",
    "폐포(closure)는 $\\{A_1, \\dots, A_n\\}^+$라고 쓰고 $$A_1,\\dots,A_n \\rightarrow B \\text{ using } \\Gamma$$ 를 만족하는 가장 큰 속성 $B$의 집합이라고 정의 된다.\n",
    "\n",
    "스탠포드 CS145 데이터베이스 수업에서 사용되는 closure.py 파일을 python3에 맞게 포팅한 closure_v3.py를 활용하여, 속성 집합에서 closure를 계산해보자 (코드를 읽어보고자 한다면, 현재 디렉터리에 있는 closure_v3.py파일을 읽으면 된다):"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 1,
   "metadata": {
    "collapsed": true
   },
   "outputs": [],
   "source": [
    "#from closure_v2 import compute_closure # python2 인 경우\n",
    "from closure_v3 import compute_closure # python3 인 경우"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "### 문제 1\n",
    "\n",
    "어떤 스키마에 속성이 다음과 같다고 하자: $X=\\{A,B,C,D,E,F,G,H\\}$.\n",
    "\n",
    "이 문제를 위해 속성 집합 $A\\subset X$ 과 FD의 집합 $F$가 주어졌다고 하자. 클로져 $A^+=X$ 를 만족하는 **하나의 FD**를 $F$에 추가해보자.\n",
    "\n",
    "**Note: 다음의 셀에 있는 $F$에 `F.append((set([...]), set([...])))` 같은 방식을 써서 FD를 추가할 수 있다. 그리고, `compute_closure` 를 실행하여 결과를 확인해보자.**\n",
    "\n",
    "(이 활동이 끝나면 알게 되겠지만, 이 질문은 _$A$가 $X$의 수퍼키가 되는 FD 하나를 추가하여라_ 와 같은 질문이다.)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 32,
   "metadata": {
    "collapsed": true
   },
   "outputs": [],
   "source": [
    "A = set(['A', 'B','F'])\n",
    "F = [(set(['A', 'C']), 'D'),\n",
    "     (set(['D', 'H', 'G']), 'E'),\n",
    "     (set(['A', 'B']), 'G'),\n",
    "     (set(['F', 'B', 'G']), 'C')]"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 37,
   "metadata": {},
   "outputs": [
    {
     "data": {
      "text/plain": [
       "{'A', 'B', 'C', 'D', 'F', 'G'}"
      ]
     },
     "execution_count": 37,
     "metadata": {},
     "output_type": "execute_result"
    }
   ],
   "source": [
    "compute_closure(A,F)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {
    "collapsed": true
   },
   "outputs": [],
   "source": []
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "## Section 3: Superkeys & Keys\n",
    "\n",
    "다음으로 우리가 알아볼 것은 수퍼키와 키에 대한 내용이다. 수퍼키와 키를 위한 새로운 함수를 추가할 것이다. 수퍼키와 키의 정의를 다시 확인해보자:\n",
    "* 릴레이션 $R(B_1,\\dots,B_m)$의 _superkey_ 는 $$ \\{A_1,\\dots,A_n\\} \\rightarrow B_{j} \\text{,   }\\forall j=1,\\dots m$$를 만족하는 속성 집합  $\\{A_1,\\dots,A_n\\}$ 이다.\n",
    "\n",
    "*  _key_ 는 (집합적으로) 최소한의 수준의 _superkey_\n",
    "\n",
    "속성 집합 $A$가 $X$의 수퍼키인지 여부를 판단하는 알고리즘은 매우간단하다. $A^+=X$인지 판단해보면 된다:"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 7,
   "metadata": {
    "collapsed": true
   },
   "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": [
    "그리고, $A$가 $X$의 키인지 확인하기 위해서는 다음의 검사하면 된다:\n",
    "* (a) 수퍼키이다. \n",
    "* (b) 더 작은 수퍼키가 없다 (_모든 경우를 따질 필요 없이, 현재 수퍼키보다 하나 작은 것만 찾아보면 된다. 왜 그런지 생각해보자!_)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 6,
   "metadata": {
    "collapsed": true
   },
   "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) and \\\n",
    "        all([not is_superkey_for(set(SA), X, fds) for SA in subsets])"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "### 문제 1\n",
    "\n",
    "스키가가 $R=\\{A,B,C\\}$라고 주어졌다고 가정하자. 이 때, _오직 두 개의 키_ 만 존재하도록 FD 집합을 만들어 보자. 위에 정의한 함수들을 호출하여 검사해보자!"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {
    "collapsed": true
   },
   "outputs": [],
   "source": [
    "R = set(['A','B','C'])"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {
    "collapsed": true
   },
   "outputs": [],
   "source": [
    "F = [\"\"\"your FD definition\"\"\"]\n",
    "\n",
    "# test for key\n",
    "print(is_key_for(\"\"\"your FD\"\"\", R, F))\n",
    "# and more ..."
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "### 문제 2\n",
    "\n",
    "이번에는 아래의 셀에 나온 것처럼 릴레이션이 주어졌다고 가정하자. 위에 정의한 함수들을 활용하여 가능한 많은 속성이 키가 되도록 FD를 정의해보자. 몇 개의 키를 만들 수 있었는가? 가능한 많은 속성들을 키에 포함시켜보자. \n",
    "\n",
    "_Bonus question: 키의 갯수가 최대가 되려면 최소 몇 개의 다른 FD가 필요한가?_"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 3,
   "metadata": {
    "collapsed": true
   },
   "outputs": [],
   "source": [
    "R = set(['A','B','C','D','E'])"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {
    "collapsed": true
   },
   "outputs": [],
   "source": [
    "F = [\"\"\"your FD definition\"\"\"]\n",
    "\n",
    "# test for key\n",
    "print(is_key_for(\"\"\"your FD\"\"\", R, F))\n",
    "# and more ..."
   ]
  }
 ],
 "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
}