{ "cells": [ { "cell_type": "code", "execution_count": 1, "metadata": {}, "outputs": [ { "data": { "text/plain": [ "u'Connected: None@PS2.db'" ] }, "execution_count": 1, "metadata": {}, "output_type": "execute_result" } ], "source": [ "%load_ext sql\n", "%sql sqlite:///PS2.db" ] }, { "cell_type": "markdown", "metadata": {}, "source": [ "Problem Set 2\n", "=======\n", "\n", "\n", "### Instructions / Notes:\n", "\n", "**_Read these carefully_**\n", "\n", "* For some of the questions in this problem set _you will need to make your own instances of tables, either as solutions to the problems or for testing solutions to the problems_.\n", "* You **may** create new IPython notebook cells to use for e.g. testing, debugging, exploring, etc.- this is encouraged in fact!- **just make sure that your final answer for each question is _in its own cell_ and _clearly indicated_**\n", "* When you see `In [*]:` to the left of the cell you are executing, this means that the code / query is _running_.\n", " * **If the cell is hanging- i.e. running for too long: To restart the SQL connection, you must restart the entire python kernel**\n", " * To restart kernel using the menu bar: \"Kernel >> Restart >> Clear all outputs & restart\"), then re-execute the sql connection cell at top\n", " * You will also need to restart the connection if you want to load a different version of the database file\n", "* Remember:\n", " * `%sql [SQL]` is for _single line_ SQL queries\n", " * `%%sql [SQL]` is for _multi line_ SQL queries\n", "* **See Piazza for submission instructions**\n", "* _Have fun!_" ] }, { "cell_type": "markdown", "metadata": {}, "source": [ "Problem 1\n", "---------\n", "\n", "For Parts 1 & 2 of this problem you will need to provide a _single_ SQL query which will check whether a certain condition holds on the **hospital** table in the provided database:" ] }, { "cell_type": "code", "execution_count": 2, "metadata": {}, "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", " \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", " \n", " \n", " \n", " \n", " \n", " \n", " \n", " \n", " \n", "
providerhospitaladdresscitystatezipcountyphone_numberhospital_typehospital_owneremergency_serviceconditionmeasure_code
10018CALLAHAN EYE FOUNDATION HOSPITAL1720 UNIVERSITY BLVDBIRMINGHAMAL35233JEFFERSON2053258100Acute Care HospitalsVoluntary non-profit - PrivateYesSurgical Infection PreventionSCIP-CARD-2
10018CALLAHAN EYE FOUNDATION HOSPITAL1720 UNIVERSITY BLVDBIRMINGHAMAL35233JEFFERSON2053258100Acute Care HospitalsVoluntary non-profit - PrivateYesSurgical Infection PreventionSCIP-INF-1
10018CALLAHAN EYE FOUNDATION HOSPITAL1720 UNIVERSITY BLVDBIRMINGHAMAL35233JEFFERSON2053258100Acute Care HospitalsVoluntary non-profit - PrivateYesSurgical Infection PreventionSCIP-INF-2
" ], "text/plain": [ "[(10018, u'CALLAHAN EYE FOUNDATION HOSPITAL', u'1720 UNIVERSITY BLVD', u'BIRMINGHAM', u'AL', 35233, u'JEFFERSON', 2053258100, u'Acute Care Hospitals', u'Voluntary non-profit - Private', u'Yes', u'Surgical Infection Prevention', u'SCIP-CARD-2'),\n", " (10018, u'CALLAHAN EYE FOUNDATION HOSPITAL', u'1720 UNIVERSITY BLVD', u'BIRMINGHAM', u'AL', 35233, u'JEFFERSON', 2053258100, u'Acute Care Hospitals', u'Voluntary non-profit - Private', u'Yes', u'Surgical Infection Prevention', u'SCIP-INF-1'),\n", " (10018, u'CALLAHAN EYE FOUNDATION HOSPITAL', u'1720 UNIVERSITY BLVD', u'BIRMINGHAM', u'AL', 35233, u'JEFFERSON', 2053258100, u'Acute Care Hospitals', u'Voluntary non-profit - Private', u'Yes', u'Surgical Infection Prevention', u'SCIP-INF-2')]" ] }, "execution_count": 2, "metadata": {}, "output_type": "execute_result" } ], "source": [ "%sql select * from hospital limit 3;" ] }, { "cell_type": "markdown", "metadata": {}, "source": [ "You need to evaluate any requested conditions in the following way: **your query should return an empty result if and only if the condition holds on the instance.** If the condition _doesn't hold_, your query should return something non-empty, but it doesn't matter what this is.\n", "\n", "Note our language here: the conditions that we specify cannot be proved to hold **in general** without knowing the externally-defined functional dependencies; so what we mean is, _check whether they **are not violated** for the provided instance_.\n", "\n", "You may assume that there are no `NULL` values in the tables." ] }, { "cell_type": "markdown", "metadata": {}, "source": [ "### Part (a)\n", "\n", "Is $\\{provider\\}$ a **superkey** for relation $Hospital$?" ] }, { "cell_type": "code", "execution_count": null, "metadata": { "collapsed": true }, "outputs": [], "source": [] }, { "cell_type": "markdown", "metadata": {}, "source": [ "### Part (b)\n", "\n", "Does $\\{Zip\\} \\rightarrow \\{City, State\\}$ hold for relation $Hospital$?" ] }, { "cell_type": "code", "execution_count": null, "metadata": { "collapsed": true }, "outputs": [], "source": [] }, { "cell_type": "markdown", "metadata": {}, "source": [ "### Part (c)\n", "\n", "A **multivalued dependency (MVD)** is defined as follows: let $R$ be a schema i.e. a set of attributes, and consider two _sets of attributes_ $X\\subseteq R$ and $Y\\subseteq R$. We say that a multivalued dependency (MVD), written:\n", "\n", "$X\\twoheadrightarrow Y$\n", "\n", "**holds on $R$** if whenever there are two tuples $t_1,t_2$ such that $t_1[A] = t_2[A]$, there also exists a third tuple $t_3$ such that:\n", "\n", "* $t_3[A] = t_1[A] = t_2[A]$\n", "* $t_3[B] = t_1[B]$\n", "* $t_3[R\\setminus B] = t_2[R\\setminus B]$\n", "\n", "Note that $R\\setminus B$ is all the attributes in $R$ that are not in $B$, and that $t_3$ need not be distinct from $t_1$ or $t_2$. Note especially that an MVD holds on an entire _relation_, meaning that any two tuples (in any order) in the relation should satisfy the above conditions if the MVD holds. **See the end of the lecture 8 slides for more on MVDs!**\n", "\n", "\n", "For this part of this problem you will need to provide a _single_ SQL query which will check whether a MVD holds for relation $courses$." ] }, { "cell_type": "code", "execution_count": 3, "metadata": {}, "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", "
coursebooklecturer
DBSilberschatzJohn D
DBNederpeltJohn D
DBSilberschatzWilliam M
" ], "text/plain": [ "[(u'DB', u'Silberschatz', u'John D'),\n", " (u'DB', u'Nederpelt', u'John D'),\n", " (u'DB', u'Silberschatz', u'William M')]" ] }, "execution_count": 3, "metadata": {}, "output_type": "execute_result" } ], "source": [ "%sql select * from courses limit 3;" ] }, { "cell_type": "markdown", "metadata": {}, "source": [ "Write your query to check if the MVD $\\{course\\}\\twoheadrightarrow \\{book\\}$ holds for a relation $courses$." ] }, { "cell_type": "code", "execution_count": null, "metadata": { "collapsed": true }, "outputs": [], "source": [] }, { "cell_type": "markdown", "metadata": {}, "source": [ "Problem 2\n", "---------\n", "\n", "Consider a relation $S(A,B,C,D,E,F)$ with the following functional dependencies:\n", "\n", "* $\\{A\\} \\rightarrow \\{D\\}$\n", "* $\\{A\\} \\rightarrow \\{E\\}$\n", "* $\\{D\\} \\rightarrow \\{C\\}$\n", "* $\\{D\\} \\rightarrow \\{F\\}$\n", "\n", "In each part of this problem, we will examine different properties the provided schema (i.e., the provided relation with the above functional dependencies).\n", "\n", "To answer **yes**, provide python code that assigns the variable ```answer``` to ```True``` and assigns ```explanation``` to be a python string which contains a (short!) explanation of why. For example:\n", "\n", "```python\n", "answer = True\n", "explanation = \"Lise is correct because all keys are superkeys.\"\n", "```\n", "\n", "To answer **no**, provide python code that assigns the variable ```answer``` to ```False``` and assigns ```explanation``` to be a python string which contains a (short!) explanation of why. For example:\n", "\n", "```python\n", "answer = False\n", "explanation = \"D is not a superkey because its closure is {D,C,F}.\"\n", "```" ] }, { "cell_type": "markdown", "metadata": { "collapsed": true }, "source": [ "### Part (a)\n", "\n", "CS564 student Jeff claims that if ${A,B}$ is a superkey. Is Jeff correct?" ] }, { "cell_type": "code", "execution_count": null, "metadata": { "collapsed": true }, "outputs": [], "source": [ "answer = \n", "explanation = \"\"" ] }, { "cell_type": "markdown", "metadata": {}, "source": [ "### Part (b)\n", "\n", "Jeff also claims that the decomposition $ABC$, $CDE$, $EFA$ is lossless. Is Jeff correct?" ] }, { "cell_type": "code", "execution_count": null, "metadata": { "collapsed": true }, "outputs": [], "source": [ "answer = \n", "explanation = \"\"" ] }, { "cell_type": "markdown", "metadata": {}, "source": [ "### Part (c)\n", "\n", "CS564 Maria claims that the decomposition $ABC$, $CDE$, $EFA$ is dependency preserving. Is Maria correct?" ] }, { "cell_type": "code", "execution_count": null, "metadata": { "collapsed": true }, "outputs": [], "source": [ "answer = \n", "explanation = \"\"" ] }, { "cell_type": "markdown", "metadata": {}, "source": [ "### Part (d)\n", "\n", "Now consider a relation $R(X, Y, Z)$ with some list of functional dependencies $f_1, f_2, \\ldots, f_n$. Now suppose that $K$ is a **key** for this relation, given these functional dependencies.\n", "\n", "CS564 student Liam claims that if we add any new functional dependency $f_{n+1} = U \\rightarrow V$ to our list of functional dependencies, then $K$ will still be a key for $R$ given $f_1, f_2, \\ldots, f_{n+1}$. Is Liam correct? If yes, explain why. If no, provide a counter-example in your explanation." ] }, { "cell_type": "code", "execution_count": null, "metadata": { "collapsed": true }, "outputs": [], "source": [ "answer = \n", "explanation = \"\"" ] }, { "cell_type": "markdown", "metadata": {}, "source": [ "Bonus Problem:\n", "-------------\n", "\n", "Prove the **transitivity rule for MVDs**\n", "\n", "If $A\\twoheadrightarrow B$ and $B\\twoheadrightarrow C$ $\\implies$ $A\\twoheadrightarrow C \\setminus B$\n", "\n", "using only the basic definition of an MVD; and where $A,B,C$ are _sets of_ attributes such that $A\\cup B\\cup C\\subseteq R$, where $R$ is the full set of attributes." ] }, { "cell_type": "markdown", "metadata": {}, "source": [] } ], "metadata": { "kernelspec": { "display_name": "Python 2", "language": "python", "name": "python2" }, "language_info": { "codemirror_mode": { "name": "ipython", "version": 2 }, "file_extension": ".py", "mimetype": "text/x-python", "name": "python", "nbconvert_exporter": "python", "pygments_lexer": "ipython2", "version": "2.7.13" } }, "nbformat": 4, "nbformat_minor": 1 }