{ "cells": [ { "cell_type": "code", "execution_count": 2, "metadata": {}, "outputs": [ { "data": { "text/plain": [ "u'Connected: None@PS2.db'" ] }, "execution_count": 2, "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": 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", " \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": 3, "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": 21, "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", " \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", " \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", " \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", " \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", " \n", " \n", " \n", " \n", "
providerhospitaladdresscitystatezipcountyphone_numberhospital_typehospital_owneremergency_serviceconditionmeasure_codeprovider_1hospital_1address_1city_1state_1zip_1county_1phone_number_1hospital_type_1hospital_owner_1emergency_service_1condition_1measure_code_1
10018CALLAHAN EYE FOUNDATION HOSPITAL1720 UNIVERSITY BLVDBIRMINGHAMAL35233JEFFERSON2053258100Acute Care HospitalsVoluntary non-profit - PrivateYesSurgical Infection PreventionSCIP-CARD-210018CALLAHAN EYE FOUNDATION HOSPITAL1720 UNIVERSITY BLVDBIRMINGHAMAL35233JEFFERSON2053258100Acute Care HospitalsVoluntary non-profit - PrivateYesHeart AttackAMI-1
10018CALLAHAN EYE FOUNDATION HOSPITAL1720 UNIVERSITY BLVDBIRMINGHAMAL35233JEFFERSON2053258100Acute Care HospitalsVoluntary non-profit - PrivateYesSurgical Infection PreventionSCIP-CARD-210018CALLAHAN EYE FOUNDATION HOSPITAL1720 UNIVERSITY BLVDBIRMINGHAMAL35233JEFFERSON2053258100Acute Care HospitalsVoluntary non-profit - PrivateYesHeart AttackAMI-2
10018CALLAHAN EYE FOUNDATION HOSPITAL1720 UNIVERSITY BLVDBIRMINGHAMAL35233JEFFERSON2053258100Acute Care HospitalsVoluntary non-profit - PrivateYesSurgical Infection PreventionSCIP-CARD-210018CALLAHAN EYE FOUNDATION HOSPITAL1720 UNIVERSITY BLVDBIRMINGHAMAL35233JEFFERSON2053258100Acute Care HospitalsVoluntary non-profit - PrivateYesHeart AttackAMI-3
10018CALLAHAN EYE FOUNDATION HOSPITAL1720 UNIVERSITY BLVDBIRMINGHAMAL35233JEFFERSON2053258100Acute Care HospitalsVoluntary non-profit - PrivateYesSurgical Infection PreventionSCIP-CARD-210018CALLAHAN EYE FOUNDATION HOSPITAL1720 UNIVERSITY BLVDBIRMINGHAMAL35233JEFFERSON2053258100Acute Care HospitalsVoluntary non-profit - PrivateYesHeart AttackAMI-4
10018CALLAHAN EYE FOUNDATION HOSPITAL1720 UNIVERSITY BLVDBIRMINGHAMAL35233JEFFERSON2053258100Acute Care HospitalsVoluntary non-profit - PrivateYesSurgical Infection PreventionSCIP-CARD-210018CALLAHAN EYE FOUNDATION HOSPITAL1720 UNIVERSITY BLVDBIRMINGHAMAL35233JEFFERSON2053258100Acute Care HospitalsVoluntary non-profit - PrivateYesHeart AttackAMI-5
10018CALLAHAN EYE FOUNDATION HOSPITAL1720 UNIVERSITY BLVDBIRMINGHAMAL35233JEFFERSON2053258100Acute Care HospitalsVoluntary non-profit - PrivateYesSurgical Infection PreventionSCIP-CARD-210018CALLAHAN EYE FOUNDATION HOSPITAL1720 UNIVERSITY BLVDBIRMINGHAMAL35233JEFFERSON2053258100Acute Care HospitalsVoluntary non-profit - PrivateYesHeart AttackAMI-7A
10018CALLAHAN EYE FOUNDATION HOSPITAL1720 UNIVERSITY BLVDBIRMINGHAMAL35233JEFFERSON2053258100Acute Care HospitalsVoluntary non-profit - PrivateYesSurgical Infection PreventionSCIP-CARD-210018CALLAHAN EYE FOUNDATION HOSPITAL1720 UNIVERSITY BLVDBIRMINGHAMAL35233JEFFERSON2053258100Acute Care HospitalsVoluntary non-profit - PrivateYesHeart AttackAMI-8A
10018CALLAHAN EYE FOUNDATION HOSPITAL1720 UNIVERSITY BLVDBIRMINGHAMAL35233JEFFERSON2053258100Acute Care HospitalsVoluntary non-profit - PrivateYesSurgical Infection PreventionSCIP-CARD-210018CALLAHAN EYE FOUNDATION HOSPITAL1720 UNIVERSITY BLVDBIRMINGHAMAL35233JEFFERSON2053258100Acute Care HospitalsVoluntary non-profit - PrivateYesHeart FailureHF-1
10018CALLAHAN EYE FOUNDATION HOSPITAL1720 UNIVERSITY BLVDBIRMINGHAMAL35233JEFFERSON2053258100Acute Care HospitalsVoluntary non-profit - PrivateYesSurgical Infection PreventionSCIP-CARD-210018CALLAHAN EYE FOUNDATION HOSPITAL1720 UNIVERSITY BLVDBIRMINGHAMAL35233JEFFERSON2053258100Acute Care HospitalsVoluntary non-profit - PrivateYesHeart FailureHF-2
10018CALLAHAN EYE FOUNDATION HOSPITAL1720 UNIVERSITY BLVDBIRMINGHAMAL35233JEFFERSON2053258100Acute Care HospitalsVoluntary non-profit - PrivateYesSurgical Infection PreventionSCIP-CARD-210018CALLAHAN EYE FOUNDATION HOSPITAL1720 UNIVERSITY BLVDBIRMINGHAMAL35233JEFFERSON2053258100Acute Care HospitalsVoluntary non-profit - PrivateYesHeart FailureHF-3
" ], "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', 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'Heart Attack', u'AMI-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-CARD-2', 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'Heart Attack', u'AMI-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-CARD-2', 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'Heart Attack', u'AMI-3'),\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-CARD-2', 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'Heart Attack', u'AMI-4'),\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-CARD-2', 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'Heart Attack', u'AMI-5'),\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-CARD-2', 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'Heart Attack', u'AMI-7A'),\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-CARD-2', 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'Heart Attack', u'AMI-8A'),\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-CARD-2', 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'Heart Failure', u'HF-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-CARD-2', 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'Heart Failure', u'HF-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-CARD-2', 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'Heart Failure', u'HF-3')]" ] }, "execution_count": 21, "metadata": {}, "output_type": "execute_result" } ], "source": [ "%%sql \n", "SELECT *\n", "FROM hospital h1, hospital h2\n", "WHERE (h1.provider = h2.provider) \n", " and not (h1.hospital = h2.hospital and\n", " h1.address = h2.address and\n", " h1.city = h2.city and\n", " h1.state = h2.state and\n", " h1.zip = h2.zip and\n", " h1.county = h2.county and\n", " h1.phone_number = h2.phone_number and\n", " h1.hospital_type = h2.hospital_type and\n", " h1.hospital_owner = h2.hospital_owner and\n", " h1.emergency_service = h2.emergency_service and\n", " h1.condition = h2.condition and\n", " h1.measure_code = h2.measure_code) LIMIT 10;" ] }, { "cell_type": "markdown", "metadata": {}, "source": [ "### Part (b)\n", "\n", "Does $\\{Zip\\} \\rightarrow \\{City, State\\}$ hold for relation $Hospital$?" ] }, { "cell_type": "code", "execution_count": 14, "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", "
providerhospitaladdresscitystatezipcountyphone_numberhospital_typehospital_owneremergency_serviceconditionmeasure_codeprovider_1hospital_1address_1city_1state_1zip_1county_1phone_number_1hospital_type_1hospital_owner_1emergency_service_1condition_1measure_code_1
" ], "text/plain": [ "[]" ] }, "execution_count": 14, "metadata": {}, "output_type": "execute_result" } ], "source": [ "%%sql \n", "SELECT *\n", "FROM hospital h1, hospital h2\n", "WHERE (h1.zip = h2.zip) and not (h1.city = h2.city and h1.state = h2.state)" ] }, { "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": 22, "metadata": {}, "outputs": [ { "name": "stdout", "output_type": "stream", "text": [ "Done.\n" ] }, { "data": { "text/html": [ "\n", " \n", " \n", " \n", " \n", " \n", " \n", " \n", " \n", "
coursebooklecturercourse_1book_1lecturer_1
" ], "text/plain": [ "[]" ] }, "execution_count": 22, "metadata": {}, "output_type": "execute_result" } ], "source": [ "%%sql\n", "SELECT *\n", "FROM courses c1, courses c2\n", "WHERE c1.course = c2.course and\n", " NOT EXISTS (\n", " SELECT *\n", " FROM courses c3\n", " WHERE c3.course = c1.course and\n", " c3.book = c1.book and\n", " c3.lecturer = c1.lecturer);" ] }, { "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 relatin 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 = True\n", "explanation = \"Because {AB}+ ={ABCDEF}\"" ] }, { "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 = False\n", "explanation = \"Not lossless because the intersection of CDE and EFA (i.e E) is not a key for either of the relations.\"" ] }, { "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 = False\n", "explanation = \"Not dependency preserving because A -> D is not present in the closure of the unions of projection of FD on the three decomposed relations.\"" ] }, { "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": 23, "metadata": { "collapsed": true }, "outputs": [], "source": [ "answer = False\n", "explanation = \"Conside the following example: FDs: {X,Y} -> Z, K: {X,Y} and we add X -> Y. K is not minimal any more.\"" ] }, { "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": [ "_Proof:_\n", "\n", "1. Suppose that we have two tuples $t_1,t_2$ such that $t_1[A] = t_2[A]$\n", "\n", "2. Because $A\\twoheadrightarrow B$, we know by the definition of an MVD that $\\exists t_3$ s.t.:\n", " 1. $t_3[A] = t_1[A] = t_2[A]$\n", " 2. $t_3[B] = t_1[B]$\n", " 3. $t_3[R\\setminus B]=t_2[R\\setminus B]$\n", "\n", "3. Since $B\\twoheadrightarrow C$, there also $\\exists t_4$ s.t.\n", " 1. $t_4[B] = t_1[B] = t_3[B]$\n", " 2. $t_4[C] = t_1[C]$\n", " 3. $t_4[R\\setminus C] = t_3[R\\setminus C]$\n", "\n", "4. To show that $A\\twoheadrightarrow C \\setminus B$, we next need to show that the following holds: Given $t_1[A] = t_3[A]$, there also $\\exists t_4$ s.t.:\n", " 1. $t_4[A] = t_1[A] = t_3[A]$\n", " 2. $t_4[C\\setminus B] = t_1[C\\setminus B]$\n", " 3. $t_4[R\\setminus (C\\setminus B)] = t_3[R\\setminus (C\\setminus B)]$" ] }, { "cell_type": "markdown", "metadata": {}, "source": [ "We now show that the 4.A-4.C hold:\n", "\n", "4.A: We see that:\n", "\n", "1. $t_4[R\\setminus C] = t_3[R\\setminus C]$ (3.C)\n", "2. $\\implies t_4[A\\setminus C] = t_3[A\\setminus C] = t_1[A\\setminus C]$ (2.A)\n", "3. We also know that $t_4[C] = t_1[C]$ (3.B)\n", "4. $\\implies t_4[(A\\setminus C)\\cup C] = t_1[(A\\setminus C)\\cup C]$\n", "5. $\\implies t_4[A]=t_1[A]$\n", "\n", "4.B: $t_4[C] = t_1[C]$ (3.B) $\\implies t_4[C\\setminus B] = t_1[C\\setminus B]$\n", "\n", "4.C: We see that:\n", "\n", "1. $t_4[R\\setminus C] = t_3[R\\setminus C]$ (3.C)\n", "2. Also $t_4[B] = t_3[B]$ (3.A)\n", "3. $\\implies t_4[(R\\setminus C)\\cup B] = t_3[(R\\setminus C)\\cup B]$\n", "4. $\\implies t_4[R\\setminus (C\\setminus B)] = t_3[R\\setminus (C\\setminus B)]$" ] }, { "cell_type": "markdown", "metadata": {}, "source": [ "Finally, we know that following holds by $A\\twoheadrightarrow B$: Given $t_2[A] = t_4[A]$, there also $\\exists t_5$ s.t.:\n", "* $t_5[A] = t_2[A] = t_4[A]$\n", "* $t_5[B] = t_2[B]$\n", "* $t_5[R\\setminus B] = t_4[R\\setminus B]$\n", "\n", "Now we know the following about $t_5$:\n", "* $t_5[R\\setminus B] = t_4[R\\setminus B] \\implies t_5[C\\setminus B] = t_4[C\\setminus B] = t_1[C\\setminus B]$\n", "* $t_5[R\\setminus B] = t_4[R\\setminus B] \\implies t_5[(R\\setminus C)\\setminus B] = t_4[(R\\setminus C)\\setminus B] = t_3[(R\\setminus C)\\setminus B] = t_2[(R\\setminus C)\\setminus B]$\n", "* However we know that $t_5[B] = t_2[B] \\implies t_5[(R\\setminus C)\\cup B] = t_2[(R\\setminus C)\\cup B] \\implies t_5[R\\setminus(C\\setminus B)] = t_2[R\\setminus(C\\setminus B)]$\n", "\n", "Thus we have arrived at the following statement: given $t_1[A]=t_2[A]$, $\\exists t_5$ s.t.:\n", "* $t_5[A] = t_1[A] = t_2[A]$\n", "* $t_5[C\\setminus B] = t_1[C\\setminus B]$\n", "* $t_5[R\\setminus(C\\setminus B)] = t_2[R\\setminus(C\\setminus B)]$\n", "\n", "Which is equivalent to saying $A\\twoheadrightarrow C\\setminus B$ holds$\\square$." ] }, { "cell_type": "code", "execution_count": null, "metadata": { "collapsed": true }, "outputs": [], "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 }