Rule-based Optimization.ipynb

{
 "cells": [
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "# Query optimization of relational algebra in Python.\n",
    "\n",
    "Copyright Jens Dittrich & Felix Martin Schuhknecht & Marcel Maltry [Big Data Analytics Group](https://bigdata.uni-saarland.de/), [CC-BY-SA](https://creativecommons.org/licenses/by-sa/4.0/legalcode)\n",
    "\n",
    "## Rule-based Optimization\n",
    "\n",
    "### Imports and Setup"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 1,
   "metadata": {},
   "outputs": [],
   "source": [
    "from graphviz import Digraph, Source\n",
    "from ra.relation import Relation\n",
    "from ra.utils import load_csv\n",
    "from ra.operators_log import *\n",
    "from ra.operators_phys import *\n",
    "from ra.rule import *\n",
    "from ra.rules_log import *\n",
    "from ra.rules_phys import *\n",
    "\n",
    "import copy"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 2,
   "metadata": {
    "scrolled": false
   },
   "outputs": [
    {
     "name": "stdout",
     "output_type": "stream",
     "text": [
      "{'movies_directors': ----------------\n",
      "\u001b[1mmovies_directors\u001b[0m \n",
      "--------------------------\n",
      "\u001b[1mdirector_id  movie_id     \u001b[0m \n",
      "--------------------------\n",
      "43095        121538       \n",
      "78273        223710       \n",
      "78273        118367       \n",
      "78273        164572       \n",
      "78273        267038       \n",
      "43095        299073       \n",
      "11652        10920        \n",
      "11652        333856       \n",
      "78273        176711       \n",
      "43095        291833       \n",
      "\n",
      "WARNING: skipping 30 out of 40 tuples..., 'actors': ------\n",
      "\u001b[1mactors\u001b[0m \n",
      "--------------------------------------------------------------------------------------------\n",
      "\u001b[1mid                     first_name             last_name              gender                 \u001b[0m \n",
      "--------------------------------------------------------------------------------------------\n",
      "452838                 Burr                   Steers                 M                      \n",
      "54507                  Buff                   Brady                  M                      \n",
      "363245                 James                  Parks                  M                      \n",
      "331537                 Wayne (I)              Morris                 M                      \n",
      "334067                 Marcus K.              Mukai                  M                      \n",
      "718489                 Harriet                Medin                  F                      \n",
      "512106                 Robert (I)             Williams               M                      \n",
      "58357                  Dr. John               Broadwater             M                      \n",
      "285138                 Mike                   Lovell                 M                      \n",
      "160622                 Ken (I)                Fritz                  M                      \n",
      "\n",
      "WARNING: skipping 1081 out of 1091 tuples..., 'directors': ---------\n",
      "\u001b[1mdirectors\u001b[0m \n",
      "------------------------------------\n",
      "\u001b[1mid          first_name  last_name   \u001b[0m \n",
      "------------------------------------\n",
      "11652       James (I)   Cameron     \n",
      "78273       Quentin     Tarantino   \n",
      "43095       Stanley     Kubrick     \n",
      ", 'movies_genres': -------------\n",
      "\u001b[1mmovies_genres\u001b[0m \n",
      "--------------------------\n",
      "\u001b[1mmovie_id     genre        \u001b[0m \n",
      "--------------------------\n",
      "369522       Fantasy      \n",
      "79846        Documentary  \n",
      "79846        Short        \n",
      "106666       Drama        \n",
      "5306         Action       \n",
      "328277       Sci-Fi       \n",
      "340799       Romance      \n",
      "276217       Crime        \n",
      "176712       Drama        \n",
      "30431        War          \n",
      "\n",
      "WARNING: skipping 92 out of 102 tuples..., 'directors_genres': ----------------\n",
      "\u001b[1mdirectors_genres\u001b[0m \n",
      "---------------------------------------\n",
      "\u001b[1mdirector_id  genre        prob         \u001b[0m \n",
      "---------------------------------------\n",
      "11652        Fantasy      0.0833333    \n",
      "43095        Thriller     0.1875       \n",
      "78273        Action       0.5          \n",
      "43095        Music        0.0625       \n",
      "43095        Mystery      0.0625       \n",
      "43095        Documentary  0.1875       \n",
      "11652        Horror       0.166667     \n",
      "78273        Comedy       0.25         \n",
      "78273        Drama        0.75         \n",
      "11652        Action       0.5          \n",
      "\n",
      "WARNING: skipping 25 out of 35 tuples..., 'movies': ------\n",
      "\u001b[1mmovies\u001b[0m \n",
      "----------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------\n",
      "\u001b[1mid                                                                    name                                                                  year                                                                  rank                                                                  \u001b[0m \n",
      "----------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------\n",
      "177019                                                                Killing, The                                                          1956                                                                  8.1                                                                   \n",
      "10920                                                                 Aliens                                                                1986                                                                  8.2                                                                   \n",
      "340799                                                                True Lies                                                             1994                                                                  7.0                                                                   \n",
      "299073                                                                Shining, The                                                          1980                                                                  8.2                                                                   \n",
      "159665                                                                Inglorious Bastards                                                   2006                                                                  8.3                                                                   \n",
      "310455                                                                Spartacus                                                             1960                                                                  8.0                                                                   \n",
      "322652                                                                T2 3-D: Battle Across Time                                            1996                                                                  7.4                                                                   \n",
      "92616                                                                 Dr. Strangelove or: How I Learned to Stop Worrying and Love the Bomb  1964                                                                  8.7                                                                   \n",
      "30431                                                                 Barry Lyndon                                                          1975                                                                  7.9                                                                   \n",
      "96779                                                                 Earthship.TV                                                          2001                                                                  5.6                                                                   \n",
      "\n",
      "WARNING: skipping 30 out of 40 tuples..., 'roles': -----\n",
      "\u001b[1mroles\u001b[0m \n",
      "---------------------------------------------------------------------------------------------\n",
      "\u001b[1mactor_id                       movie_id                       role                           \u001b[0m \n",
      "---------------------------------------------------------------------------------------------\n",
      "714657                         164572                         Girl at Security Gate          \n",
      "374784                         267038                         Dean Martin                    \n",
      "210153                         267038                         Ed Sullivan                    \n",
      "712889                         5306                           Lindsey Brigman                \n",
      "839709                         65764                          Girl in ascot fantasy          \n",
      "498580                         223710                         Lenny Otis                     \n",
      "426628                         340799                         Harry Tasker                   \n",
      "332070                         328277                         Dr. Miles Bennett Dyson        \n",
      "70744                          333856                         Second-class man               \n",
      "11865                          333856                         Lookout Fredrick Fleet         \n",
      "\n",
      "WARNING: skipping 1196 out of 1206 tuples...}\n"
     ]
    }
   ],
   "source": [
    "from os import listdir\n",
    "\n",
    "# Data source: https://relational.fit.cvut.cz/dataset/IMDb\n",
    "# Information courtesy of IMDb (http://www.imdb.com). Used with permission.\n",
    "# Notice: The data can only be used for personal and non-commercial use and must not\n",
    "# be altered/republished/resold/repurposed to create any kind of online/offline\n",
    "# database of movie information (except for individual personal use).\n",
    "\n",
    "path = 'data/IMDb_sample'  \n",
    "# create a list of all files in that directory that end with \"*.csv\":\n",
    "files = [file for file in listdir(path) if file.endswith('.csv')]\n",
    "\n",
    "relations = [load_csv(path + '/' + file, file[:-4], delimiter='\\t') for file in files]\n",
    "\n",
    "relationsDict = {}\n",
    "for rel in relations:\n",
    "    relationsDict[rel.name] = rel\n",
    "print(relationsDict)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 3,
   "metadata": {},
   "outputs": [],
   "source": [
    "# build LeafRelation object from relations dictionary\n",
    "movies_directors = LeafRelation(relationsDict['movies_directors'])\n",
    "actors = LeafRelation(relationsDict['actors'])\n",
    "directors = LeafRelation(relationsDict['directors'])\n",
    "movies_genres = LeafRelation(relationsDict['movies_genres'])\n",
    "directors_genres = LeafRelation(relationsDict['directors_genres'])\n",
    "movies = LeafRelation(relationsDict['movies'])\n",
    "roles = LeafRelation(relationsDict['roles'])"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 4,
   "metadata": {},
   "outputs": [],
   "source": [
    "# build indexes\n",
    "#directors_genres.relation.build_index('genre')\n",
    "#directors_genres.relation.build_index('prob')"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "### Example"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "An example for an unoptimized logical operator tree (aka **canonical plan**):"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 5,
   "metadata": {},
   "outputs": [
    {
     "data": {
      "image/svg+xml": [
       "<?xml version=\"1.0\" encoding=\"UTF-8\" standalone=\"no\"?>\n",
       "<!DOCTYPE svg PUBLIC \"-//W3C//DTD SVG 1.1//EN\"\n",
       " \"http://www.w3.org/Graphics/SVG/1.1/DTD/svg11.dtd\">\n",
       "<!-- Generated by graphviz version 2.47.2 (20210527.0053)\n",
       " -->\n",
       "<!-- Pages: 1 -->\n",
       "<svg width=\"347pt\" height=\"404pt\"\n",
       " viewBox=\"0.00 0.00 347.27 404.00\" xmlns=\"http://www.w3.org/2000/svg\" xmlns:xlink=\"http://www.w3.org/1999/xlink\">\n",
       "<g id=\"graph0\" class=\"graph\" transform=\"scale(1 1) rotate(0) translate(4 400)\">\n",
       "<polygon fill=\"white\" stroke=\"transparent\" points=\"-4,4 -4,-400 343.27,-400 343.27,4 -4,4\"/>\n",
       "<!-- Pro -->\n",
       "<g id=\"node1\" class=\"node\">\n",
       "<title>Pro</title>\n",
       "<ellipse fill=\"#76d6ff\" stroke=\"#76d6ff\" cx=\"169.63\" cy=\"-378\" rx=\"83.39\" ry=\"18\"/>\n",
       "<text text-anchor=\"middle\" x=\"169.63\" y=\"-374.3\" font-family=\"Times,serif\" font-size=\"14.00\">π_[last_name, prob]</text>\n",
       "</g>\n",
       "<!-- ISel -->\n",
       "<g id=\"node2\" class=\"node\">\n",
       "<title>ISel</title>\n",
       "<ellipse fill=\"#ffd479\" stroke=\"#ffd479\" cx=\"169.63\" cy=\"-306\" rx=\"148.67\" ry=\"18\"/>\n",
       "<text text-anchor=\"middle\" x=\"169.63\" y=\"-302.3\" font-family=\"Times,serif\" font-size=\"14.00\">σ_[genre == &#39;Mystery&#39; or prob &gt;= 0.3]</text>\n",
       "</g>\n",
       "<!-- ISel&#45;&gt;Pro -->\n",
       "<g id=\"edge6\" class=\"edge\">\n",
       "<title>ISel&#45;&gt;Pro</title>\n",
       "<path fill=\"none\" stroke=\"black\" d=\"M169.63,-324.3C169.63,-332.02 169.63,-341.29 169.63,-349.89\"/>\n",
       "<polygon fill=\"black\" stroke=\"black\" points=\"166.14,-349.9 169.63,-359.9 173.14,-349.9 166.14,-349.9\"/>\n",
       "</g>\n",
       "<!-- IISel -->\n",
       "<g id=\"node3\" class=\"node\">\n",
       "<title>IISel</title>\n",
       "<ellipse fill=\"#ffd479\" stroke=\"#ffd479\" cx=\"169.63\" cy=\"-234\" rx=\"169.77\" ry=\"18\"/>\n",
       "<text text-anchor=\"middle\" x=\"169.63\" y=\"-230.3\" font-family=\"Times,serif\" font-size=\"14.00\">σ_[last_name == &#39;Tarantino&#39; and prob &lt; 0.7]</text>\n",
       "</g>\n",
       "<!-- IISel&#45;&gt;ISel -->\n",
       "<g id=\"edge5\" class=\"edge\">\n",
       "<title>IISel&#45;&gt;ISel</title>\n",
       "<path fill=\"none\" stroke=\"black\" d=\"M169.63,-252.3C169.63,-260.02 169.63,-269.29 169.63,-277.89\"/>\n",
       "<polygon fill=\"black\" stroke=\"black\" points=\"166.14,-277.9 169.63,-287.9 173.14,-277.9 166.14,-277.9\"/>\n",
       "</g>\n",
       "<!-- IIISel -->\n",
       "<g id=\"node4\" class=\"node\">\n",
       "<title>IIISel</title>\n",
       "<ellipse fill=\"#ffd479\" stroke=\"#ffd479\" cx=\"169.63\" cy=\"-162\" rx=\"87.18\" ry=\"18\"/>\n",
       "<text text-anchor=\"middle\" x=\"169.63\" y=\"-158.3\" font-family=\"Times,serif\" font-size=\"14.00\">σ_[id == director_id]</text>\n",
       "</g>\n",
       "<!-- IIISel&#45;&gt;IISel -->\n",
       "<g id=\"edge4\" class=\"edge\">\n",
       "<title>IIISel&#45;&gt;IISel</title>\n",
       "<path fill=\"none\" stroke=\"black\" d=\"M169.63,-180.3C169.63,-188.02 169.63,-197.29 169.63,-205.89\"/>\n",
       "<polygon fill=\"black\" stroke=\"black\" points=\"166.14,-205.9 169.63,-215.9 173.14,-205.9 166.14,-205.9\"/>\n",
       "</g>\n",
       "<!-- IIIICar -->\n",
       "<g id=\"node5\" class=\"node\">\n",
       "<title>IIIICar</title>\n",
       "<ellipse fill=\"#d4fb79\" stroke=\"#d4fb79\" cx=\"169.63\" cy=\"-90\" rx=\"27\" ry=\"18\"/>\n",
       "<text text-anchor=\"middle\" x=\"169.63\" y=\"-86.3\" font-family=\"Times,serif\" font-size=\"14.00\">×</text>\n",
       "</g>\n",
       "<!-- IIIICar&#45;&gt;IIISel -->\n",
       "<g id=\"edge3\" class=\"edge\">\n",
       "<title>IIIICar&#45;&gt;IIISel</title>\n",
       "<path fill=\"none\" stroke=\"black\" d=\"M169.63,-108.3C169.63,-116.02 169.63,-125.29 169.63,-133.89\"/>\n",
       "<polygon fill=\"black\" stroke=\"black\" points=\"166.14,-133.9 169.63,-143.9 173.14,-133.9 166.14,-133.9\"/>\n",
       "</g>\n",
       "<!-- IIIILRel -->\n",
       "<g id=\"node6\" class=\"node\">\n",
       "<title>IIIILRel</title>\n",
       "<ellipse fill=\"none\" stroke=\"black\" cx=\"105.63\" cy=\"-18\" rx=\"41.69\" ry=\"18\"/>\n",
       "<text text-anchor=\"middle\" x=\"105.63\" y=\"-14.3\" font-family=\"Times,serif\" font-size=\"14.00\">directors</text>\n",
       "</g>\n",
       "<!-- IIIILRel&#45;&gt;IIIICar -->\n",
       "<g id=\"edge1\" class=\"edge\">\n",
       "<title>IIIILRel&#45;&gt;IIIICar</title>\n",
       "<path fill=\"none\" stroke=\"black\" d=\"M120.16,-34.88C128.74,-44.27 139.74,-56.3 149.19,-66.64\"/>\n",
       "<polygon fill=\"black\" stroke=\"black\" points=\"146.71,-69.12 156.05,-74.14 151.88,-64.39 146.71,-69.12\"/>\n",
       "</g>\n",
       "<!-- IIIIRRel -->\n",
       "<g id=\"node7\" class=\"node\">\n",
       "<title>IIIIRRel</title>\n",
       "<ellipse fill=\"none\" stroke=\"black\" cx=\"233.63\" cy=\"-18\" rx=\"68.79\" ry=\"18\"/>\n",
       "<text text-anchor=\"middle\" x=\"233.63\" y=\"-14.3\" font-family=\"Times,serif\" font-size=\"14.00\">directors_genres</text>\n",
       "</g>\n",
       "<!-- IIIIRRel&#45;&gt;IIIICar -->\n",
       "<g id=\"edge2\" class=\"edge\">\n",
       "<title>IIIIRRel&#45;&gt;IIIICar</title>\n",
       "<path fill=\"none\" stroke=\"black\" d=\"M218.47,-35.59C210.07,-44.78 199.5,-56.33 190.35,-66.34\"/>\n",
       "<polygon fill=\"black\" stroke=\"black\" points=\"187.55,-64.22 183.38,-73.96 192.72,-68.94 187.55,-64.22\"/>\n",
       "</g>\n",
       "</g>\n",
       "</svg>\n"
      ],
      "text/plain": [
       "<graphviz.dot.Digraph at 0x125136a90>"
      ]
     },
     "execution_count": 5,
     "metadata": {},
     "output_type": "execute_result"
    }
   ],
   "source": [
    "# Unoptimized plan\n",
    "cp = Cartesian_Product(directors, directors_genres)\n",
    "sel1 = Selection(cp, 'id == director_id')\n",
    "sel2 = Selection(sel1, 'last_name == \\'Tarantino\\' and prob < 0.7')\n",
    "sel3 = Selection(sel2, 'genre == \\'Mystery\\' or prob >= 0.3')\n",
    "proj = Projection(sel3, 'last_name, prob')\n",
    "\n",
    "graph = proj.get_graph()\n",
    "graph"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "### Optimization 1: Break up 'and' selections\n",
    "\n",
    "Replace every conjunction, i.e. selection of the form (A and B and C), with a chain of individual selections of the form (A), (B), (C). This optimization enables a fine-granular selection pushdown (Optimization 2)."
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 6,
   "metadata": {},
   "outputs": [
    {
     "data": {
      "image/svg+xml": [
       "<?xml version=\"1.0\" encoding=\"UTF-8\" standalone=\"no\"?>\n",
       "<!DOCTYPE svg PUBLIC \"-//W3C//DTD SVG 1.1//EN\"\n",
       " \"http://www.w3.org/Graphics/SVG/1.1/DTD/svg11.dtd\">\n",
       "<!-- Generated by graphviz version 2.47.2 (20210527.0053)\n",
       " -->\n",
       "<!-- Pages: 1 -->\n",
       "<svg width=\"347pt\" height=\"404pt\"\n",
       " viewBox=\"0.00 0.00 347.27 404.00\" xmlns=\"http://www.w3.org/2000/svg\" xmlns:xlink=\"http://www.w3.org/1999/xlink\">\n",
       "<g id=\"graph0\" class=\"graph\" transform=\"scale(1 1) rotate(0) translate(4 400)\">\n",
       "<polygon fill=\"white\" stroke=\"transparent\" points=\"-4,4 -4,-400 343.27,-400 343.27,4 -4,4\"/>\n",
       "<!-- Pro -->\n",
       "<g id=\"node1\" class=\"node\">\n",
       "<title>Pro</title>\n",
       "<ellipse fill=\"#76d6ff\" stroke=\"#76d6ff\" cx=\"169.63\" cy=\"-378\" rx=\"83.39\" ry=\"18\"/>\n",
       "<text text-anchor=\"middle\" x=\"169.63\" y=\"-374.3\" font-family=\"Times,serif\" font-size=\"14.00\">π_[last_name, prob]</text>\n",
       "</g>\n",
       "<!-- ISel -->\n",
       "<g id=\"node2\" class=\"node\">\n",
       "<title>ISel</title>\n",
       "<ellipse fill=\"#ffd479\" stroke=\"#ffd479\" cx=\"169.63\" cy=\"-306\" rx=\"148.67\" ry=\"18\"/>\n",
       "<text text-anchor=\"middle\" x=\"169.63\" y=\"-302.3\" font-family=\"Times,serif\" font-size=\"14.00\">σ_[genre == &#39;Mystery&#39; or prob &gt;= 0.3]</text>\n",
       "</g>\n",
       "<!-- ISel&#45;&gt;Pro -->\n",
       "<g id=\"edge6\" class=\"edge\">\n",
       "<title>ISel&#45;&gt;Pro</title>\n",
       "<path fill=\"none\" stroke=\"black\" d=\"M169.63,-324.3C169.63,-332.02 169.63,-341.29 169.63,-349.89\"/>\n",
       "<polygon fill=\"black\" stroke=\"black\" points=\"166.14,-349.9 169.63,-359.9 173.14,-349.9 166.14,-349.9\"/>\n",
       "</g>\n",
       "<!-- IISel -->\n",
       "<g id=\"node3\" class=\"node\">\n",
       "<title>IISel</title>\n",
       "<ellipse fill=\"#ffd479\" stroke=\"#ffd479\" cx=\"169.63\" cy=\"-234\" rx=\"169.77\" ry=\"18\"/>\n",
       "<text text-anchor=\"middle\" x=\"169.63\" y=\"-230.3\" font-family=\"Times,serif\" font-size=\"14.00\">σ_[last_name == &#39;Tarantino&#39; and prob &lt; 0.7]</text>\n",
       "</g>\n",
       "<!-- IISel&#45;&gt;ISel -->\n",
       "<g id=\"edge5\" class=\"edge\">\n",
       "<title>IISel&#45;&gt;ISel</title>\n",
       "<path fill=\"none\" stroke=\"black\" d=\"M169.63,-252.3C169.63,-260.02 169.63,-269.29 169.63,-277.89\"/>\n",
       "<polygon fill=\"black\" stroke=\"black\" points=\"166.14,-277.9 169.63,-287.9 173.14,-277.9 166.14,-277.9\"/>\n",
       "</g>\n",
       "<!-- IIISel -->\n",
       "<g id=\"node4\" class=\"node\">\n",
       "<title>IIISel</title>\n",
       "<ellipse fill=\"#ffd479\" stroke=\"#ffd479\" cx=\"169.63\" cy=\"-162\" rx=\"87.18\" ry=\"18\"/>\n",
       "<text text-anchor=\"middle\" x=\"169.63\" y=\"-158.3\" font-family=\"Times,serif\" font-size=\"14.00\">σ_[id == director_id]</text>\n",
       "</g>\n",
       "<!-- IIISel&#45;&gt;IISel -->\n",
       "<g id=\"edge4\" class=\"edge\">\n",
       "<title>IIISel&#45;&gt;IISel</title>\n",
       "<path fill=\"none\" stroke=\"black\" d=\"M169.63,-180.3C169.63,-188.02 169.63,-197.29 169.63,-205.89\"/>\n",
       "<polygon fill=\"black\" stroke=\"black\" points=\"166.14,-205.9 169.63,-215.9 173.14,-205.9 166.14,-205.9\"/>\n",
       "</g>\n",
       "<!-- IIIICar -->\n",
       "<g id=\"node5\" class=\"node\">\n",
       "<title>IIIICar</title>\n",
       "<ellipse fill=\"#d4fb79\" stroke=\"#d4fb79\" cx=\"169.63\" cy=\"-90\" rx=\"27\" ry=\"18\"/>\n",
       "<text text-anchor=\"middle\" x=\"169.63\" y=\"-86.3\" font-family=\"Times,serif\" font-size=\"14.00\">×</text>\n",
       "</g>\n",
       "<!-- IIIICar&#45;&gt;IIISel -->\n",
       "<g id=\"edge3\" class=\"edge\">\n",
       "<title>IIIICar&#45;&gt;IIISel</title>\n",
       "<path fill=\"none\" stroke=\"black\" d=\"M169.63,-108.3C169.63,-116.02 169.63,-125.29 169.63,-133.89\"/>\n",
       "<polygon fill=\"black\" stroke=\"black\" points=\"166.14,-133.9 169.63,-143.9 173.14,-133.9 166.14,-133.9\"/>\n",
       "</g>\n",
       "<!-- IIIILRel -->\n",
       "<g id=\"node6\" class=\"node\">\n",
       "<title>IIIILRel</title>\n",
       "<ellipse fill=\"none\" stroke=\"black\" cx=\"105.63\" cy=\"-18\" rx=\"41.69\" ry=\"18\"/>\n",
       "<text text-anchor=\"middle\" x=\"105.63\" y=\"-14.3\" font-family=\"Times,serif\" font-size=\"14.00\">directors</text>\n",
       "</g>\n",
       "<!-- IIIILRel&#45;&gt;IIIICar -->\n",
       "<g id=\"edge1\" class=\"edge\">\n",
       "<title>IIIILRel&#45;&gt;IIIICar</title>\n",
       "<path fill=\"none\" stroke=\"black\" d=\"M120.16,-34.88C128.74,-44.27 139.74,-56.3 149.19,-66.64\"/>\n",
       "<polygon fill=\"black\" stroke=\"black\" points=\"146.71,-69.12 156.05,-74.14 151.88,-64.39 146.71,-69.12\"/>\n",
       "</g>\n",
       "<!-- IIIIRRel -->\n",
       "<g id=\"node7\" class=\"node\">\n",
       "<title>IIIIRRel</title>\n",
       "<ellipse fill=\"none\" stroke=\"black\" cx=\"233.63\" cy=\"-18\" rx=\"68.79\" ry=\"18\"/>\n",
       "<text text-anchor=\"middle\" x=\"233.63\" y=\"-14.3\" font-family=\"Times,serif\" font-size=\"14.00\">directors_genres</text>\n",
       "</g>\n",
       "<!-- IIIIRRel&#45;&gt;IIIICar -->\n",
       "<g id=\"edge2\" class=\"edge\">\n",
       "<title>IIIIRRel&#45;&gt;IIIICar</title>\n",
       "<path fill=\"none\" stroke=\"black\" d=\"M218.47,-35.59C210.07,-44.78 199.5,-56.33 190.35,-66.34\"/>\n",
       "<polygon fill=\"black\" stroke=\"black\" points=\"187.55,-64.22 183.38,-73.96 192.72,-68.94 187.55,-64.22\"/>\n",
       "</g>\n",
       "</g>\n",
       "</svg>\n"
      ],
      "text/plain": [
       "<graphviz.dot.Digraph at 0x125126310>"
      ]
     },
     "execution_count": 6,
     "metadata": {},
     "output_type": "execute_result"
    }
   ],
   "source": [
    "# before optimization\n",
    "graph = proj.get_graph()\n",
    "graph"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 7,
   "metadata": {},
   "outputs": [
    {
     "data": {
      "image/svg+xml": [
       "<?xml version=\"1.0\" encoding=\"UTF-8\" standalone=\"no\"?>\n",
       "<!DOCTYPE svg PUBLIC \"-//W3C//DTD SVG 1.1//EN\"\n",
       " \"http://www.w3.org/Graphics/SVG/1.1/DTD/svg11.dtd\">\n",
       "<!-- Generated by graphviz version 2.47.2 (20210527.0053)\n",
       " -->\n",
       "<!-- Pages: 1 -->\n",
       "<svg width=\"306pt\" height=\"476pt\"\n",
       " viewBox=\"0.00 0.00 305.67 476.00\" xmlns=\"http://www.w3.org/2000/svg\" xmlns:xlink=\"http://www.w3.org/1999/xlink\">\n",
       "<g id=\"graph0\" class=\"graph\" transform=\"scale(1 1) rotate(0) translate(4 472)\">\n",
       "<polygon fill=\"white\" stroke=\"transparent\" points=\"-4,4 -4,-472 301.67,-472 301.67,4 -4,4\"/>\n",
       "<!-- Pro -->\n",
       "<g id=\"node1\" class=\"node\">\n",
       "<title>Pro</title>\n",
       "<ellipse fill=\"#76d6ff\" stroke=\"#76d6ff\" cx=\"148.84\" cy=\"-450\" rx=\"83.39\" ry=\"18\"/>\n",
       "<text text-anchor=\"middle\" x=\"148.84\" y=\"-446.3\" font-family=\"Times,serif\" font-size=\"14.00\">π_[last_name, prob]</text>\n",
       "</g>\n",
       "<!-- ISel -->\n",
       "<g id=\"node2\" class=\"node\">\n",
       "<title>ISel</title>\n",
       "<ellipse fill=\"#ffd479\" stroke=\"#ffd479\" cx=\"148.84\" cy=\"-378\" rx=\"148.67\" ry=\"18\"/>\n",
       "<text text-anchor=\"middle\" x=\"148.84\" y=\"-374.3\" font-family=\"Times,serif\" font-size=\"14.00\">σ_[genre == &#39;Mystery&#39; or prob &gt;= 0.3]</text>\n",
       "</g>\n",
       "<!-- ISel&#45;&gt;Pro -->\n",
       "<g id=\"edge7\" class=\"edge\">\n",
       "<title>ISel&#45;&gt;Pro</title>\n",
       "<path fill=\"none\" stroke=\"black\" d=\"M148.84,-396.3C148.84,-404.02 148.84,-413.29 148.84,-421.89\"/>\n",
       "<polygon fill=\"black\" stroke=\"black\" points=\"145.34,-421.9 148.84,-431.9 152.34,-421.9 145.34,-421.9\"/>\n",
       "</g>\n",
       "<!-- IISel -->\n",
       "<g id=\"node3\" class=\"node\">\n",
       "<title>IISel</title>\n",
       "<ellipse fill=\"#ffd479\" stroke=\"#ffd479\" cx=\"148.84\" cy=\"-306\" rx=\"63.89\" ry=\"18\"/>\n",
       "<text text-anchor=\"middle\" x=\"148.84\" y=\"-302.3\" font-family=\"Times,serif\" font-size=\"14.00\">σ_[prob &lt; 0.7]</text>\n",
       "</g>\n",
       "<!-- IISel&#45;&gt;ISel -->\n",
       "<g id=\"edge6\" class=\"edge\">\n",
       "<title>IISel&#45;&gt;ISel</title>\n",
       "<path fill=\"none\" stroke=\"black\" d=\"M148.84,-324.3C148.84,-332.02 148.84,-341.29 148.84,-349.89\"/>\n",
       "<polygon fill=\"black\" stroke=\"black\" points=\"145.34,-349.9 148.84,-359.9 152.34,-349.9 145.34,-349.9\"/>\n",
       "</g>\n",
       "<!-- IIISel -->\n",
       "<g id=\"node4\" class=\"node\">\n",
       "<title>IIISel</title>\n",
       "<ellipse fill=\"#ffd479\" stroke=\"#ffd479\" cx=\"148.84\" cy=\"-234\" rx=\"114.28\" ry=\"18\"/>\n",
       "<text text-anchor=\"middle\" x=\"148.84\" y=\"-230.3\" font-family=\"Times,serif\" font-size=\"14.00\">σ_[last_name == &#39;Tarantino&#39;]</text>\n",
       "</g>\n",
       "<!-- IIISel&#45;&gt;IISel -->\n",
       "<g id=\"edge5\" class=\"edge\">\n",
       "<title>IIISel&#45;&gt;IISel</title>\n",
       "<path fill=\"none\" stroke=\"black\" d=\"M148.84,-252.3C148.84,-260.02 148.84,-269.29 148.84,-277.89\"/>\n",
       "<polygon fill=\"black\" stroke=\"black\" points=\"145.34,-277.9 148.84,-287.9 152.34,-277.9 145.34,-277.9\"/>\n",
       "</g>\n",
       "<!-- IIIISel -->\n",
       "<g id=\"node5\" class=\"node\">\n",
       "<title>IIIISel</title>\n",
       "<ellipse fill=\"#ffd479\" stroke=\"#ffd479\" cx=\"148.84\" cy=\"-162\" rx=\"87.18\" ry=\"18\"/>\n",
       "<text text-anchor=\"middle\" x=\"148.84\" y=\"-158.3\" font-family=\"Times,serif\" font-size=\"14.00\">σ_[id == director_id]</text>\n",
       "</g>\n",
       "<!-- IIIISel&#45;&gt;IIISel -->\n",
       "<g id=\"edge4\" class=\"edge\">\n",
       "<title>IIIISel&#45;&gt;IIISel</title>\n",
       "<path fill=\"none\" stroke=\"black\" d=\"M148.84,-180.3C148.84,-188.02 148.84,-197.29 148.84,-205.89\"/>\n",
       "<polygon fill=\"black\" stroke=\"black\" points=\"145.34,-205.9 148.84,-215.9 152.34,-205.9 145.34,-205.9\"/>\n",
       "</g>\n",
       "<!-- IIIIICar -->\n",
       "<g id=\"node6\" class=\"node\">\n",
       "<title>IIIIICar</title>\n",
       "<ellipse fill=\"#d4fb79\" stroke=\"#d4fb79\" cx=\"148.84\" cy=\"-90\" rx=\"27\" ry=\"18\"/>\n",
       "<text text-anchor=\"middle\" x=\"148.84\" y=\"-86.3\" font-family=\"Times,serif\" font-size=\"14.00\">×</text>\n",
       "</g>\n",
       "<!-- IIIIICar&#45;&gt;IIIISel -->\n",
       "<g id=\"edge3\" class=\"edge\">\n",
       "<title>IIIIICar&#45;&gt;IIIISel</title>\n",
       "<path fill=\"none\" stroke=\"black\" d=\"M148.84,-108.3C148.84,-116.02 148.84,-125.29 148.84,-133.89\"/>\n",
       "<polygon fill=\"black\" stroke=\"black\" points=\"145.34,-133.9 148.84,-143.9 152.34,-133.9 145.34,-133.9\"/>\n",
       "</g>\n",
       "<!-- IIIIILRel -->\n",
       "<g id=\"node7\" class=\"node\">\n",
       "<title>IIIIILRel</title>\n",
       "<ellipse fill=\"none\" stroke=\"black\" cx=\"84.84\" cy=\"-18\" rx=\"41.69\" ry=\"18\"/>\n",
       "<text text-anchor=\"middle\" x=\"84.84\" y=\"-14.3\" font-family=\"Times,serif\" font-size=\"14.00\">directors</text>\n",
       "</g>\n",
       "<!-- IIIIILRel&#45;&gt;IIIIICar -->\n",
       "<g id=\"edge1\" class=\"edge\">\n",
       "<title>IIIIILRel&#45;&gt;IIIIICar</title>\n",
       "<path fill=\"none\" stroke=\"black\" d=\"M99.36,-34.88C107.94,-44.27 118.94,-56.3 128.39,-66.64\"/>\n",
       "<polygon fill=\"black\" stroke=\"black\" points=\"125.92,-69.12 135.25,-74.14 131.08,-64.39 125.92,-69.12\"/>\n",
       "</g>\n",
       "<!-- IIIIIRRel -->\n",
       "<g id=\"node8\" class=\"node\">\n",
       "<title>IIIIIRRel</title>\n",
       "<ellipse fill=\"none\" stroke=\"black\" cx=\"212.84\" cy=\"-18\" rx=\"68.79\" ry=\"18\"/>\n",
       "<text text-anchor=\"middle\" x=\"212.84\" y=\"-14.3\" font-family=\"Times,serif\" font-size=\"14.00\">directors_genres</text>\n",
       "</g>\n",
       "<!-- IIIIIRRel&#45;&gt;IIIIICar -->\n",
       "<g id=\"edge2\" class=\"edge\">\n",
       "<title>IIIIIRRel&#45;&gt;IIIIICar</title>\n",
       "<path fill=\"none\" stroke=\"black\" d=\"M197.67,-35.59C189.27,-44.78 178.71,-56.33 169.55,-66.34\"/>\n",
       "<polygon fill=\"black\" stroke=\"black\" points=\"166.75,-64.22 162.59,-73.96 171.92,-68.94 166.75,-64.22\"/>\n",
       "</g>\n",
       "</g>\n",
       "</svg>\n"
      ],
      "text/plain": [
       "<graphviz.dot.Digraph at 0x1251369d0>"
      ]
     },
     "execution_count": 7,
     "metadata": {},
     "output_type": "execute_result"
    }
   ],
   "source": [
    "bus = BreakUpSelections(proj) \n",
    "bus.optimize(proj)\n",
    "\n",
    "# after optimization\n",
    "graph = bus.root.get_graph()\n",
    "graph"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "### Optimization 2: Push down selections"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Push down every selection as far as possible in the operator tree. This assures the early elimination of tuples. We assume that optimization 1 has been applied already."
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 8,
   "metadata": {},
   "outputs": [
    {
     "data": {
      "image/svg+xml": [
       "<?xml version=\"1.0\" encoding=\"UTF-8\" standalone=\"no\"?>\n",
       "<!DOCTYPE svg PUBLIC \"-//W3C//DTD SVG 1.1//EN\"\n",
       " \"http://www.w3.org/Graphics/SVG/1.1/DTD/svg11.dtd\">\n",
       "<!-- Generated by graphviz version 2.47.2 (20210527.0053)\n",
       " -->\n",
       "<!-- Pages: 1 -->\n",
       "<svg width=\"306pt\" height=\"476pt\"\n",
       " viewBox=\"0.00 0.00 305.67 476.00\" xmlns=\"http://www.w3.org/2000/svg\" xmlns:xlink=\"http://www.w3.org/1999/xlink\">\n",
       "<g id=\"graph0\" class=\"graph\" transform=\"scale(1 1) rotate(0) translate(4 472)\">\n",
       "<polygon fill=\"white\" stroke=\"transparent\" points=\"-4,4 -4,-472 301.67,-472 301.67,4 -4,4\"/>\n",
       "<!-- Pro -->\n",
       "<g id=\"node1\" class=\"node\">\n",
       "<title>Pro</title>\n",
       "<ellipse fill=\"#76d6ff\" stroke=\"#76d6ff\" cx=\"148.84\" cy=\"-450\" rx=\"83.39\" ry=\"18\"/>\n",
       "<text text-anchor=\"middle\" x=\"148.84\" y=\"-446.3\" font-family=\"Times,serif\" font-size=\"14.00\">π_[last_name, prob]</text>\n",
       "</g>\n",
       "<!-- ISel -->\n",
       "<g id=\"node2\" class=\"node\">\n",
       "<title>ISel</title>\n",
       "<ellipse fill=\"#ffd479\" stroke=\"#ffd479\" cx=\"148.84\" cy=\"-378\" rx=\"148.67\" ry=\"18\"/>\n",
       "<text text-anchor=\"middle\" x=\"148.84\" y=\"-374.3\" font-family=\"Times,serif\" font-size=\"14.00\">σ_[genre == &#39;Mystery&#39; or prob &gt;= 0.3]</text>\n",
       "</g>\n",
       "<!-- ISel&#45;&gt;Pro -->\n",
       "<g id=\"edge7\" class=\"edge\">\n",
       "<title>ISel&#45;&gt;Pro</title>\n",
       "<path fill=\"none\" stroke=\"black\" d=\"M148.84,-396.3C148.84,-404.02 148.84,-413.29 148.84,-421.89\"/>\n",
       "<polygon fill=\"black\" stroke=\"black\" points=\"145.34,-421.9 148.84,-431.9 152.34,-421.9 145.34,-421.9\"/>\n",
       "</g>\n",
       "<!-- IISel -->\n",
       "<g id=\"node3\" class=\"node\">\n",
       "<title>IISel</title>\n",
       "<ellipse fill=\"#ffd479\" stroke=\"#ffd479\" cx=\"148.84\" cy=\"-306\" rx=\"63.89\" ry=\"18\"/>\n",
       "<text text-anchor=\"middle\" x=\"148.84\" y=\"-302.3\" font-family=\"Times,serif\" font-size=\"14.00\">σ_[prob &lt; 0.7]</text>\n",
       "</g>\n",
       "<!-- IISel&#45;&gt;ISel -->\n",
       "<g id=\"edge6\" class=\"edge\">\n",
       "<title>IISel&#45;&gt;ISel</title>\n",
       "<path fill=\"none\" stroke=\"black\" d=\"M148.84,-324.3C148.84,-332.02 148.84,-341.29 148.84,-349.89\"/>\n",
       "<polygon fill=\"black\" stroke=\"black\" points=\"145.34,-349.9 148.84,-359.9 152.34,-349.9 145.34,-349.9\"/>\n",
       "</g>\n",
       "<!-- IIISel -->\n",
       "<g id=\"node4\" class=\"node\">\n",
       "<title>IIISel</title>\n",
       "<ellipse fill=\"#ffd479\" stroke=\"#ffd479\" cx=\"148.84\" cy=\"-234\" rx=\"114.28\" ry=\"18\"/>\n",
       "<text text-anchor=\"middle\" x=\"148.84\" y=\"-230.3\" font-family=\"Times,serif\" font-size=\"14.00\">σ_[last_name == &#39;Tarantino&#39;]</text>\n",
       "</g>\n",
       "<!-- IIISel&#45;&gt;IISel -->\n",
       "<g id=\"edge5\" class=\"edge\">\n",
       "<title>IIISel&#45;&gt;IISel</title>\n",
       "<path fill=\"none\" stroke=\"black\" d=\"M148.84,-252.3C148.84,-260.02 148.84,-269.29 148.84,-277.89\"/>\n",
       "<polygon fill=\"black\" stroke=\"black\" points=\"145.34,-277.9 148.84,-287.9 152.34,-277.9 145.34,-277.9\"/>\n",
       "</g>\n",
       "<!-- IIIISel -->\n",
       "<g id=\"node5\" class=\"node\">\n",
       "<title>IIIISel</title>\n",
       "<ellipse fill=\"#ffd479\" stroke=\"#ffd479\" cx=\"148.84\" cy=\"-162\" rx=\"87.18\" ry=\"18\"/>\n",
       "<text text-anchor=\"middle\" x=\"148.84\" y=\"-158.3\" font-family=\"Times,serif\" font-size=\"14.00\">σ_[id == director_id]</text>\n",
       "</g>\n",
       "<!-- IIIISel&#45;&gt;IIISel -->\n",
       "<g id=\"edge4\" class=\"edge\">\n",
       "<title>IIIISel&#45;&gt;IIISel</title>\n",
       "<path fill=\"none\" stroke=\"black\" d=\"M148.84,-180.3C148.84,-188.02 148.84,-197.29 148.84,-205.89\"/>\n",
       "<polygon fill=\"black\" stroke=\"black\" points=\"145.34,-205.9 148.84,-215.9 152.34,-205.9 145.34,-205.9\"/>\n",
       "</g>\n",
       "<!-- IIIIICar -->\n",
       "<g id=\"node6\" class=\"node\">\n",
       "<title>IIIIICar</title>\n",
       "<ellipse fill=\"#d4fb79\" stroke=\"#d4fb79\" cx=\"148.84\" cy=\"-90\" rx=\"27\" ry=\"18\"/>\n",
       "<text text-anchor=\"middle\" x=\"148.84\" y=\"-86.3\" font-family=\"Times,serif\" font-size=\"14.00\">×</text>\n",
       "</g>\n",
       "<!-- IIIIICar&#45;&gt;IIIISel -->\n",
       "<g id=\"edge3\" class=\"edge\">\n",
       "<title>IIIIICar&#45;&gt;IIIISel</title>\n",
       "<path fill=\"none\" stroke=\"black\" d=\"M148.84,-108.3C148.84,-116.02 148.84,-125.29 148.84,-133.89\"/>\n",
       "<polygon fill=\"black\" stroke=\"black\" points=\"145.34,-133.9 148.84,-143.9 152.34,-133.9 145.34,-133.9\"/>\n",
       "</g>\n",
       "<!-- IIIIILRel -->\n",
       "<g id=\"node7\" class=\"node\">\n",
       "<title>IIIIILRel</title>\n",
       "<ellipse fill=\"none\" stroke=\"black\" cx=\"84.84\" cy=\"-18\" rx=\"41.69\" ry=\"18\"/>\n",
       "<text text-anchor=\"middle\" x=\"84.84\" y=\"-14.3\" font-family=\"Times,serif\" font-size=\"14.00\">directors</text>\n",
       "</g>\n",
       "<!-- IIIIILRel&#45;&gt;IIIIICar -->\n",
       "<g id=\"edge1\" class=\"edge\">\n",
       "<title>IIIIILRel&#45;&gt;IIIIICar</title>\n",
       "<path fill=\"none\" stroke=\"black\" d=\"M99.36,-34.88C107.94,-44.27 118.94,-56.3 128.39,-66.64\"/>\n",
       "<polygon fill=\"black\" stroke=\"black\" points=\"125.92,-69.12 135.25,-74.14 131.08,-64.39 125.92,-69.12\"/>\n",
       "</g>\n",
       "<!-- IIIIIRRel -->\n",
       "<g id=\"node8\" class=\"node\">\n",
       "<title>IIIIIRRel</title>\n",
       "<ellipse fill=\"none\" stroke=\"black\" cx=\"212.84\" cy=\"-18\" rx=\"68.79\" ry=\"18\"/>\n",
       "<text text-anchor=\"middle\" x=\"212.84\" y=\"-14.3\" font-family=\"Times,serif\" font-size=\"14.00\">directors_genres</text>\n",
       "</g>\n",
       "<!-- IIIIIRRel&#45;&gt;IIIIICar -->\n",
       "<g id=\"edge2\" class=\"edge\">\n",
       "<title>IIIIIRRel&#45;&gt;IIIIICar</title>\n",
       "<path fill=\"none\" stroke=\"black\" d=\"M197.67,-35.59C189.27,-44.78 178.71,-56.33 169.55,-66.34\"/>\n",
       "<polygon fill=\"black\" stroke=\"black\" points=\"166.75,-64.22 162.59,-73.96 171.92,-68.94 166.75,-64.22\"/>\n",
       "</g>\n",
       "</g>\n",
       "</svg>\n"
      ],
      "text/plain": [
       "<graphviz.dot.Digraph at 0x125126d90>"
      ]
     },
     "execution_count": 8,
     "metadata": {},
     "output_type": "execute_result"
    }
   ],
   "source": [
    "# before optimization\n",
    "graph = bus.root.get_graph()\n",
    "graph"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 9,
   "metadata": {},
   "outputs": [
    {
     "data": {
      "image/svg+xml": [
       "<?xml version=\"1.0\" encoding=\"UTF-8\" standalone=\"no\"?>\n",
       "<!DOCTYPE svg PUBLIC \"-//W3C//DTD SVG 1.1//EN\"\n",
       " \"http://www.w3.org/Graphics/SVG/1.1/DTD/svg11.dtd\">\n",
       "<!-- Generated by graphviz version 2.47.2 (20210527.0053)\n",
       " -->\n",
       "<!-- Pages: 1 -->\n",
       "<svg width=\"552pt\" height=\"404pt\"\n",
       " viewBox=\"0.00 0.00 552.23 404.00\" xmlns=\"http://www.w3.org/2000/svg\" xmlns:xlink=\"http://www.w3.org/1999/xlink\">\n",
       "<g id=\"graph0\" class=\"graph\" transform=\"scale(1 1) rotate(0) translate(4 400)\">\n",
       "<polygon fill=\"white\" stroke=\"transparent\" points=\"-4,4 -4,-400 548.23,-400 548.23,4 -4,4\"/>\n",
       "<!-- Pro -->\n",
       "<g id=\"node1\" class=\"node\">\n",
       "<title>Pro</title>\n",
       "<ellipse fill=\"#76d6ff\" stroke=\"#76d6ff\" cx=\"254.39\" cy=\"-378\" rx=\"83.39\" ry=\"18\"/>\n",
       "<text text-anchor=\"middle\" x=\"254.39\" y=\"-374.3\" font-family=\"Times,serif\" font-size=\"14.00\">π_[last_name, prob]</text>\n",
       "</g>\n",
       "<!-- ISel -->\n",
       "<g id=\"node2\" class=\"node\">\n",
       "<title>ISel</title>\n",
       "<ellipse fill=\"#ffd479\" stroke=\"#ffd479\" cx=\"254.39\" cy=\"-306\" rx=\"87.18\" ry=\"18\"/>\n",
       "<text text-anchor=\"middle\" x=\"254.39\" y=\"-302.3\" font-family=\"Times,serif\" font-size=\"14.00\">σ_[id == director_id]</text>\n",
       "</g>\n",
       "<!-- ISel&#45;&gt;Pro -->\n",
       "<g id=\"edge7\" class=\"edge\">\n",
       "<title>ISel&#45;&gt;Pro</title>\n",
       "<path fill=\"none\" stroke=\"black\" d=\"M254.39,-324.3C254.39,-332.02 254.39,-341.29 254.39,-349.89\"/>\n",
       "<polygon fill=\"black\" stroke=\"black\" points=\"250.89,-349.9 254.39,-359.9 257.89,-349.9 250.89,-349.9\"/>\n",
       "</g>\n",
       "<!-- IICar -->\n",
       "<g id=\"node3\" class=\"node\">\n",
       "<title>IICar</title>\n",
       "<ellipse fill=\"#d4fb79\" stroke=\"#d4fb79\" cx=\"254.39\" cy=\"-234\" rx=\"27\" ry=\"18\"/>\n",
       "<text text-anchor=\"middle\" x=\"254.39\" y=\"-230.3\" font-family=\"Times,serif\" font-size=\"14.00\">×</text>\n",
       "</g>\n",
       "<!-- IICar&#45;&gt;ISel -->\n",
       "<g id=\"edge6\" class=\"edge\">\n",
       "<title>IICar&#45;&gt;ISel</title>\n",
       "<path fill=\"none\" stroke=\"black\" d=\"M254.39,-252.3C254.39,-260.02 254.39,-269.29 254.39,-277.89\"/>\n",
       "<polygon fill=\"black\" stroke=\"black\" points=\"250.89,-277.9 254.39,-287.9 257.89,-277.9 250.89,-277.9\"/>\n",
       "</g>\n",
       "<!-- IILSel -->\n",
       "<g id=\"node4\" class=\"node\">\n",
       "<title>IILSel</title>\n",
       "<ellipse fill=\"#ffd479\" stroke=\"#ffd479\" cx=\"114.39\" cy=\"-162\" rx=\"114.28\" ry=\"18\"/>\n",
       "<text text-anchor=\"middle\" x=\"114.39\" y=\"-158.3\" font-family=\"Times,serif\" font-size=\"14.00\">σ_[last_name == &#39;Tarantino&#39;]</text>\n",
       "</g>\n",
       "<!-- IILSel&#45;&gt;IICar -->\n",
       "<g id=\"edge4\" class=\"edge\">\n",
       "<title>IILSel&#45;&gt;IICar</title>\n",
       "<path fill=\"none\" stroke=\"black\" d=\"M147.21,-179.41C170.55,-191.08 201.65,-206.63 224.34,-217.97\"/>\n",
       "<polygon fill=\"black\" stroke=\"black\" points=\"222.99,-221.21 233.5,-222.56 226.12,-214.95 222.99,-221.21\"/>\n",
       "</g>\n",
       "<!-- IILIRel -->\n",
       "<g id=\"node5\" class=\"node\">\n",
       "<title>IILIRel</title>\n",
       "<ellipse fill=\"none\" stroke=\"black\" cx=\"114.39\" cy=\"-90\" rx=\"41.69\" ry=\"18\"/>\n",
       "<text text-anchor=\"middle\" x=\"114.39\" y=\"-86.3\" font-family=\"Times,serif\" font-size=\"14.00\">directors</text>\n",
       "</g>\n",
       "<!-- IILIRel&#45;&gt;IILSel -->\n",
       "<g id=\"edge1\" class=\"edge\">\n",
       "<title>IILIRel&#45;&gt;IILSel</title>\n",
       "<path fill=\"none\" stroke=\"black\" d=\"M114.39,-108.3C114.39,-116.02 114.39,-125.29 114.39,-133.89\"/>\n",
       "<polygon fill=\"black\" stroke=\"black\" points=\"110.89,-133.9 114.39,-143.9 117.89,-133.9 110.89,-133.9\"/>\n",
       "</g>\n",
       "<!-- IIRSel -->\n",
       "<g id=\"node6\" class=\"node\">\n",
       "<title>IIRSel</title>\n",
       "<ellipse fill=\"#ffd479\" stroke=\"#ffd479\" cx=\"395.39\" cy=\"-162\" rx=\"148.67\" ry=\"18\"/>\n",
       "<text text-anchor=\"middle\" x=\"395.39\" y=\"-158.3\" font-family=\"Times,serif\" font-size=\"14.00\">σ_[genre == &#39;Mystery&#39; or prob &gt;= 0.3]</text>\n",
       "</g>\n",
       "<!-- IIRSel&#45;&gt;IICar -->\n",
       "<g id=\"edge5\" class=\"edge\">\n",
       "<title>IIRSel&#45;&gt;IICar</title>\n",
       "<path fill=\"none\" stroke=\"black\" d=\"M361.97,-179.59C338.46,-191.26 307.25,-206.76 284.5,-218.05\"/>\n",
       "<polygon fill=\"black\" stroke=\"black\" points=\"282.72,-215.03 275.32,-222.61 285.83,-221.3 282.72,-215.03\"/>\n",
       "</g>\n",
       "<!-- IIRISel -->\n",
       "<g id=\"node7\" class=\"node\">\n",
       "<title>IIRISel</title>\n",
       "<ellipse fill=\"#ffd479\" stroke=\"#ffd479\" cx=\"395.39\" cy=\"-90\" rx=\"63.89\" ry=\"18\"/>\n",
       "<text text-anchor=\"middle\" x=\"395.39\" y=\"-86.3\" font-family=\"Times,serif\" font-size=\"14.00\">σ_[prob &lt; 0.7]</text>\n",
       "</g>\n",
       "<!-- IIRISel&#45;&gt;IIRSel -->\n",
       "<g id=\"edge3\" class=\"edge\">\n",
       "<title>IIRISel&#45;&gt;IIRSel</title>\n",
       "<path fill=\"none\" stroke=\"black\" d=\"M395.39,-108.3C395.39,-116.02 395.39,-125.29 395.39,-133.89\"/>\n",
       "<polygon fill=\"black\" stroke=\"black\" points=\"391.89,-133.9 395.39,-143.9 398.89,-133.9 391.89,-133.9\"/>\n",
       "</g>\n",
       "<!-- IIRIIRel -->\n",
       "<g id=\"node8\" class=\"node\">\n",
       "<title>IIRIIRel</title>\n",
       "<ellipse fill=\"none\" stroke=\"black\" cx=\"395.39\" cy=\"-18\" rx=\"68.79\" ry=\"18\"/>\n",
       "<text text-anchor=\"middle\" x=\"395.39\" y=\"-14.3\" font-family=\"Times,serif\" font-size=\"14.00\">directors_genres</text>\n",
       "</g>\n",
       "<!-- IIRIIRel&#45;&gt;IIRISel -->\n",
       "<g id=\"edge2\" class=\"edge\">\n",
       "<title>IIRIIRel&#45;&gt;IIRISel</title>\n",
       "<path fill=\"none\" stroke=\"black\" d=\"M395.39,-36.3C395.39,-44.02 395.39,-53.29 395.39,-61.89\"/>\n",
       "<polygon fill=\"black\" stroke=\"black\" points=\"391.89,-61.9 395.39,-71.9 398.89,-61.9 391.89,-61.9\"/>\n",
       "</g>\n",
       "</g>\n",
       "</svg>\n"
      ],
      "text/plain": [
       "<graphviz.dot.Digraph at 0x1251266a0>"
      ]
     },
     "execution_count": 9,
     "metadata": {},
     "output_type": "execute_result"
    }
   ],
   "source": [
    "pds = PushDownSelection(bus.root) \n",
    "pds.optimize(bus.root)\n",
    "\n",
    "# after optimization\n",
    "graph = pds.root.get_graph()\n",
    "graph"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "### Optimization 3: Replace a join-style selection on top of a cartesian product by a theta join "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 10,
   "metadata": {},
   "outputs": [
    {
     "data": {
      "image/svg+xml": [
       "<?xml version=\"1.0\" encoding=\"UTF-8\" standalone=\"no\"?>\n",
       "<!DOCTYPE svg PUBLIC \"-//W3C//DTD SVG 1.1//EN\"\n",
       " \"http://www.w3.org/Graphics/SVG/1.1/DTD/svg11.dtd\">\n",
       "<!-- Generated by graphviz version 2.47.2 (20210527.0053)\n",
       " -->\n",
       "<!-- Pages: 1 -->\n",
       "<svg width=\"552pt\" height=\"404pt\"\n",
       " viewBox=\"0.00 0.00 552.23 404.00\" xmlns=\"http://www.w3.org/2000/svg\" xmlns:xlink=\"http://www.w3.org/1999/xlink\">\n",
       "<g id=\"graph0\" class=\"graph\" transform=\"scale(1 1) rotate(0) translate(4 400)\">\n",
       "<polygon fill=\"white\" stroke=\"transparent\" points=\"-4,4 -4,-400 548.23,-400 548.23,4 -4,4\"/>\n",
       "<!-- Pro -->\n",
       "<g id=\"node1\" class=\"node\">\n",
       "<title>Pro</title>\n",
       "<ellipse fill=\"#76d6ff\" stroke=\"#76d6ff\" cx=\"254.39\" cy=\"-378\" rx=\"83.39\" ry=\"18\"/>\n",
       "<text text-anchor=\"middle\" x=\"254.39\" y=\"-374.3\" font-family=\"Times,serif\" font-size=\"14.00\">π_[last_name, prob]</text>\n",
       "</g>\n",
       "<!-- ISel -->\n",
       "<g id=\"node2\" class=\"node\">\n",
       "<title>ISel</title>\n",
       "<ellipse fill=\"#ffd479\" stroke=\"#ffd479\" cx=\"254.39\" cy=\"-306\" rx=\"87.18\" ry=\"18\"/>\n",
       "<text text-anchor=\"middle\" x=\"254.39\" y=\"-302.3\" font-family=\"Times,serif\" font-size=\"14.00\">σ_[id == director_id]</text>\n",
       "</g>\n",
       "<!-- ISel&#45;&gt;Pro -->\n",
       "<g id=\"edge7\" class=\"edge\">\n",
       "<title>ISel&#45;&gt;Pro</title>\n",
       "<path fill=\"none\" stroke=\"black\" d=\"M254.39,-324.3C254.39,-332.02 254.39,-341.29 254.39,-349.89\"/>\n",
       "<polygon fill=\"black\" stroke=\"black\" points=\"250.89,-349.9 254.39,-359.9 257.89,-349.9 250.89,-349.9\"/>\n",
       "</g>\n",
       "<!-- IICar -->\n",
       "<g id=\"node3\" class=\"node\">\n",
       "<title>IICar</title>\n",
       "<ellipse fill=\"#d4fb79\" stroke=\"#d4fb79\" cx=\"254.39\" cy=\"-234\" rx=\"27\" ry=\"18\"/>\n",
       "<text text-anchor=\"middle\" x=\"254.39\" y=\"-230.3\" font-family=\"Times,serif\" font-size=\"14.00\">×</text>\n",
       "</g>\n",
       "<!-- IICar&#45;&gt;ISel -->\n",
       "<g id=\"edge6\" class=\"edge\">\n",
       "<title>IICar&#45;&gt;ISel</title>\n",
       "<path fill=\"none\" stroke=\"black\" d=\"M254.39,-252.3C254.39,-260.02 254.39,-269.29 254.39,-277.89\"/>\n",
       "<polygon fill=\"black\" stroke=\"black\" points=\"250.89,-277.9 254.39,-287.9 257.89,-277.9 250.89,-277.9\"/>\n",
       "</g>\n",
       "<!-- IILSel -->\n",
       "<g id=\"node4\" class=\"node\">\n",
       "<title>IILSel</title>\n",
       "<ellipse fill=\"#ffd479\" stroke=\"#ffd479\" cx=\"114.39\" cy=\"-162\" rx=\"114.28\" ry=\"18\"/>\n",
       "<text text-anchor=\"middle\" x=\"114.39\" y=\"-158.3\" font-family=\"Times,serif\" font-size=\"14.00\">σ_[last_name == &#39;Tarantino&#39;]</text>\n",
       "</g>\n",
       "<!-- IILSel&#45;&gt;IICar -->\n",
       "<g id=\"edge4\" class=\"edge\">\n",
       "<title>IILSel&#45;&gt;IICar</title>\n",
       "<path fill=\"none\" stroke=\"black\" d=\"M147.21,-179.41C170.55,-191.08 201.65,-206.63 224.34,-217.97\"/>\n",
       "<polygon fill=\"black\" stroke=\"black\" points=\"222.99,-221.21 233.5,-222.56 226.12,-214.95 222.99,-221.21\"/>\n",
       "</g>\n",
       "<!-- IILIRel -->\n",
       "<g id=\"node5\" class=\"node\">\n",
       "<title>IILIRel</title>\n",
       "<ellipse fill=\"none\" stroke=\"black\" cx=\"114.39\" cy=\"-90\" rx=\"41.69\" ry=\"18\"/>\n",
       "<text text-anchor=\"middle\" x=\"114.39\" y=\"-86.3\" font-family=\"Times,serif\" font-size=\"14.00\">directors</text>\n",
       "</g>\n",
       "<!-- IILIRel&#45;&gt;IILSel -->\n",
       "<g id=\"edge1\" class=\"edge\">\n",
       "<title>IILIRel&#45;&gt;IILSel</title>\n",
       "<path fill=\"none\" stroke=\"black\" d=\"M114.39,-108.3C114.39,-116.02 114.39,-125.29 114.39,-133.89\"/>\n",
       "<polygon fill=\"black\" stroke=\"black\" points=\"110.89,-133.9 114.39,-143.9 117.89,-133.9 110.89,-133.9\"/>\n",
       "</g>\n",
       "<!-- IIRSel -->\n",
       "<g id=\"node6\" class=\"node\">\n",
       "<title>IIRSel</title>\n",
       "<ellipse fill=\"#ffd479\" stroke=\"#ffd479\" cx=\"395.39\" cy=\"-162\" rx=\"148.67\" ry=\"18\"/>\n",
       "<text text-anchor=\"middle\" x=\"395.39\" y=\"-158.3\" font-family=\"Times,serif\" font-size=\"14.00\">σ_[genre == &#39;Mystery&#39; or prob &gt;= 0.3]</text>\n",
       "</g>\n",
       "<!-- IIRSel&#45;&gt;IICar -->\n",
       "<g id=\"edge5\" class=\"edge\">\n",
       "<title>IIRSel&#45;&gt;IICar</title>\n",
       "<path fill=\"none\" stroke=\"black\" d=\"M361.97,-179.59C338.46,-191.26 307.25,-206.76 284.5,-218.05\"/>\n",
       "<polygon fill=\"black\" stroke=\"black\" points=\"282.72,-215.03 275.32,-222.61 285.83,-221.3 282.72,-215.03\"/>\n",
       "</g>\n",
       "<!-- IIRISel -->\n",
       "<g id=\"node7\" class=\"node\">\n",
       "<title>IIRISel</title>\n",
       "<ellipse fill=\"#ffd479\" stroke=\"#ffd479\" cx=\"395.39\" cy=\"-90\" rx=\"63.89\" ry=\"18\"/>\n",
       "<text text-anchor=\"middle\" x=\"395.39\" y=\"-86.3\" font-family=\"Times,serif\" font-size=\"14.00\">σ_[prob &lt; 0.7]</text>\n",
       "</g>\n",
       "<!-- IIRISel&#45;&gt;IIRSel -->\n",
       "<g id=\"edge3\" class=\"edge\">\n",
       "<title>IIRISel&#45;&gt;IIRSel</title>\n",
       "<path fill=\"none\" stroke=\"black\" d=\"M395.39,-108.3C395.39,-116.02 395.39,-125.29 395.39,-133.89\"/>\n",
       "<polygon fill=\"black\" stroke=\"black\" points=\"391.89,-133.9 395.39,-143.9 398.89,-133.9 391.89,-133.9\"/>\n",
       "</g>\n",
       "<!-- IIRIIRel -->\n",
       "<g id=\"node8\" class=\"node\">\n",
       "<title>IIRIIRel</title>\n",
       "<ellipse fill=\"none\" stroke=\"black\" cx=\"395.39\" cy=\"-18\" rx=\"68.79\" ry=\"18\"/>\n",
       "<text text-anchor=\"middle\" x=\"395.39\" y=\"-14.3\" font-family=\"Times,serif\" font-size=\"14.00\">directors_genres</text>\n",
       "</g>\n",
       "<!-- IIRIIRel&#45;&gt;IIRISel -->\n",
       "<g id=\"edge2\" class=\"edge\">\n",
       "<title>IIRIIRel&#45;&gt;IIRISel</title>\n",
       "<path fill=\"none\" stroke=\"black\" d=\"M395.39,-36.3C395.39,-44.02 395.39,-53.29 395.39,-61.89\"/>\n",
       "<polygon fill=\"black\" stroke=\"black\" points=\"391.89,-61.9 395.39,-71.9 398.89,-61.9 391.89,-61.9\"/>\n",
       "</g>\n",
       "</g>\n",
       "</svg>\n"
      ],
      "text/plain": [
       "<graphviz.dot.Digraph at 0x125126dc0>"
      ]
     },
     "execution_count": 10,
     "metadata": {},
     "output_type": "execute_result"
    }
   ],
   "source": [
    "# before optimization\n",
    "graph = pds.root.get_graph()\n",
    "graph"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 11,
   "metadata": {},
   "outputs": [
    {
     "data": {
      "image/svg+xml": [
       "<?xml version=\"1.0\" encoding=\"UTF-8\" standalone=\"no\"?>\n",
       "<!DOCTYPE svg PUBLIC \"-//W3C//DTD SVG 1.1//EN\"\n",
       " \"http://www.w3.org/Graphics/SVG/1.1/DTD/svg11.dtd\">\n",
       "<!-- Generated by graphviz version 2.47.2 (20210527.0053)\n",
       " -->\n",
       "<!-- Pages: 1 -->\n",
       "<svg width=\"552pt\" height=\"332pt\"\n",
       " viewBox=\"0.00 0.00 552.23 332.00\" xmlns=\"http://www.w3.org/2000/svg\" xmlns:xlink=\"http://www.w3.org/1999/xlink\">\n",
       "<g id=\"graph0\" class=\"graph\" transform=\"scale(1 1) rotate(0) translate(4 328)\">\n",
       "<polygon fill=\"white\" stroke=\"transparent\" points=\"-4,4 -4,-328 548.23,-328 548.23,4 -4,4\"/>\n",
       "<!-- Pro -->\n",
       "<g id=\"node1\" class=\"node\">\n",
       "<title>Pro</title>\n",
       "<ellipse fill=\"#76d6ff\" stroke=\"#76d6ff\" cx=\"254.39\" cy=\"-306\" rx=\"83.39\" ry=\"18\"/>\n",
       "<text text-anchor=\"middle\" x=\"254.39\" y=\"-302.3\" font-family=\"Times,serif\" font-size=\"14.00\">π_[last_name, prob]</text>\n",
       "</g>\n",
       "<!-- IJoin -->\n",
       "<g id=\"node2\" class=\"node\">\n",
       "<title>IJoin</title>\n",
       "<ellipse fill=\"#fffc79\" stroke=\"#fffc79\" cx=\"254.39\" cy=\"-234\" rx=\"89.08\" ry=\"18\"/>\n",
       "<text text-anchor=\"middle\" x=\"254.39\" y=\"-230.3\" font-family=\"Times,serif\" font-size=\"14.00\">⋈_[id == director_id]</text>\n",
       "</g>\n",
       "<!-- IJoin&#45;&gt;Pro -->\n",
       "<g id=\"edge6\" class=\"edge\">\n",
       "<title>IJoin&#45;&gt;Pro</title>\n",
       "<path fill=\"none\" stroke=\"black\" d=\"M254.39,-252.3C254.39,-260.02 254.39,-269.29 254.39,-277.89\"/>\n",
       "<polygon fill=\"black\" stroke=\"black\" points=\"250.89,-277.9 254.39,-287.9 257.89,-277.9 250.89,-277.9\"/>\n",
       "</g>\n",
       "<!-- ILSel -->\n",
       "<g id=\"node3\" class=\"node\">\n",
       "<title>ILSel</title>\n",
       "<ellipse fill=\"#ffd479\" stroke=\"#ffd479\" cx=\"114.39\" cy=\"-162\" rx=\"114.28\" ry=\"18\"/>\n",
       "<text text-anchor=\"middle\" x=\"114.39\" y=\"-158.3\" font-family=\"Times,serif\" font-size=\"14.00\">σ_[last_name == &#39;Tarantino&#39;]</text>\n",
       "</g>\n",
       "<!-- ILSel&#45;&gt;IJoin -->\n",
       "<g id=\"edge4\" class=\"edge\">\n",
       "<title>ILSel&#45;&gt;IJoin</title>\n",
       "<path fill=\"none\" stroke=\"black\" d=\"M147.21,-179.41C167.07,-189.34 192.54,-202.08 213.67,-212.64\"/>\n",
       "<polygon fill=\"black\" stroke=\"black\" points=\"212.23,-215.83 222.74,-217.17 215.36,-209.57 212.23,-215.83\"/>\n",
       "</g>\n",
       "<!-- ILIRel -->\n",
       "<g id=\"node4\" class=\"node\">\n",
       "<title>ILIRel</title>\n",
       "<ellipse fill=\"none\" stroke=\"black\" cx=\"114.39\" cy=\"-90\" rx=\"41.69\" ry=\"18\"/>\n",
       "<text text-anchor=\"middle\" x=\"114.39\" y=\"-86.3\" font-family=\"Times,serif\" font-size=\"14.00\">directors</text>\n",
       "</g>\n",
       "<!-- ILIRel&#45;&gt;ILSel -->\n",
       "<g id=\"edge1\" class=\"edge\">\n",
       "<title>ILIRel&#45;&gt;ILSel</title>\n",
       "<path fill=\"none\" stroke=\"black\" d=\"M114.39,-108.3C114.39,-116.02 114.39,-125.29 114.39,-133.89\"/>\n",
       "<polygon fill=\"black\" stroke=\"black\" points=\"110.89,-133.9 114.39,-143.9 117.89,-133.9 110.89,-133.9\"/>\n",
       "</g>\n",
       "<!-- IRSel -->\n",
       "<g id=\"node5\" class=\"node\">\n",
       "<title>IRSel</title>\n",
       "<ellipse fill=\"#ffd479\" stroke=\"#ffd479\" cx=\"395.39\" cy=\"-162\" rx=\"148.67\" ry=\"18\"/>\n",
       "<text text-anchor=\"middle\" x=\"395.39\" y=\"-158.3\" font-family=\"Times,serif\" font-size=\"14.00\">σ_[genre == &#39;Mystery&#39; or prob &gt;= 0.3]</text>\n",
       "</g>\n",
       "<!-- IRSel&#45;&gt;IJoin -->\n",
       "<g id=\"edge5\" class=\"edge\">\n",
       "<title>IRSel&#45;&gt;IJoin</title>\n",
       "<path fill=\"none\" stroke=\"black\" d=\"M361.97,-179.59C342.11,-189.45 316.76,-202.04 295.65,-212.51\"/>\n",
       "<polygon fill=\"black\" stroke=\"black\" points=\"294,-209.43 286.59,-217.01 297.11,-215.7 294,-209.43\"/>\n",
       "</g>\n",
       "<!-- IRISel -->\n",
       "<g id=\"node6\" class=\"node\">\n",
       "<title>IRISel</title>\n",
       "<ellipse fill=\"#ffd479\" stroke=\"#ffd479\" cx=\"395.39\" cy=\"-90\" rx=\"63.89\" ry=\"18\"/>\n",
       "<text text-anchor=\"middle\" x=\"395.39\" y=\"-86.3\" font-family=\"Times,serif\" font-size=\"14.00\">σ_[prob &lt; 0.7]</text>\n",
       "</g>\n",
       "<!-- IRISel&#45;&gt;IRSel -->\n",
       "<g id=\"edge3\" class=\"edge\">\n",
       "<title>IRISel&#45;&gt;IRSel</title>\n",
       "<path fill=\"none\" stroke=\"black\" d=\"M395.39,-108.3C395.39,-116.02 395.39,-125.29 395.39,-133.89\"/>\n",
       "<polygon fill=\"black\" stroke=\"black\" points=\"391.89,-133.9 395.39,-143.9 398.89,-133.9 391.89,-133.9\"/>\n",
       "</g>\n",
       "<!-- IRIIRel -->\n",
       "<g id=\"node7\" class=\"node\">\n",
       "<title>IRIIRel</title>\n",
       "<ellipse fill=\"none\" stroke=\"black\" cx=\"395.39\" cy=\"-18\" rx=\"68.79\" ry=\"18\"/>\n",
       "<text text-anchor=\"middle\" x=\"395.39\" y=\"-14.3\" font-family=\"Times,serif\" font-size=\"14.00\">directors_genres</text>\n",
       "</g>\n",
       "<!-- IRIIRel&#45;&gt;IRISel -->\n",
       "<g id=\"edge2\" class=\"edge\">\n",
       "<title>IRIIRel&#45;&gt;IRISel</title>\n",
       "<path fill=\"none\" stroke=\"black\" d=\"M395.39,-36.3C395.39,-44.02 395.39,-53.29 395.39,-61.89\"/>\n",
       "<polygon fill=\"black\" stroke=\"black\" points=\"391.89,-61.9 395.39,-71.9 398.89,-61.9 391.89,-61.9\"/>\n",
       "</g>\n",
       "</g>\n",
       "</svg>\n"
      ],
      "text/plain": [
       "<graphviz.dot.Digraph at 0x125126280>"
      ]
     },
     "execution_count": 11,
     "metadata": {},
     "output_type": "execute_result"
    }
   ],
   "source": [
    "rbj = ReplaceByJoin(pds.root) \n",
    "rbj.optimize(pds.root)\n",
    "\n",
    "# after optimization\n",
    "graph = rbj.root.get_graph()\n",
    "graph"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "### Optimization 4: Insert projections\n",
    "\n",
    "Project only the attributes, that are needed upwards the tree"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 12,
   "metadata": {},
   "outputs": [
    {
     "data": {
      "image/svg+xml": [
       "<?xml version=\"1.0\" encoding=\"UTF-8\" standalone=\"no\"?>\n",
       "<!DOCTYPE svg PUBLIC \"-//W3C//DTD SVG 1.1//EN\"\n",
       " \"http://www.w3.org/Graphics/SVG/1.1/DTD/svg11.dtd\">\n",
       "<!-- Generated by graphviz version 2.47.2 (20210527.0053)\n",
       " -->\n",
       "<!-- Pages: 1 -->\n",
       "<svg width=\"552pt\" height=\"332pt\"\n",
       " viewBox=\"0.00 0.00 552.23 332.00\" xmlns=\"http://www.w3.org/2000/svg\" xmlns:xlink=\"http://www.w3.org/1999/xlink\">\n",
       "<g id=\"graph0\" class=\"graph\" transform=\"scale(1 1) rotate(0) translate(4 328)\">\n",
       "<polygon fill=\"white\" stroke=\"transparent\" points=\"-4,4 -4,-328 548.23,-328 548.23,4 -4,4\"/>\n",
       "<!-- Pro -->\n",
       "<g id=\"node1\" class=\"node\">\n",
       "<title>Pro</title>\n",
       "<ellipse fill=\"#76d6ff\" stroke=\"#76d6ff\" cx=\"254.39\" cy=\"-306\" rx=\"83.39\" ry=\"18\"/>\n",
       "<text text-anchor=\"middle\" x=\"254.39\" y=\"-302.3\" font-family=\"Times,serif\" font-size=\"14.00\">π_[last_name, prob]</text>\n",
       "</g>\n",
       "<!-- IJoin -->\n",
       "<g id=\"node2\" class=\"node\">\n",
       "<title>IJoin</title>\n",
       "<ellipse fill=\"#fffc79\" stroke=\"#fffc79\" cx=\"254.39\" cy=\"-234\" rx=\"89.08\" ry=\"18\"/>\n",
       "<text text-anchor=\"middle\" x=\"254.39\" y=\"-230.3\" font-family=\"Times,serif\" font-size=\"14.00\">⋈_[id == director_id]</text>\n",
       "</g>\n",
       "<!-- IJoin&#45;&gt;Pro -->\n",
       "<g id=\"edge6\" class=\"edge\">\n",
       "<title>IJoin&#45;&gt;Pro</title>\n",
       "<path fill=\"none\" stroke=\"black\" d=\"M254.39,-252.3C254.39,-260.02 254.39,-269.29 254.39,-277.89\"/>\n",
       "<polygon fill=\"black\" stroke=\"black\" points=\"250.89,-277.9 254.39,-287.9 257.89,-277.9 250.89,-277.9\"/>\n",
       "</g>\n",
       "<!-- ILSel -->\n",
       "<g id=\"node3\" class=\"node\">\n",
       "<title>ILSel</title>\n",
       "<ellipse fill=\"#ffd479\" stroke=\"#ffd479\" cx=\"114.39\" cy=\"-162\" rx=\"114.28\" ry=\"18\"/>\n",
       "<text text-anchor=\"middle\" x=\"114.39\" y=\"-158.3\" font-family=\"Times,serif\" font-size=\"14.00\">σ_[last_name == &#39;Tarantino&#39;]</text>\n",
       "</g>\n",
       "<!-- ILSel&#45;&gt;IJoin -->\n",
       "<g id=\"edge4\" class=\"edge\">\n",
       "<title>ILSel&#45;&gt;IJoin</title>\n",
       "<path fill=\"none\" stroke=\"black\" d=\"M147.21,-179.41C167.07,-189.34 192.54,-202.08 213.67,-212.64\"/>\n",
       "<polygon fill=\"black\" stroke=\"black\" points=\"212.23,-215.83 222.74,-217.17 215.36,-209.57 212.23,-215.83\"/>\n",
       "</g>\n",
       "<!-- ILIRel -->\n",
       "<g id=\"node4\" class=\"node\">\n",
       "<title>ILIRel</title>\n",
       "<ellipse fill=\"none\" stroke=\"black\" cx=\"114.39\" cy=\"-90\" rx=\"41.69\" ry=\"18\"/>\n",
       "<text text-anchor=\"middle\" x=\"114.39\" y=\"-86.3\" font-family=\"Times,serif\" font-size=\"14.00\">directors</text>\n",
       "</g>\n",
       "<!-- ILIRel&#45;&gt;ILSel -->\n",
       "<g id=\"edge1\" class=\"edge\">\n",
       "<title>ILIRel&#45;&gt;ILSel</title>\n",
       "<path fill=\"none\" stroke=\"black\" d=\"M114.39,-108.3C114.39,-116.02 114.39,-125.29 114.39,-133.89\"/>\n",
       "<polygon fill=\"black\" stroke=\"black\" points=\"110.89,-133.9 114.39,-143.9 117.89,-133.9 110.89,-133.9\"/>\n",
       "</g>\n",
       "<!-- IRSel -->\n",
       "<g id=\"node5\" class=\"node\">\n",
       "<title>IRSel</title>\n",
       "<ellipse fill=\"#ffd479\" stroke=\"#ffd479\" cx=\"395.39\" cy=\"-162\" rx=\"148.67\" ry=\"18\"/>\n",
       "<text text-anchor=\"middle\" x=\"395.39\" y=\"-158.3\" font-family=\"Times,serif\" font-size=\"14.00\">σ_[genre == &#39;Mystery&#39; or prob &gt;= 0.3]</text>\n",
       "</g>\n",
       "<!-- IRSel&#45;&gt;IJoin -->\n",
       "<g id=\"edge5\" class=\"edge\">\n",
       "<title>IRSel&#45;&gt;IJoin</title>\n",
       "<path fill=\"none\" stroke=\"black\" d=\"M361.97,-179.59C342.11,-189.45 316.76,-202.04 295.65,-212.51\"/>\n",
       "<polygon fill=\"black\" stroke=\"black\" points=\"294,-209.43 286.59,-217.01 297.11,-215.7 294,-209.43\"/>\n",
       "</g>\n",
       "<!-- IRISel -->\n",
       "<g id=\"node6\" class=\"node\">\n",
       "<title>IRISel</title>\n",
       "<ellipse fill=\"#ffd479\" stroke=\"#ffd479\" cx=\"395.39\" cy=\"-90\" rx=\"63.89\" ry=\"18\"/>\n",
       "<text text-anchor=\"middle\" x=\"395.39\" y=\"-86.3\" font-family=\"Times,serif\" font-size=\"14.00\">σ_[prob &lt; 0.7]</text>\n",
       "</g>\n",
       "<!-- IRISel&#45;&gt;IRSel -->\n",
       "<g id=\"edge3\" class=\"edge\">\n",
       "<title>IRISel&#45;&gt;IRSel</title>\n",
       "<path fill=\"none\" stroke=\"black\" d=\"M395.39,-108.3C395.39,-116.02 395.39,-125.29 395.39,-133.89\"/>\n",
       "<polygon fill=\"black\" stroke=\"black\" points=\"391.89,-133.9 395.39,-143.9 398.89,-133.9 391.89,-133.9\"/>\n",
       "</g>\n",
       "<!-- IRIIRel -->\n",
       "<g id=\"node7\" class=\"node\">\n",
       "<title>IRIIRel</title>\n",
       "<ellipse fill=\"none\" stroke=\"black\" cx=\"395.39\" cy=\"-18\" rx=\"68.79\" ry=\"18\"/>\n",
       "<text text-anchor=\"middle\" x=\"395.39\" y=\"-14.3\" font-family=\"Times,serif\" font-size=\"14.00\">directors_genres</text>\n",
       "</g>\n",
       "<!-- IRIIRel&#45;&gt;IRISel -->\n",
       "<g id=\"edge2\" class=\"edge\">\n",
       "<title>IRIIRel&#45;&gt;IRISel</title>\n",
       "<path fill=\"none\" stroke=\"black\" d=\"M395.39,-36.3C395.39,-44.02 395.39,-53.29 395.39,-61.89\"/>\n",
       "<polygon fill=\"black\" stroke=\"black\" points=\"391.89,-61.9 395.39,-71.9 398.89,-61.9 391.89,-61.9\"/>\n",
       "</g>\n",
       "</g>\n",
       "</svg>\n"
      ],
      "text/plain": [
       "<graphviz.dot.Digraph at 0x125136520>"
      ]
     },
     "execution_count": 12,
     "metadata": {},
     "output_type": "execute_result"
    }
   ],
   "source": [
    "# before optimization\n",
    "graph = rbj.root.get_graph()\n",
    "graph"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 13,
   "metadata": {},
   "outputs": [
    {
     "data": {
      "image/svg+xml": [
       "<?xml version=\"1.0\" encoding=\"UTF-8\" standalone=\"no\"?>\n",
       "<!DOCTYPE svg PUBLIC \"-//W3C//DTD SVG 1.1//EN\"\n",
       " \"http://www.w3.org/Graphics/SVG/1.1/DTD/svg11.dtd\">\n",
       "<!-- Generated by graphviz version 2.47.2 (20210527.0053)\n",
       " -->\n",
       "<!-- Pages: 1 -->\n",
       "<svg width=\"500pt\" height=\"476pt\"\n",
       " viewBox=\"0.00 0.00 500.23 476.00\" xmlns=\"http://www.w3.org/2000/svg\" xmlns:xlink=\"http://www.w3.org/1999/xlink\">\n",
       "<g id=\"graph0\" class=\"graph\" transform=\"scale(1 1) rotate(0) translate(4 472)\">\n",
       "<polygon fill=\"white\" stroke=\"transparent\" points=\"-4,4 -4,-472 496.23,-472 496.23,4 -4,4\"/>\n",
       "<!-- Pro -->\n",
       "<g id=\"node1\" class=\"node\">\n",
       "<title>Pro</title>\n",
       "<ellipse fill=\"#76d6ff\" stroke=\"#76d6ff\" cx=\"223.39\" cy=\"-450\" rx=\"83.39\" ry=\"18\"/>\n",
       "<text text-anchor=\"middle\" x=\"223.39\" y=\"-446.3\" font-family=\"Times,serif\" font-size=\"14.00\">π_[last_name, prob]</text>\n",
       "</g>\n",
       "<!-- IJoin -->\n",
       "<g id=\"node2\" class=\"node\">\n",
       "<title>IJoin</title>\n",
       "<ellipse fill=\"#fffc79\" stroke=\"#fffc79\" cx=\"223.39\" cy=\"-378\" rx=\"89.08\" ry=\"18\"/>\n",
       "<text text-anchor=\"middle\" x=\"223.39\" y=\"-374.3\" font-family=\"Times,serif\" font-size=\"14.00\">⋈_[id == director_id]</text>\n",
       "</g>\n",
       "<!-- IJoin&#45;&gt;Pro -->\n",
       "<g id=\"edge9\" class=\"edge\">\n",
       "<title>IJoin&#45;&gt;Pro</title>\n",
       "<path fill=\"none\" stroke=\"black\" d=\"M223.39,-396.3C223.39,-404.02 223.39,-413.29 223.39,-421.89\"/>\n",
       "<polygon fill=\"black\" stroke=\"black\" points=\"219.89,-421.9 223.39,-431.9 226.89,-421.9 219.89,-421.9\"/>\n",
       "</g>\n",
       "<!-- ILSel -->\n",
       "<g id=\"node3\" class=\"node\">\n",
       "<title>ILSel</title>\n",
       "<ellipse fill=\"#ffd479\" stroke=\"#ffd479\" cx=\"114.39\" cy=\"-306\" rx=\"114.28\" ry=\"18\"/>\n",
       "<text text-anchor=\"middle\" x=\"114.39\" y=\"-302.3\" font-family=\"Times,serif\" font-size=\"14.00\">σ_[last_name == &#39;Tarantino&#39;]</text>\n",
       "</g>\n",
       "<!-- ILSel&#45;&gt;IJoin -->\n",
       "<g id=\"edge7\" class=\"edge\">\n",
       "<title>ILSel&#45;&gt;IJoin</title>\n",
       "<path fill=\"none\" stroke=\"black\" d=\"M140.22,-323.59C154.88,-333 173.41,-344.9 189.26,-355.08\"/>\n",
       "<polygon fill=\"black\" stroke=\"black\" points=\"187.44,-358.07 197.74,-360.53 191.22,-352.18 187.44,-358.07\"/>\n",
       "</g>\n",
       "<!-- ILIPro -->\n",
       "<g id=\"node4\" class=\"node\">\n",
       "<title>ILIPro</title>\n",
       "<ellipse fill=\"#76d6ff\" stroke=\"#76d6ff\" cx=\"103.39\" cy=\"-234\" rx=\"73.39\" ry=\"18\"/>\n",
       "<text text-anchor=\"middle\" x=\"103.39\" y=\"-230.3\" font-family=\"Times,serif\" font-size=\"14.00\">π_[id, last_name]</text>\n",
       "</g>\n",
       "<!-- ILIPro&#45;&gt;ILSel -->\n",
       "<g id=\"edge2\" class=\"edge\">\n",
       "<title>ILIPro&#45;&gt;ILSel</title>\n",
       "<path fill=\"none\" stroke=\"black\" d=\"M106.11,-252.3C107.32,-260.02 108.78,-269.29 110.13,-277.89\"/>\n",
       "<polygon fill=\"black\" stroke=\"black\" points=\"106.69,-278.56 111.7,-287.9 113.61,-277.47 106.69,-278.56\"/>\n",
       "</g>\n",
       "<!-- ILIIRel -->\n",
       "<g id=\"node5\" class=\"node\">\n",
       "<title>ILIIRel</title>\n",
       "<ellipse fill=\"none\" stroke=\"black\" cx=\"103.39\" cy=\"-162\" rx=\"41.69\" ry=\"18\"/>\n",
       "<text text-anchor=\"middle\" x=\"103.39\" y=\"-158.3\" font-family=\"Times,serif\" font-size=\"14.00\">directors</text>\n",
       "</g>\n",
       "<!-- ILIIRel&#45;&gt;ILIPro -->\n",
       "<g id=\"edge1\" class=\"edge\">\n",
       "<title>ILIIRel&#45;&gt;ILIPro</title>\n",
       "<path fill=\"none\" stroke=\"black\" d=\"M103.39,-180.3C103.39,-188.02 103.39,-197.29 103.39,-205.89\"/>\n",
       "<polygon fill=\"black\" stroke=\"black\" points=\"99.89,-205.9 103.39,-215.9 106.89,-205.9 99.89,-205.9\"/>\n",
       "</g>\n",
       "<!-- IRPro -->\n",
       "<g id=\"node6\" class=\"node\">\n",
       "<title>IRPro</title>\n",
       "<ellipse fill=\"#76d6ff\" stroke=\"#76d6ff\" cx=\"337.39\" cy=\"-306\" rx=\"85.29\" ry=\"18\"/>\n",
       "<text text-anchor=\"middle\" x=\"337.39\" y=\"-302.3\" font-family=\"Times,serif\" font-size=\"14.00\">π_[prob, director_id]</text>\n",
       "</g>\n",
       "<!-- IRPro&#45;&gt;IJoin -->\n",
       "<g id=\"edge8\" class=\"edge\">\n",
       "<title>IRPro&#45;&gt;IJoin</title>\n",
       "<path fill=\"none\" stroke=\"black\" d=\"M310.95,-323.24C295.52,-332.71 275.85,-344.79 259.07,-355.09\"/>\n",
       "<polygon fill=\"black\" stroke=\"black\" points=\"256.77,-352.39 250.08,-360.61 260.43,-358.36 256.77,-352.39\"/>\n",
       "</g>\n",
       "<!-- IRISel -->\n",
       "<g id=\"node7\" class=\"node\">\n",
       "<title>IRISel</title>\n",
       "<ellipse fill=\"#ffd479\" stroke=\"#ffd479\" cx=\"343.39\" cy=\"-234\" rx=\"148.67\" ry=\"18\"/>\n",
       "<text text-anchor=\"middle\" x=\"343.39\" y=\"-230.3\" font-family=\"Times,serif\" font-size=\"14.00\">σ_[genre == &#39;Mystery&#39; or prob &gt;= 0.3]</text>\n",
       "</g>\n",
       "<!-- IRISel&#45;&gt;IRPro -->\n",
       "<g id=\"edge6\" class=\"edge\">\n",
       "<title>IRISel&#45;&gt;IRPro</title>\n",
       "<path fill=\"none\" stroke=\"black\" d=\"M341.91,-252.3C341.25,-260.02 340.45,-269.29 339.71,-277.89\"/>\n",
       "<polygon fill=\"black\" stroke=\"black\" points=\"336.22,-277.63 338.86,-287.9 343.2,-278.23 336.22,-277.63\"/>\n",
       "</g>\n",
       "<!-- IRIISel -->\n",
       "<g id=\"node8\" class=\"node\">\n",
       "<title>IRIISel</title>\n",
       "<ellipse fill=\"#ffd479\" stroke=\"#ffd479\" cx=\"343.39\" cy=\"-162\" rx=\"63.89\" ry=\"18\"/>\n",
       "<text text-anchor=\"middle\" x=\"343.39\" y=\"-158.3\" font-family=\"Times,serif\" font-size=\"14.00\">σ_[prob &lt; 0.7]</text>\n",
       "</g>\n",
       "<!-- IRIISel&#45;&gt;IRISel -->\n",
       "<g id=\"edge5\" class=\"edge\">\n",
       "<title>IRIISel&#45;&gt;IRISel</title>\n",
       "<path fill=\"none\" stroke=\"black\" d=\"M343.39,-180.3C343.39,-188.02 343.39,-197.29 343.39,-205.89\"/>\n",
       "<polygon fill=\"black\" stroke=\"black\" points=\"339.89,-205.9 343.39,-215.9 346.89,-205.9 339.89,-205.9\"/>\n",
       "</g>\n",
       "<!-- IRIIIPro -->\n",
       "<g id=\"node9\" class=\"node\">\n",
       "<title>IRIIIPro</title>\n",
       "<ellipse fill=\"#76d6ff\" stroke=\"#76d6ff\" cx=\"343.39\" cy=\"-90\" rx=\"109.68\" ry=\"18\"/>\n",
       "<text text-anchor=\"middle\" x=\"343.39\" y=\"-86.3\" font-family=\"Times,serif\" font-size=\"14.00\">π_[prob, director_id, genre]</text>\n",
       "</g>\n",
       "<!-- IRIIIPro&#45;&gt;IRIISel -->\n",
       "<g id=\"edge4\" class=\"edge\">\n",
       "<title>IRIIIPro&#45;&gt;IRIISel</title>\n",
       "<path fill=\"none\" stroke=\"black\" d=\"M343.39,-108.3C343.39,-116.02 343.39,-125.29 343.39,-133.89\"/>\n",
       "<polygon fill=\"black\" stroke=\"black\" points=\"339.89,-133.9 343.39,-143.9 346.89,-133.9 339.89,-133.9\"/>\n",
       "</g>\n",
       "<!-- IRIIIIRel -->\n",
       "<g id=\"node10\" class=\"node\">\n",
       "<title>IRIIIIRel</title>\n",
       "<ellipse fill=\"none\" stroke=\"black\" cx=\"343.39\" cy=\"-18\" rx=\"68.79\" ry=\"18\"/>\n",
       "<text text-anchor=\"middle\" x=\"343.39\" y=\"-14.3\" font-family=\"Times,serif\" font-size=\"14.00\">directors_genres</text>\n",
       "</g>\n",
       "<!-- IRIIIIRel&#45;&gt;IRIIIPro -->\n",
       "<g id=\"edge3\" class=\"edge\">\n",
       "<title>IRIIIIRel&#45;&gt;IRIIIPro</title>\n",
       "<path fill=\"none\" stroke=\"black\" d=\"M343.39,-36.3C343.39,-44.02 343.39,-53.29 343.39,-61.89\"/>\n",
       "<polygon fill=\"black\" stroke=\"black\" points=\"339.89,-61.9 343.39,-71.9 346.89,-61.9 339.89,-61.9\"/>\n",
       "</g>\n",
       "</g>\n",
       "</svg>\n"
      ],
      "text/plain": [
       "<graphviz.dot.Digraph at 0x125136b50>"
      ]
     },
     "execution_count": 13,
     "metadata": {},
     "output_type": "execute_result"
    }
   ],
   "source": [
    "ip = InsertProjection(rbj.root) \n",
    "ip.optimize(rbj.root)\n",
    "\n",
    "# after optimization\n",
    "graph = ip.root.get_graph()\n",
    "graph"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": []
  }
 ],
 "metadata": {
  "kernelspec": {
   "display_name": "Python 3",
   "language": "python",
   "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.9.5"
  },
  "varInspector": {
   "cols": {
    "lenName": 16,
    "lenType": 16,
    "lenVar": 40
   },
   "kernels_config": {
    "python": {
     "delete_cmd_postfix": "",
     "delete_cmd_prefix": "del ",
     "library": "var_list.py",
     "varRefreshCmd": "print(var_dic_list())"
    },
    "r": {
     "delete_cmd_postfix": ") ",
     "delete_cmd_prefix": "rm(",
     "library": "var_list.r",
     "varRefreshCmd": "cat(var_dic_list()) "
    }
   },
   "types_to_exclude": [
    "module",
    "function",
    "builtin_function_or_method",
    "instance",
    "_Feature"
   ],
   "window_display": false
  }
 },
 "nbformat": 4,
 "nbformat_minor": 2
}