{ "cells": [ { "cell_type": "code", "execution_count": 3, "metadata": { "collapsed": false, "scrolled": true }, "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": 3, "metadata": {}, "output_type": "execute_result" } ], "source": [ "%load_ext sql\n", "%sql sqlite://" ] }, { "cell_type": "code", "execution_count": 4, "metadata": { "collapsed": true }, "outputs": [], "source": [ "# 활용할 함수들...\n", "from IPython.core.display import display_html, HTML\n", "def to_html_table(res, style=None):\n", " html = ''\n", " html += ''.join(res.keys) + ''\n", " html += ''.join([''.join([str(cell) for cell in row]) for row in list(res)])\n", " return html + ''\n", "def display_side_by_side(l, r):\n", " s = \"display: inline-block;\"\n", " html = to_html_table(l, style=s) + ' ' + to_html_table(r, style=s)\n", " display_html(HTML(data=html))" ] }, { "cell_type": "markdown", "metadata": {}, "source": [ "MVDs (MultiValued Dependency)\n", "=============================\n", "\n", "MVDs (다치 종속). 최근 많은 사람들이 관심 같는 부분이다. \n", "\n", "이 노트북에서 MVD에 대해 알아보자. " ] }, { "cell_type": "markdown", "metadata": {}, "source": [ "## 형식적 정의\n", "\n", "속성 집합 $A$를 갖는 릴레이션 $R$이 있다고 가정하자. 이 때, 두 개의 속성 집합이 $X,Y\\subseteq A$을 만족한다. $t_1[X] = t_2[X]$인 터플이 $t_1,t_2\\in R$이라면 **_다치 종속 multi-value dependency (MVD)_** 인 $X\\twoheadrightarrow Y$가 $R$에서 유지가 되며, 다음을 만족하는 $t_3\\in R$도 존재한다. \n", "\n", "* $t_3[X] = t_1[X] = t_2[X]$\n", "* $t_3[Y] = t_1[Y]$\n", "* $t_3[A\\setminus Y] = t_2[A\\setminus Y]$\n", "\n", "이 때, $A\\setminus B$ = $B$에 없는 모든 $A$의 요소들이다.\n", "\n", "이해를 위해 간단한 예제를 먼저 살펴보고 넘어가자:" ] }, { "cell_type": "code", "execution_count": 5, "metadata": { "collapsed": false }, "outputs": [ { "name": "stdout", "output_type": "stream", "text": [ " * sqlite://\n", "Done.\n", "Done.\n", "1 rows affected.\n", "1 rows affected.\n", "Done.\n" ] }, { "data": { "text/html": [ "\n", " \n", " \n", " \n", " \n", " \n", " \n", " \n", " \n", " \n", " \n", " \n", " \n", " \n", " \n", " \n", "
ABC
110
101
" ], "text/plain": [ "[(1, 1, 0), (1, 0, 1)]" ] }, "execution_count": 5, "metadata": {}, "output_type": "execute_result" } ], "source": [ "%%sql\n", "DROP TABLE IF EXISTS R; CREATE TABLE R (A INT, B INT, C INT);\n", "INSERT INTO R VALUES (1, 1, 0);\n", "INSERT INTO R VALUES (1, 0, 1);\n", "SELECT * FROM R;" ] }, { "cell_type": "markdown", "metadata": {}, "source": [ "결과로 얻은 두 줄을 각각 $t_1$ 과 $t_2$라고 하자. 정의상 MVD $\\{A\\}\\twoheadrightarrow\\{B\\}$ 을 만족하는 $t_3$을 추가하려면, 어떤 값을 추가해야 하는가? 다음의 값을 추가해보자:" ] }, { "cell_type": "code", "execution_count": 6, "metadata": { "collapsed": false }, "outputs": [ { "name": "stdout", "output_type": "stream", "text": [ " * sqlite://\n", "1 rows affected.\n", "Done.\n" ] }, { "data": { "text/html": [ "\n", " \n", " \n", " \n", " \n", " \n", " \n", " \n", " \n", " \n", " \n", " \n", " \n", " \n", " \n", " \n", " \n", " \n", " \n", " \n", " \n", "
ABC
110
101
111
" ], "text/plain": [ "[(1, 1, 0), (1, 0, 1), (1, 1, 1)]" ] }, "execution_count": 6, "metadata": {}, "output_type": "execute_result" } ], "source": [ "%sql INSERT INTO R VALUES (1,1,1); SELECT * FROM R;" ] }, { "cell_type": "markdown", "metadata": {}, "source": [ "만약, 첫 두 줄의 결과가 $t_2$ 과 $t_1$라고 한다면 어떻겠는가? 정의상 어떤 값을 추가해야 하는가?" ] }, { "cell_type": "code", "execution_count": 4, "metadata": { "collapsed": false }, "outputs": [ { "name": "stdout", "output_type": "stream", "text": [ "1 rows affected.\n", "Done.\n" ] }, { "data": { "text/html": [ "\n", " \n", " \n", " \n", " \n", " \n", " \n", " \n", " \n", " \n", " \n", " \n", " \n", " \n", " \n", " \n", " \n", " \n", " \n", " \n", " \n", " \n", " \n", " \n", " \n", " \n", "
ABC
110
101
111
100
" ], "text/plain": [ "[(1, 1, 0), (1, 0, 1), (1, 1, 1), (1, 0, 0)]" ] }, "execution_count": 4, "metadata": {}, "output_type": "execute_result" } ], "source": [ "%sql INSERT INTO R VALUES (1,0,0); SELECT * FROM R;" ] }, { "cell_type": "markdown", "metadata": {}, "source": [ "이제, 나머지 모든 쌍을 이런 식으로 비교를 다 해보면 끝이 나며, MVD $\\{A\\}\\twoheadrightarrow\\{B\\}$을 만족한다.\n", "\n", "## 두 번째 정의 \n", "\n", "또 다른 동치인 정의가 존재한다. 약간은 비형식적으로 정의 해보자:\n", "\n", "**MVD $\\{A\\}\\twoheadrightarrow\\{B\\}$를 만족하려면 어떤 속성 $A$의 터플 쌍에 대응하는 _\"swapped(교차된)\"_ 쌍을 찾아야 한다: $A$라는 값을 동일하게 갖는 터플 쌍이지만 $B$와 $(A\\cup B)^C$의 속성이 서로 뒤바뀐 경우이다.**\n", "\n", "(*이 때, $(A\\cup B)^C$는 $A$ 또는 $B$에 포함되지 않는 속성들을 말한다*)\n", "\n", "앞에서 다룬 예제를 통해 이 번 정의는 쉽게 이해가 될 것이다. 어째면 더 직관적이라고 생각될 수도 있다. " ] }, { "cell_type": "markdown", "metadata": {}, "source": [ "### 혼란스러울 수 있는 부분:\n", "\n", "**릴레이션**에 대해서 MVD 인 것을 기억해야 한다. 하나의 터플이나 한 쌍($t_1,t_2$, ...)의 터플이 MVD를 만족한다고 릴레이션이 MVD인 것은 아니다. 정의를 다시 보면, $t_1[A]=t_2[A]$을 만족하는 **가능한** $t_1,t_2$의 **조합이** $R$에 **존재**하는 경우에만 릴레이션 $R$에 대해 $\\{X\\}\\twoheadrightarrow\\{Y\\}$이 만족한다.\n", "\n", "### 용어에 대한 재확인:\n", "그러면 $R$의 _인스턴스_ 만 보고 어떻게 릴레이션 $R$이 MVD를 만족하는지 _검사_ 할 수 있을까? 누군가가 새로운 터플을 추가하여 MVD 성질을 깰 수 있지 않을까? 인스턴스만 검사하고 어떤 릴레이션의 _인스턴스_ 가 MVD를 '만족'한다고 하기에는 너무 성급한 것 아닐까?\n", "\n", "맞는 말이다. FDdㅔ서 비슷한 경험을 했었다. 예를 들어 함수 종속인 집합에 대한 _외부 정보_ 가 필요했던 것처럼 한 릴레이션이 전반적으로 MVD를 만족한다는 것을 확신하기 위해서는 _증거_ 가 필요하다. $R$의 인스턴스만 보고도 위배의 여부를 판단할 수 **있고** 일반적으로 MVD인지 판단할 수 **있다**. \n", "\n", "인스턴스만 확인하고도 MVD (또는 FD)가 어떤 인스턴스에 대해 _만족_ 한다면, 암묵적으로 성질을 만족한다고 한다. 그리고 우리가 지금 보는 인스턴스만으로 일반화도 _가능할 것_ 이라 말한다." ] }, { "cell_type": "markdown", "metadata": {}, "source": [ "### 세 번째 정의...\n", "\n", "이 시점에서 (생각하면서 읽었다면) 벡터곱과 join의 관계를 의심해볼 수 있을 것이다. **MVD를 만족시키기 위해 두 개의 줄을 추가하기 전 상태의 테이블**을 활용하여 다시 생각해보자. MVD를 만족하는 속성들로 테이블을 두 개로 분해해보자 ($\\{A\\}\\twoheadrightarrow\\{B\\}$):" ] }, { "cell_type": "code", "execution_count": 11, "metadata": { "collapsed": false }, "outputs": [ { "name": "stdout", "output_type": "stream", "text": [ "Done.\n", "Done.\n", "1 rows affected.\n", "1 rows affected.\n", "Done.\n" ] }, { "data": { "text/html": [ "\n", " \n", " \n", " \n", " \n", " \n", " \n", " \n", " \n", " \n", " \n", " \n", " \n", " \n", " \n", " \n", "
ABC
110
101
" ], "text/plain": [ "[(1, 1, 0), (1, 0, 1)]" ] }, "execution_count": 11, "metadata": {}, "output_type": "execute_result" } ], "source": [ "%%sql\n", "DROP TABLE IF EXISTS R; CREATE TABLE R (A INT, B INT, C INT);\n", "INSERT INTO R VALUES (1, 1, 0);\n", "INSERT INTO R VALUES (1, 0, 1);\n", "SELECT * FROM R;" ] }, { "cell_type": "code", "execution_count": 10, "metadata": { "collapsed": false }, "outputs": [ { "name": "stdout", "output_type": "stream", "text": [ "Done.\n", "Done.\n", "Done.\n", "Done.\n", "Done.\n", "Done.\n" ] }, { "data": { "text/html": [ "
AB
10
11
AC
10
11
" ] }, "metadata": {}, "output_type": "display_data" } ], "source": [ "%sql DROP TABLE IF EXISTS R1; CREATE TABLE R1 AS SELECT A,B FROM R GROUP BY A,B;\n", "%sql DROP TABLE IF EXISTS R2; CREATE TABLE R2 AS SELECT A,C FROM R GROUP BY A,C;\n", "r1 = %sql SELECT * FROM R1;\n", "r2 = %sql SELECT * FROM R2;\n", "display_side_by_side(r1,r2)" ] }, { "cell_type": "markdown", "metadata": {}, "source": [ "join을 사용하여 두개의 테이블을 결합해보자:" ] }, { "cell_type": "code", "execution_count": 13, "metadata": { "collapsed": false }, "outputs": [ { "name": "stdout", "output_type": "stream", "text": [ "Done.\n" ] }, { "data": { "text/html": [ "\n", " \n", " \n", " \n", " \n", " \n", " \n", " \n", " \n", " \n", " \n", " \n", " \n", " \n", " \n", " \n", " \n", " \n", " \n", " \n", " \n", " \n", " \n", " \n", " \n", " \n", "
ABC
100
101
110
111
" ], "text/plain": [ "[(1, 0, 0), (1, 0, 1), (1, 1, 0), (1, 1, 1)]" ] }, "execution_count": 13, "metadata": {}, "output_type": "execute_result" } ], "source": [ "%%sql\n", "SELECT r1.A AS A, r1.B AS B, r2.C AS C\n", "FROM R1 r1, R2 r2\n", "WHERE r1.A = r2.A;" ] }, { "cell_type": "markdown", "metadata": {}, "source": [ "우와! MVD를 만족하도록 분해했던 결과와 join의 결과와 같다! 이 것이 MVD의 또 다른 정의이다. 'local join': 속성 $A$의 값이 같은 어떤 줄들을 $R_1(A,B)$ 와 $R_2(A,(A\\cup B)^C)$으로 분해 한 후 다시 그 테이블들을 조인하여 이전과 같은 줄들을 얻게 된다면 MVD $\\{A\\}\\twoheadrightarrow\\{B\\}$ 를 만족한다." ] }, { "cell_type": "code", "execution_count": null, "metadata": { "collapsed": true }, "outputs": [], "source": [] } ], "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 }