{
"cells": [
{
"cell_type": "code",
"execution_count": null,
"metadata": {
"collapsed": false
},
"outputs": [],
"source": [
"%load_ext sql\n",
"%sql sqlite:///"
]
},
{
"cell_type": "markdown",
"metadata": {},
"source": [
"Problem Set 2\n",
"=============\n",
"\n",
"**_[100 points total]_**\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 are encouraged to create new IPython notebook cells to use for testing, debugging, exploring, etc. **Just make sure that your final answer for each question is in its own cell when you submit.**\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): You can restart the SQL connection by restarting the entire python kernel.**\n",
" * To restart the python kernel: Use the menu bar (Kernel >> Restart).\n",
" * To restart the SQL connection: Re-execute the SQL connection cell at the top of the notebook\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",
"**_[20 points total]_**\n",
"\n",
"For each part of this problem you will provide a _single_ SQL query to 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 are specified in each part may not hold **in general** for _any instance_ of a relation without knowing the externally-defined functional dependencies of that relation. You are checking 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 check your answers!**"
]
},
{
"cell_type": "code",
"execution_count": null,
"metadata": {
"collapsed": false
},
"outputs": [],
"source": [
"%%sql\n",
"DROP TABLE IF EXISTS R; CREATE TABLE R (A INT, B INT, C INT, D INT, E INT);\n",
"DROP TABLE IF EXISTS S; CREATE TABLE S (A INT, B INT, C INT);"
]
},
{
"cell_type": "markdown",
"metadata": {},
"source": [
"### Part (a)\n",
"\n",
"**_[5 points]_**\n",
"\n",
"$\\{A, B\\} \\rightarrow \\{C\\}$ and $\\{C\\} \\rightarrow \\{A, B\\}$ hold for a relation $R(A,B,C,D,E)$."
]
},
{
"cell_type": "code",
"execution_count": null,
"metadata": {
"collapsed": false
},
"outputs": [],
"source": [
"%%sql"
]
},
{
"cell_type": "markdown",
"metadata": {},
"source": [
"### Part (b)\n",
"\n",
"**_[5 points]_**\n",
"\n",
"$\\{A, B, C\\}$ is a **superkey** for a relation $R(A,B,C,D,E)$."
]
},
{
"cell_type": "code",
"execution_count": null,
"metadata": {
"collapsed": false
},
"outputs": [],
"source": [
"%%sql"
]
},
{
"cell_type": "markdown",
"metadata": {},
"source": [
"### Part (c)\n",
"\n",
"**_[5 points]_**\n",
"\n",
"$\\{A\\}$ and $\\{B\\}$ are each **keys** for a relation $S(A,B,C)$."
]
},
{
"cell_type": "code",
"execution_count": null,
"metadata": {
"collapsed": false
},
"outputs": [],
"source": [
"%%sql"
]
},
{
"cell_type": "markdown",
"metadata": {},
"source": [
"### Part (d)\n",
"\n",
"**_[5 points]_**\n",
"\n",
"A **multi-valued 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 multi-valued 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[X] = t_2[X]$, there also exists a third tuple $t_3$ such that:\n",
"\n",
"* $t_3[X] = t_1[X] = t_2[X]$\n",
"* $t_3[Y] = t_1[Y]$\n",
"* $t_3[R \\setminus Y] = t_2[R \\setminus Y]$\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 6 slides for more on MVDs!**\n",
"\n",
"\n",
"In this problem, write your query following the specifications listed at the top of problem 1 to check if the MVD $\\{A\\}\\twoheadrightarrow \\{C,E\\}$ holds for a relation $R(A,B,C,D,E)$."
]
},
{
"cell_type": "code",
"execution_count": null,
"metadata": {
"collapsed": false
},
"outputs": [],
"source": [
"%%sql"
]
},
{
"cell_type": "markdown",
"metadata": {},
"source": [
"Problem 2\n",
"---------\n",
"\n",
"**_[30 points total]_**\n",
"\n",
"Consider a relation $R(X, Y, Z)$ with some list of functional dependencies $f_1, f_2, \\ldots, f_n$. Suppose that $K$ is a **superkey** for this relation, given these functional dependencies (recall that any superkey $K$ must be a subset of the attributes of $R$, which are $\\{X, Y, Z\\}$). In each part of this problem, we will examine what can happen if we add an additional functional dependency to our relation.\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, if we are given the statement \"if $K$ is a key, then it will still be a superkey when we add a new functional dependency\", we can give the following answer:\n",
"\n",
"```python\n",
"answer = True\n",
"explanation = \"\"\n",
"```\n",
"\n",
"To answer **no**, provide python code that assigns the variable ```answer``` to ```False```. You must also assign the variable ```K``` to be a set of attributes, the variable ```FDs``` (functional dependencies) to be a python list having elements that are _pairs_ of sets, and the variable ``new_FD`` (the new functional dependency to be added) to be a pair of sets, such that these three variables together produce a counter-example for the desired statement. For example, a counter-example to the statement \"if $K \\rightarrow \\{Z\\}$ is false, then it will remain false when we add a new functional depencency\" could look like: \n",
"\n",
"```python\n",
"answer = False\n",
"K = set(\"X\")\n",
"FDs = [\n",
" (set(\"Y\"), set(\"Z\")),\n",
" (set((\"Y\", \"Z\")), set(\"X\"))\n",
"]\n",
"new_FD = (set(\"X\"), set(\"Z\"))\n",
"```"
]
},
{
"cell_type": "markdown",
"metadata": {},
"source": [
"### Part (a)\n",
"\n",
"**_[10 points]_**\n",
"\n",
"CS145 student Alex claims that if we add any new functional dependency $f_{n+1} = U \\rightarrow V$ (where $U$ and $V$ are subsets of $\\{X, Y, Z\\}$) to our list of functional dependencies, then $K$ will still be a superkey for $R$ given $f_1, f_2, \\ldots, f_{n+1}$. Is Alex correct? If yes, explain why. If no, provide a counter-example."
]
},
{
"cell_type": "code",
"execution_count": null,
"metadata": {
"collapsed": false
},
"outputs": [],
"source": []
},
{
"cell_type": "markdown",
"metadata": {},
"source": [
"### Part (b)\n",
"\n",
"**_[10 points]_**\n",
"\n",
"Consider again 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",
"CS145 student Bryan claims that if we add any new functional dependency $f_{n+1} = U \\rightarrow V$ (where $U$ and $V$ are again subsets of $\\{X, Y, Z\\}$) 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 Bryan correct? If yes, explain why. If no, provide a counter-example."
]
},
{
"cell_type": "code",
"execution_count": null,
"metadata": {
"collapsed": true
},
"outputs": [],
"source": []
},
{
"cell_type": "markdown",
"metadata": {},
"source": [
"### Part (c)\n",
"\n",
"**_[10 points]_**\n",
"\n",
"Consider now a more general relation $R(X_1, X_2, \\ldots, X_m)$ with some list of functional dependencies $f_1, f_2, \\ldots, f_n$. Suppose again that $K$ is a **key** for this relation, given these functional dependencies (recall that any superkey $K$ must be a subset of the attributes of $R$, which are $\\{X_1, X_2, \\ldots X_m\\}$).\n",
"\n",
"CS145 student Chris claims that if we add any new functional dependency $f_{n+1} = U \\rightarrow V$ (where $U$ and $V$ are subsets of $\\{X_1, X_2, \\ldots, X_m\\}$) to our list of functional dependencies, and the new functional dependency **does not include any of the attributes that are in the key $K$** (that is, $U \\cap K = V \\cap K = \\emptyset$), then $K$ will still be a key for $R$ given $f_1, f_2, \\ldots, f_{n+1}$. Is Chris correct? If yes, explain why. If no, provide a counter-example."
]
},
{
"cell_type": "code",
"execution_count": null,
"metadata": {
"collapsed": true
},
"outputs": [],
"source": []
},
{
"cell_type": "markdown",
"metadata": {},
"source": [
"Problem 3\n",
"---------\n",
"\n",
"**_[30 points total]_**\n",
"\n",
"Dan wants to find the keys of a relation based on an instance (the concrete rows stored in a database), rather than the functional dependencies (which are external constraints on the schema), but he isn't sure when this problem is possible. In this problem, you will study potential errors that can occur when using an instance instead of the functional dependencies.\n",
"\n",
"Dan defines a set $K$ to be a **plausible key** for an instance `T` if $K$ could be a superkey for `T`, and no subset of $K$ could possibly be a superkey for `T`. (Equivalently, $K$ is a plausible key for `T` if there is an set of functional dependencies that are consistent with `T` in which $K$ is a superkey, and for all subsets $U \\subset K$, there are no sets of functional dependencies that are consistent with `T` in which $U$ is a superkey.)\n",
"\n",
"Consider a relation $R(A, B, C, D)$ that satisfies the following set of functional dependencies:\n",
"\\begin{align}\n",
"\\{A, B\\} &\\rightarrow \\{C\\} \\\\\n",
"\\{C\\} &\\rightarrow \\{D\\} \\\\\n",
"\\{D\\} &\\rightarrow \\{A, B\\}\n",
"\\end{align}"
]
},
{
"cell_type": "markdown",
"metadata": {},
"source": [
"### Part (a)\n",
"\n",
"**_[10 points]_**\n",
"\n",
"Create an instance `T` of $R$ for which $\\{A, B\\}$ is a plausible key. If you believe that `T` cannot be created, provide it as an empty table.\n",
"\n",
"Use a series of `INSERT` statements below to populate the table `T`."
]
},
{
"cell_type": "code",
"execution_count": null,
"metadata": {
"collapsed": false
},
"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": [
"### Part (b)\n",
"\n",
"**_[10 points]_**\n",
"\n",
"Create an instance `T` of $R$ for which $\\{A\\}$ is a plausible key. If you believe that `T` cannot be created, provide it as an empty table.\n",
"\n",
"Use a series of `INSERT` statements below to populate the table `T`."
]
},
{
"cell_type": "code",
"execution_count": null,
"metadata": {
"collapsed": false
},
"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": [
"### Part (c)\n",
"\n",
"**_[10 points]_**\n",
"\n",
"Create an instance `T` of $R$ for which $\\{A, B, C\\}$ is a plausible key. If you believe that `T` cannot be created, provide it as an empty table.\n",
"\n",
"Use a series of `INSERT` statements below to populate the table `T`."
]
},
{
"cell_type": "code",
"execution_count": null,
"metadata": {
"collapsed": true
},
"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 4\n",
"---------\n",
"\n",
"**_[20 points total]_**\n",
"\n",
"### Part (a)\n",
"\n",
"**_[10 points]_**\n",
"\n",
"Consider a schema $R(A, B, C, D)$ which has functional dependencies\n",
"\\begin{align}\n",
" \\{A, C\\} &\\rightarrow \\{ B \\} \\\\\n",
" \\{D \\} &\\rightarrow \\{ C \\}. \\\\\n",
"\\end{align}\n",
"Create an instance of $R$ which is consistent with these functional dependencies, but not with any other functional dependencies (i.e. **all functional dependencies that are not inferred from these are violated**).\n",
"\n",
"Use a series of `INSERT` statements below to populate the table `R`."
]
},
{
"cell_type": "code",
"execution_count": null,
"metadata": {
"collapsed": false
},
"outputs": [],
"source": [
"%%sql"
]
},
{
"cell_type": "markdown",
"metadata": {},
"source": [
"### Part (b)\n",
"\n",
"**_[10 points]_**\n",
"\n",
"Now consider a schema $S(A, B, C, D, E)$ which has an additional attribute $E$, but the same functional dependencies\n",
"\\begin{align}\n",
" \\{A, C\\} &\\rightarrow \\{ B \\} \\\\\n",
" \\{D \\} &\\rightarrow \\{ C \\}. \\\\\n",
"\\end{align}\n",
"Create an instance of $S$ which is consistent with these functional dependencies, but not with any other functional dependencies (i.e. **all functional dependencies that are not inferred from these are violated**).\n",
"\n",
"Write one or more SQL statements that populate the table `S` using the table `R` you constructed in part (a). You may find the following SQL query helpful: **INSERT INTO S SELECT [SELECT CLAUSE] FROM R;**, where **[SELECT CLAUSE]** is something you will have to fill out."
]
},
{
"cell_type": "code",
"execution_count": null,
"metadata": {
"collapsed": false
},
"outputs": [],
"source": [
"%%sql\n",
"DROP TABLE IF EXISTS S;\n",
"CREATE TABLE S (A int, B int, C int, D int, E int);"
]
}
],
"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.9"
}
},
"nbformat": 4,
"nbformat_minor": 0
}