{
"cells": [
{
"cell_type": "code",
"execution_count": null,
"metadata": {},
"outputs": [],
"source": [
"%load_ext sql\n",
"%sql sqlite:///"
]
},
{
"cell_type": "markdown",
"metadata": {},
"source": [
"Problem Set 2\n",
"=======\n",
"\n",
"\n",
"### Instructions / Notes:\n",
"\n",
"**_Read these carefully_**\n",
"\n",
"* This problem set _does not_ come with a dataset to load; instead, 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",
"**_[15 points total]_**\n",
"\n",
"For each part of this problem you will need to provide a _single_ SQL query which will check whether a certain condition holds on a specific instance of a relation, 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 **could** hold in general for the relation, given any specific set of tuples_.\n",
"\n",
"You may assume that there will be no `NULL` values in the tables, **and you may assume that the relations are _sets_ rather than multisets**, but otherwise your query should work for general instances. We define the schemas of the tables used below for convenience, but in this problem you will need to construct your own test tables if you wish to use them to check your answers!"
]
},
{
"cell_type": "code",
"execution_count": null,
"metadata": {},
"outputs": [],
"source": [
"%%sql\n",
"DROP TABLE IF EXISTS R; CREATE TABLE R (W INT, X INT, Y INT, Z INT);\n",
"DROP TABLE IF EXISTS Cat; CREATE TABLE Cat(cat_name TEXT, breed TEXT, owner_name TEXT);\n",
"DROP TABLE IF EXISTS Owner; CREATE TABLE Owner(owner_name TEXT, ssn INT, hometown TEXT);\n",
"DROP TABLE IF EXISTS S; CREATE TABLE S (A INT, B INT, C INT, D INT, E INT);"
]
},
{
"cell_type": "markdown",
"metadata": {},
"source": [
"### Part (a)\n",
"\n",
"**_[5 points]_**\n",
"\n",
"$\\{X, Y\\}$ is a **superkey** for a relation $R(W,X,Y,Z)$."
]
},
{
"cell_type": "code",
"execution_count": null,
"metadata": {
"collapsed": true
},
"outputs": [],
"source": [
"%%sql"
]
},
{
"cell_type": "markdown",
"metadata": {},
"source": [
"### Part (b)\n",
"\n",
"**_[5 points]_**\n",
"\n",
"The individual attributes of a relation $R(W,X,Y,Z)$ are each keys."
]
},
{
"cell_type": "code",
"execution_count": null,
"metadata": {},
"outputs": [],
"source": [
"%%sql"
]
},
{
"cell_type": "markdown",
"metadata": {},
"source": [
"### Part (c)\n",
"\n",
"**_[5 points]_**\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_ $A\\subseteq R$ and $B\\subseteq R$. We say that a multivalued dependency (MVD), written:\n",
"\n",
"$A\\twoheadrightarrow B$\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 7 slides for more on MVDs!**\n",
"\n",
"\n",
"In this problem, write your query to check if the MVD $\\{B\\}\\twoheadrightarrow \\{D,E\\}$ holds for a relation $S(A, B, C, D, E)$."
]
},
{
"cell_type": "code",
"execution_count": null,
"metadata": {
"collapsed": true
},
"outputs": [],
"source": [
"%%sql"
]
},
{
"cell_type": "markdown",
"metadata": {},
"source": [
"Problem 2\n",
"---------\n",
"\n",
"**_[20 points total]_**\n",
"\n",
"### Part (a)\n",
"\n",
"**_[10 points]_**\n",
"\n",
"Consider a relation $T(V,W,X,Y,Z)$. Provide _two different sets_ of functional dependencies, `F_1` and `F_2`, such that each one results in $T$ having the **largest number of distinct keys** $T$ could possibly have.\n",
"\n",
"Store your lists of FDs as python lists having elements that are _pairs of sets_; for example to set `F_1` as the set consisting of two FDs, $\\{V,W\\}\\rightarrow\\{X,Y\\}$ and $\\{W\\}\\rightarrow\\{X\\}$:\n",
"\n",
"```python\n",
"F_1 = [(set(['V','W']), set(['X','Y'])), (set(['W']), set(['X']))]\n",
"```\n",
"\n",
"*Note: the above is not necessarily one of the FDs- just an example of the syntax!\n",
"\n",
"*Hint: You may use any of the functions from the lecture activities if they seem helpful! However your final answer should not involve these functions directly, nor are they necessary for this problem"
]
},
{
"cell_type": "code",
"execution_count": 4,
"metadata": {
"collapsed": true
},
"outputs": [],
"source": [
"F_1 = []\n",
"\n",
"F_2 = []"
]
},
{
"cell_type": "markdown",
"metadata": {},
"source": [
"### Part (b)\n",
"\n",
"**_[10 points]_**\n",
"\n",
"Consider a schema $T(A_1,...,A_n)$ which has FDs $\\{A_i,A_{i+1}\\}\\rightarrow\\{A_{i+2}\\}$ for $i=1,...,n-2$. Create an instance of $T$, for $n=4$, for which these FDs hold, and no other ones do- i.e. **all other FDs are violated.**\n",
"\n",
"Use a series of `INSERT` statements below to populate the table `T`:"
]
},
{
"cell_type": "code",
"execution_count": null,
"metadata": {},
"outputs": [],
"source": [
"%%sql\n",
"DROP TABLE IF EXISTS T; \n",
"CREATE TABLE T (A int, B int, C int, D int);"
]
},
{
"cell_type": "markdown",
"metadata": {},
"source": [
"Problem 3\n",
"---------\n",
"\n",
"**_[30 points total]_**"
]
},
{
"cell_type": "markdown",
"metadata": {},
"source": [
"Consider a relation $R(X,Y,Z)$. In each part of this problem you will be given a condition, and you need to create the following three instances of $R$ (as tables in SQL):\n",
"\n",
"1. An instance $A$\n",
"2. An instance $B$ which differs from $A$ only in that it has one **_fewer_** row. Any row in B should also be there in A.\n",
"3. An instance $C$ which differs from $A$ only in that it has one **_additional_** row. Apart from the additional row, all the rows of C are same as A."
]
},
{
"cell_type": "markdown",
"metadata": {},
"source": [
"### Part (a)\n",
"\n",
"**_[10 points]_**\n",
"\n",
"Create $A$, $B$ and $C$ such that each individual attribute is a key for $A$, but none of the individual attributes is a key for $B$ or $C$. If you believe that $B$ and/or $C$ cannot be created, provide them as an empty table."
]
},
{
"cell_type": "code",
"execution_count": null,
"metadata": {
"collapsed": true
},
"outputs": [],
"source": [
"%%sql\n",
"DROP TABLE IF EXISTS A;\n",
"DROP TABLE IF EXISTS B;\n",
"DROP TABLE IF EXISTS C;"
]
},
{
"cell_type": "markdown",
"metadata": {},
"source": [
"### Part (b)\n",
"\n",
"**_[10 points]_**\n",
"\n",
"Create $A$, $B$ and $C$ such that ONLY the functional dependencies $\\{Z\\} \\rightarrow \\{Y\\}$ and $\\{X,Z\\} \\rightarrow \\{Y\\}$ hold on $B$, ONLY the functional dependency $\\{X,Z\\} \\rightarrow \\{Y\\}$ holds on $A$ and NO functional dependencies hold on $C$. If you believe $B$ and/or $C$ cannot be created, provide them as an empty table.\n",
"\n"
]
},
{
"cell_type": "code",
"execution_count": null,
"metadata": {
"collapsed": true
},
"outputs": [],
"source": [
"%%sql\n",
"DROP TABLE IF EXISTS A;\n",
"DROP TABLE IF EXISTS B;\n",
"DROP TABLE IF EXISTS C;"
]
},
{
"cell_type": "markdown",
"metadata": {},
"source": [
"### Part (c)\n",
"\n",
"**_[10 points]_**\n",
"\n",
"Create $A$, $B$ and $C$ such that the MVD $Z\\twoheadrightarrow X$ holds in $A$, but not in $B$ or $C$. If you believe that $B$ and/or $C$ cannot be created, provide them as an empty table.\n",
"\n"
]
},
{
"cell_type": "code",
"execution_count": null,
"metadata": {},
"outputs": [],
"source": [
"%%sql\n",
"DROP TABLE IF EXISTS A;\n",
"DROP TABLE IF EXISTS B;\n",
"DROP TABLE IF EXISTS C;"
]
}
],
"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.6"
}
},
"nbformat": 4,
"nbformat_minor": 1
}