{
 "cells": [
  {
   "cell_type": "code",
   "execution_count": null,
   "id": "4e054359",
   "metadata": {},
   "outputs": [],
   "source": [
    "import agh_db_lectures\n",
    "agh_db_lectures.prepare_notebook_for_sql()"
   ]
  },
  {
   "cell_type": "markdown",
   "id": "ccff71a5",
   "metadata": {},
   "source": [
    "# Relational Algebra"
   ]
  },
  {
   "cell_type": "markdown",
   "id": "b72b893e",
   "metadata": {},
   "source": [
    "The following **formal** languages exist for expressing queries.\n",
    "\n",
    "- tuple relational calculus\n",
    "- domain relational calculus\n",
    "- **relational algebra**"
   ]
  },
  {
   "cell_type": "markdown",
   "id": "3e7139b8",
   "metadata": {},
   "source": [
    "_notes_\n",
    "\n",
    "We mean queries on relational databases, of course.\n",
    "\n",
    "SQL is based on relational algebra.\n",
    "\n",
    "Sometimes a categorization into declarative (aka nonprocedural) languages (tuple and domain relational calculi) and procedural languges (SQL, relational algebra) is made."
   ]
  },
  {
   "cell_type": "markdown",
   "id": "439b940a",
   "metadata": {},
   "source": [
    "## Relational Algebra Operators"
   ]
  },
  {
   "cell_type": "markdown",
   "id": "bfaad0ad",
   "metadata": {},
   "source": [
    "- selection — $\\sigma$\n",
    "- projection – $\\Pi$\n",
    "- union — $\\cup$\n",
    "- set difference — $-$\n",
    "- cartesian product — $\\times$\n",
    "- renaming — $\\rho$\n",
    "\n",
    "- set intersection — $\\cap$\n",
    "- (natural) join — $\\bowtie$ (and \"outer\" variants $⟕$, $⟖$, and $⟗$)\n",
    "- assignment — $\\leftarrow$\n",
    "\n",
    "and extended relational algebra operators\n",
    "\n",
    "- generalized projection — $\\Pi$\n",
    "- aggregation – $\\mathcal{G}$ (or $\\gamma$)"
   ]
  },
  {
   "cell_type": "markdown",
   "id": "08012f1f",
   "metadata": {},
   "source": [
    "_notes_\n",
    "\n",
    "The operators from intersection onwards are sometimes labeled \"additional\".\n",
    "\n",
    "The operators correspond to operations that we perform in SQL.\n",
    "\n",
    "They **operate on relations**, i.e., the arguments of the operators are relations (sets of tuples) and the result of each operation is a relation (a set of tuples).\n",
    "\n",
    "In its basic form, the algebra considers relations as mathematical sets (without duplicates)."
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "id": "bb64cdc4",
   "metadata": {},
   "outputs": [],
   "source": [
    "%sql postgresql://demo_user:demo_pwd@localhost:25432/agh_it_northwind\n",
    "%config SqlMagic.feedback = False"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "id": "acfd5a4d",
   "metadata": {},
   "outputs": [],
   "source": [
    "agh_db_lectures.nw_diagram.download_open()"
   ]
  },
  {
   "cell_type": "markdown",
   "id": "c2faffdc",
   "metadata": {},
   "source": [
    "_notes_\n",
    "\n",
    "We shall use the Northwind db as example.\n",
    "\n",
    "We are going to preset relational algebra epressions together with their SQL equivalents."
   ]
  },
  {
   "cell_type": "markdown",
   "id": "86d4ddff",
   "metadata": {},
   "source": [
    "## Selection"
   ]
  },
  {
   "cell_type": "markdown",
   "id": "79c78b7e",
   "metadata": {},
   "source": [
    "$\\sigma_{units\\_in\\_stock=0}(products)$"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "id": "55e68362",
   "metadata": {},
   "outputs": [],
   "source": [
    "%%sql\n",
    "SELECT * FROM products WHERE units_in_stock = 0"
   ]
  },
  {
   "cell_type": "markdown",
   "id": "86f5bdda",
   "metadata": {},
   "source": [
    "Logical operators can be used in the condition of a selection.\n",
    "\n",
    "$\\sigma_{units\\_in\\_stock=0 \\land units\\_on\\_order > 0}(products)$"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "id": "f0559ba2",
   "metadata": {},
   "outputs": [],
   "source": [
    "%%sql\n",
    "SELECT * FROM products WHERE units_in_stock = 0 AND units_on_order > 0"
   ]
  },
  {
   "cell_type": "markdown",
   "id": "c78224a2",
   "metadata": {},
   "source": [
    "## Projection"
   ]
  },
  {
   "cell_type": "markdown",
   "id": "46286a9b",
   "metadata": {},
   "source": [
    "$\\Pi_{category\\_id, category\\_name}(categories)$"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "id": "f0721688",
   "metadata": {},
   "outputs": [],
   "source": [
    "%%sql\n",
    "SELECT category_id, category_name FROM categories"
   ]
  },
  {
   "cell_type": "markdown",
   "id": "530f3e08",
   "metadata": {},
   "source": [
    "The operators can be combined (one can act on the result of another).\n",
    "\n",
    "$\\Pi_{product\\_name}(\\sigma_{units\\_in\\_stock=0}(products))$"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "id": "06f3cc54",
   "metadata": {},
   "outputs": [],
   "source": [
    "%%sql\n",
    "SELECT product_name FROM products WHERE units_in_stock = 0"
   ]
  },
  {
   "cell_type": "markdown",
   "id": "a05a83a6",
   "metadata": {},
   "source": [
    "_notes_\n",
    "\n",
    "Note that to fully match the formal meaning of relational algebra operators, we'd need to remove duplicates (e.g., with `SELECT DISTINCT`) in all SQL queries.  In our examples we only use it where actually necessary to avoid duplicates when working with our database instance."
   ]
  },
  {
   "cell_type": "markdown",
   "id": "58cc2503",
   "metadata": {},
   "source": [
    "## Union"
   ]
  },
  {
   "cell_type": "markdown",
   "id": "a45ac8bf",
   "metadata": {},
   "source": [
    "$\\sigma_{units\\_in\\_stock=0}(products) \\cup \\sigma_{discontinued=1}(products)$\n",
    "\n",
    "Input relations must have the same number of attributes and attributes must have compatible domains."
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "id": "fd358205",
   "metadata": {},
   "outputs": [],
   "source": [
    "%%sql\n",
    "SELECT * FROM products WHERE units_in_stock = 0 OR discontinued = 1"
   ]
  },
  {
   "cell_type": "markdown",
   "id": "c0a4eb06",
   "metadata": {},
   "source": [
    "We could've also written the SQL like this.\n",
    "\n",
    "```sql\n",
    "SELECT * FROM products WHERE units_in_stock = 0\n",
    "UNION\n",
    "SELECT * FROM products WHERE discontinued = 1\n",
    "```"
   ]
  },
  {
   "cell_type": "markdown",
   "id": "68158f63",
   "metadata": {},
   "source": [
    "## Difference"
   ]
  },
  {
   "cell_type": "markdown",
   "id": "8806fad4",
   "metadata": {},
   "source": [
    "$\\sigma_{units\\_in\\_stock=0}(products) - \\sigma_{discontinued=1}(products)$"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "id": "61f37d8b",
   "metadata": {},
   "outputs": [],
   "source": [
    "%%sql\n",
    "SELECT * FROM products WHERE units_in_stock = 0 AND NOT discontinued = 1"
   ]
  },
  {
   "cell_type": "markdown",
   "id": "45003f18",
   "metadata": {},
   "source": [
    "We could've also written the SQL using the `EXCEPT` keyword."
   ]
  },
  {
   "cell_type": "markdown",
   "id": "c2effdb9",
   "metadata": {},
   "source": [
    "## Cartesian Product"
   ]
  },
  {
   "cell_type": "markdown",
   "id": "a2226249",
   "metadata": {},
   "source": [
    "$\\Pi_{first\\_name, last\\_name, category\\_name}(employees \\times categories)$"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "id": "0be27021",
   "metadata": {},
   "outputs": [],
   "source": [
    "%%sql\n",
    "SELECT first_name, last_name, category_name FROM employees, categories"
   ]
  },
  {
   "cell_type": "markdown",
   "id": "7a66c12b",
   "metadata": {},
   "source": [
    "## Renaming"
   ]
  },
  {
   "cell_type": "markdown",
   "id": "ffb122f5",
   "metadata": {},
   "source": [
    "$\\rho_{contacts(customer\\_name, customer\\_contact)}(\\Pi_{company\\_name, phone}(customers))$"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "id": "5bd0b98d",
   "metadata": {},
   "outputs": [],
   "source": [
    "%%sql\n",
    "SELECT company_name AS customer_name, phone AS customer_contact FROM customers"
   ]
  },
  {
   "cell_type": "markdown",
   "id": "9233b24e",
   "metadata": {},
   "source": [
    "$\\Pi_{a.first\\_name, a.last\\_name, b.first\\_name, b.last\\_name}(\\rho_a(employees) \\times \\rho_b(employees))$"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "id": "4de3c50a",
   "metadata": {},
   "outputs": [],
   "source": [
    "%%sql\n",
    "SELECT a.first_name, a.last_name, b.first_name, b.last_name\n",
    "FROM employees a, employees b"
   ]
  },
  {
   "cell_type": "markdown",
   "id": "78c0997c",
   "metadata": {},
   "source": [
    "## Constant Relations"
   ]
  },
  {
   "cell_type": "markdown",
   "id": "d70864e0",
   "metadata": {},
   "source": [
    "$\\rho_{city(name, latitude, longitude)}(\\{({\\rm Cracov}, 50.06, 19.93), ({\\rm Corinth}, 37.94, 22.93), ({\\rm Boston}, 42.36, -71.06)\\})$"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "id": "58d7160e",
   "metadata": {},
   "outputs": [],
   "source": [
    "%%sql\n",
    "SELECT *\n",
    "FROM (VALUES ('Cracov', 50.06, 19.93),\n",
    "             ('Corinth', 37.94, 22.93),\n",
    "             ('Boston', 42.36, -71.06)) AS city (name, latitude, longitude)"
   ]
  },
  {
   "cell_type": "markdown",
   "id": "05818736",
   "metadata": {},
   "source": [
    "## Intersection"
   ]
  },
  {
   "cell_type": "markdown",
   "id": "078f87b1",
   "metadata": {},
   "source": [
    "Could also be expressed using a composition of set difference operations.\n",
    "\n",
    "$\\Pi_{supplier\\_id}(\\sigma_{category\\_id=1}(products)) \\cap \\Pi_{supplier\\_id}(\\sigma_{country={\\rm USA}}(suppliers))$"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "id": "42017250",
   "metadata": {},
   "outputs": [],
   "source": [
    "%%sql\n",
    "SELECT DISTINCT supplier_id FROM products WHERE category_id = 1\n",
    "INTERSECT\n",
    "SELECT supplier_id FROM suppliers WHERE country = 'USA'"
   ]
  },
  {
   "cell_type": "markdown",
   "id": "1b238ba7",
   "metadata": {},
   "source": [
    "## Assignment"
   ]
  },
  {
   "cell_type": "markdown",
   "id": "65094d7d",
   "metadata": {},
   "source": [
    "$cat1\\_suppliers \\leftarrow \\Pi_{supplier\\_id}(\\sigma_{category\\_id=1}(products))$\n",
    "\n",
    "$usa\\_suppliers \\leftarrow \\Pi_{supplier\\_id}(\\sigma_{country={\\rm USA}}(suppliers))$\n",
    "\n",
    "$cat1\\_suppliers \\cap usa\\_suppliers$"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "id": "2f3c67dc",
   "metadata": {},
   "outputs": [],
   "source": [
    "%%sql\n",
    "DROP TABLE IF EXISTS cat1_suppliers;\n",
    "CREATE TABLE cat1_suppliers AS\n",
    "SELECT DISTINCT supplier_id FROM products WHERE category_id = 1;\n",
    "\n",
    "DROP TABLE IF EXISTS usa_suppliers;\n",
    "CREATE TABLE usa_suppliers AS\n",
    "SELECT supplier_id FROM suppliers WHERE country = 'USA';\n",
    "\n",
    "SELECT * FROM cat1_suppliers INTERSECT SELECT * FROM usa_suppliers"
   ]
  },
  {
   "cell_type": "markdown",
   "id": "bbe1ff8c",
   "metadata": {},
   "source": [
    "### Insertion, Modification, Deletion"
   ]
  },
  {
   "cell_type": "markdown",
   "id": "ac7ff10f",
   "metadata": {},
   "source": [
    "```sql\n",
    "DELETE FROM products WHERE discontinued = 1 AND units_in_stock = 0\n",
    "```"
   ]
  },
  {
   "cell_type": "markdown",
   "id": "0ad608cf",
   "metadata": {},
   "source": [
    "This can be expressed using the operators we already know."
   ]
  },
  {
   "cell_type": "markdown",
   "id": "f6a8545e",
   "metadata": {},
   "source": [
    "_notes_\n",
    "\n",
    "Any ideas?"
   ]
  },
  {
   "cell_type": "markdown",
   "id": "2263914e",
   "metadata": {},
   "source": [
    "$products \\leftarrow products - \\sigma_{discontinued=1 \\land units\\_in\\_stock=0}(products)$"
   ]
  },
  {
   "cell_type": "markdown",
   "id": "8a20bd4b",
   "metadata": {},
   "source": [
    "## Natural Join"
   ]
  },
  {
   "cell_type": "markdown",
   "id": "6a4818aa",
   "metadata": {},
   "source": [
    "Could also be expressed as a composition of cartesian product, selection and projection.\n",
    "\n",
    "$\\Pi_{category\\_id, category\\_name, product\\_name}(categories \\bowtie products)$"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "id": "9c0ce2c5",
   "metadata": {},
   "outputs": [],
   "source": [
    "%%sql\n",
    "SELECT category_id, category_name, product_name\n",
    "FROM categories NATURAL JOIN products"
   ]
  },
  {
   "cell_type": "markdown",
   "id": "67d1f770",
   "metadata": {},
   "source": [
    "### Outer Joins"
   ]
  },
  {
   "cell_type": "markdown",
   "id": "9c13c17c",
   "metadata": {},
   "source": [
    "$\\Pi_{company\\_name, order\\_id, order\\_date}(customers ⟕ orders)$"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "id": "67e3e476",
   "metadata": {},
   "outputs": [],
   "source": [
    "%%sql\n",
    "SELECT company_name, order_id, order_date\n",
    "FROM customers NATURAL LEFT JOIN orders"
   ]
  },
  {
   "cell_type": "markdown",
   "id": "260ef853",
   "metadata": {},
   "source": [
    "_notes_\n",
    "\n",
    "There are also symbols $⟖$ and $⟗$ that are used for natural left outer join and natural full outer join, respectively. "
   ]
  },
  {
   "cell_type": "markdown",
   "id": "7a81b9de",
   "metadata": {},
   "source": [
    "## Theta Join"
   ]
  },
  {
   "cell_type": "markdown",
   "id": "c1e17ced",
   "metadata": {},
   "source": [
    "This is a join with arbitrary condition.\n",
    "\n",
    "$\\bowtie_{\\Theta}$"
   ]
  },
  {
   "cell_type": "markdown",
   "id": "b166dbab",
   "metadata": {},
   "source": [
    "_notes_\n",
    "\n",
    "The name \"theta join\" name comes from the notation above, where $\\Theta$ (theta) in the subscript represets the condition."
   ]
  },
  {
   "cell_type": "markdown",
   "id": "140b0b36",
   "metadata": {},
   "source": [
    "$\\Pi_{e.first\\_name, e.last\\_name, b.first\\_name, b.last\\_name}(\\\\\\rho_e(employees) \\bowtie_{e.reports\\_to = b.employee\\_id} \\rho_b(employees))$"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "id": "aeea7146",
   "metadata": {},
   "outputs": [],
   "source": [
    "%%sql\n",
    "SELECT e.first_name, e.last_name, b.first_name, b.last_name\n",
    "FROM employees e JOIN employees b ON e.reports_to = b.employee_id"
   ]
  },
  {
   "cell_type": "markdown",
   "id": "b9e45942",
   "metadata": {},
   "source": [
    "_notes_\n",
    "\n",
    "Outer join variants can also be used as theta joins."
   ]
  },
  {
   "cell_type": "markdown",
   "id": "7921f240",
   "metadata": {},
   "source": [
    "## Generalized Projection"
   ]
  },
  {
   "cell_type": "markdown",
   "id": "afc54d91",
   "metadata": {},
   "source": [
    "$\\Pi_{order\\_id, product\\_id, unit\\_price \\cdot quantity}(order\\_details)$"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "id": "eeec87fb",
   "metadata": {},
   "outputs": [],
   "source": [
    "%%sql\n",
    "SELECT order_id, product_id, unit_price * quantity FROM order_details"
   ]
  },
  {
   "cell_type": "markdown",
   "id": "b246fb9d",
   "metadata": {},
   "source": [
    "_notes_\n",
    "\n",
    "The only difference from normal projection is that operations can be performed on values.  There is not dedicated symbol for generalized projection."
   ]
  },
  {
   "cell_type": "markdown",
   "id": "bc804c3e",
   "metadata": {},
   "source": [
    "## Aggregation"
   ]
  },
  {
   "cell_type": "markdown",
   "id": "d777b3f1",
   "metadata": {},
   "source": [
    "$_{id}\\mathcal{G}_{id, sum(value)}(\\rho_{v(id, value)}(\\Pi_{order\\_id, unit\\_price \\cdot quantity}(order\\_details)))$\n",
    "\n",
    "The meaning of lower-index text of the aggregation oprator is as annotated below.\n",
    "\n",
    "$_{\\underset{grouping \\atop attribtues}{id}}\\mathcal{G}_{\\underset{expressions\\ list \\atop (with\\ aggregate\\ functions)}{id, sum(value)}}$"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "id": "e06b5021",
   "metadata": {},
   "outputs": [],
   "source": [
    "%%sql\n",
    "SELECT order_id AS id, SUM(unit_price * quantity)\n",
    "FROM order_details\n",
    "GROUP BY order_id"
   ]
  }
 ],
 "metadata": {
  "kernelspec": {
   "display_name": "Python 3 (ipykernel)",
   "language": "/gnu/store/q35bxk1i5blx0rcgxphhrq9xqmgha9bz-python-3.11.11/bin/python3",
   "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.11.11"
  }
 },
 "nbformat": 4,
 "nbformat_minor": 5
}