{
"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",
" A | \n",
" B | \n",
" C | \n",
"
\n",
" \n",
" 1 | \n",
" 1 | \n",
" 0 | \n",
"
\n",
" \n",
" 1 | \n",
" 0 | \n",
" 1 | \n",
"
\n",
"
"
],
"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",
" A | \n",
" B | \n",
" C | \n",
"
\n",
" \n",
" 1 | \n",
" 1 | \n",
" 0 | \n",
"
\n",
" \n",
" 1 | \n",
" 0 | \n",
" 1 | \n",
"
\n",
" \n",
" 1 | \n",
" 1 | \n",
" 1 | \n",
"
\n",
"
"
],
"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",
" A | \n",
" B | \n",
" C | \n",
"
\n",
" \n",
" 1 | \n",
" 1 | \n",
" 0 | \n",
"
\n",
" \n",
" 1 | \n",
" 0 | \n",
" 1 | \n",
"
\n",
" \n",
" 1 | \n",
" 1 | \n",
" 1 | \n",
"
\n",
" \n",
" 1 | \n",
" 0 | \n",
" 0 | \n",
"
\n",
"
"
],
"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",
" A | \n",
" B | \n",
" C | \n",
"
\n",
" \n",
" 1 | \n",
" 1 | \n",
" 0 | \n",
"
\n",
" \n",
" 1 | \n",
" 0 | \n",
" 1 | \n",
"
\n",
"
"
],
"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": [
" "
]
},
"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",
" A | \n",
" B | \n",
" C | \n",
"
\n",
" \n",
" 1 | \n",
" 0 | \n",
" 0 | \n",
"
\n",
" \n",
" 1 | \n",
" 0 | \n",
" 1 | \n",
"
\n",
" \n",
" 1 | \n",
" 1 | \n",
" 0 | \n",
"
\n",
" \n",
" 1 | \n",
" 1 | \n",
" 1 | \n",
"
\n",
"
"
],
"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
}