{
"cells": [
{
"cell_type": "markdown",
"id": "43c57813-b0ec-4b89-b95a-5bd6a9d1da16",
"metadata": {
"deletable": true,
"editable": true,
"frozen": false,
"slideshow": {
"slide_type": ""
},
"tags": []
},
"source": [
"# Requêtes flexibles et stratégies d’exécution\n",
"## Travail à faire et à rendre\n",
"Ce cahier (notebook) Jupyter est à la fois l'énoncé du TP et ce qu'il faudra déposer à la fin de la séance sur l’ENT. Il vous sera demandé de remplir les cellules prévues avec vos réponses qui pourront être du texte en *markdown*, voir **[ce lien](https://commonmark.org/help/)** pour la syntaxe exacte. Ça aussi pourra être des requêtes SQL dont le résultat apparaîtra en dessous, ou des scripts Python pour calculer une information plus complexe.\n",
"\n",
"Rappel: taper entrée pour exécuter une cellule et passer à la suivante. Tapez CTRLentrée pour évaluer une cellule sans passer à la suivante."
]
},
{
"cell_type": "markdown",
"id": "234dd2ed-cf89-4abb-9e95-0527b0d93c0b",
"metadata": {
"deletable": true,
"editable": true,
"frozen": false,
"slideshow": {
"slide_type": ""
},
"tags": []
},
"source": [
"## Préparation\n",
"### Connexion au serveur PostgreSQL et accès aux données en mode shell\n",
"Vous allez commencer par installer la base de données et y insérer toutes les données du TP. C’est une base appelée `SecondHandCars`.\n",
"\n",
"Voici la commande pour commencer, à ne faire qu'une seule fois en tout (de toutes les séances de TP) :\n",
"```\n",
"...$ application install postgresql\n",
"```\n",
"Ensuite, voici la commande pour lancer PostgreSQL, à faire à chaque séance de TP :\n",
"```\n",
"...$ application start postgresql\n",
"```\n",
"Les commandes suivantes ne sont à faire que la première fois pour créer la base de données du TP :\n",
"```\n",
"...$ createdb -h localhost secondhandcars\n",
"...$ curl https://perso.univ-rennes1.fr/pierre.nerzic/BDDA/SecondHandCars.dump | psql -h localhost -d secondhandcars\n",
"...$\n",
"```\n",
"Maintenant, la base `secondhandcars` est prête pour le TP. Voici comment on s’y connecte :\n",
"```\n",
"...$ psql -h localhost secondhandcars\n",
"votrelogin=#\n",
"```\n",
"Ce prompt est celui du SGBD qui attend des requêtes SQL. Par exemple pour obtenir la liste des tables, tapez ceci. `\\l` et `\\d` sont des commandes de psql. `\\l` affiche la liste des bases de données, `\\d` affiche la liste des tables de la base courante.\n",
"```\n",
"votrelogin=# \\l\n",
"votrelogin=# \\d\n",
"votrelogin=# \\d secondhandcars\n",
"votrelogin=#\n",
"```"
]
},
{
"cell_type": "markdown",
"id": "4c3acf2b-092c-4f48-86c9-5d5b8b563322",
"metadata": {
"deletable": true,
"editable": true,
"frozen": false
},
"source": [
"\n",
" Gardez bien la fenêtre shell ouverte. Vous
devrez arrêter le service PostgreSQL à la fin de
chaque séance en faisant ce qui suit, ou en éteignant la machine :\n",
"
\n",
"votrelogin=# \\q\n",
"...$ application stop postgresql\n",
"\n",
"
\n",
" Attention, les requêtes à expliquer ne sont pas celles de comptage, mais celles qui retournent des n-uplets. C'est à dire EXPLAIN SELECT * FROM et non pas EXPLAIN SELECT COUNT(*) FROM\n",
"
"
]
},
{
"cell_type": "markdown",
"id": "3778e359-55bb-405c-ab75-b261f45505ee",
"metadata": {
"deletable": true,
"editable": true,
"frozen": false
},
"source": [
"D’autre part, cela n’est intéressant que s’il y a un index sur les colonnes concernées par la clause where. On ne va pas toucher à la colonne `puissance_ch`, mais `prix_neuf_moyen`. D'abord, on supprime tout index existant (au cas où)."
]
},
{
"cell_type": "code",
"execution_count": null,
"id": "dfe587fb-ff1d-4df2-9e1b-3dbbc506b897",
"metadata": {
"deletable": true,
"editable": true,
"frozen": false
},
"outputs": [],
"source": [
"%sql DROP INDEX IF EXISTS idx_prix_neuf_moyen"
]
},
{
"cell_type": "code",
"execution_count": null,
"id": "14dcbf59-6933-49cf-bfba-6f8968ea831d",
"metadata": {
"deletable": true,
"editable": true,
"frozen": false
},
"outputs": [],
"source": [
"%sql EXPLAIN SELECT * FROM secondhandcars WHERE prix_neuf_moyen < 5000"
]
},
{
"cell_type": "markdown",
"id": "6d47dacc-0922-473f-8511-610dfbd7fd26",
"metadata": {
"deletable": true,
"editable": true,
"frozen": false
},
"source": [
"Notez bien `Seq Scan on secondhandcars`"
]
},
{
"cell_type": "code",
"execution_count": null,
"id": "3f855f47-41b8-47b3-aa6d-d227e0836d87",
"metadata": {
"deletable": true,
"editable": true,
"frozen": false
},
"outputs": [],
"source": [
"%sql CREATE INDEX idx_prix_neuf_moyen ON secondhandcars(prix_neuf_moyen)"
]
},
{
"cell_type": "code",
"execution_count": null,
"id": "2c38d39d-1333-4529-94ea-1e2651411122",
"metadata": {
"deletable": true,
"editable": true,
"frozen": false
},
"outputs": [],
"source": [
"%sql EXPLAIN SELECT * FROM secondhandcars WHERE prix_neuf_moyen < 5000"
]
},
{
"cell_type": "markdown",
"id": "8f92e3ba-b54d-4473-bfdd-f5a250b7754c",
"metadata": {
"deletable": true,
"editable": true,
"frozen": false
},
"source": [
"Cette fois, c'est `Bitmap Heap Scan on secondhandcars`.\n",
"\n",
"Sans rentrer dans tous les détails techniques, vous allez observer deux stratégies d’exécution.\n",
"* « Seq Scan », c’est à dire un parcours exhaustif des n-uplets pas efficace et dont il n'y a rien à dire.\n",
"* « Bitmap Heap Scan » qui est un parcours à deux niveaux beaucoup plus rapide.\n",
"\n",
"La stratégie Bitmap Scan est sur 4 lignes à lire de bas en haut. Ça commence d’abord 3e ligne par un « Bitmap Index Scan » qui consiste en un parcours des « pages » contenant les n-uplets susceptibles d’être sélectionnés par la condition « Index Cond » 4e ligne.\n",
"\n",
"C’est à dire que les n-uplets sont groupés dans le stockage interne (disque dur) pour former des pages. Une page fait 8 Ko, `SELECT current_setting('block_size');` voir ci-dessous. Une page contient donc un certain nombre de n-uplets. Certaines pages contiennent des n-uplets utiles, d’autres aucun. L’index contient un « bitmap » qui indique lesquelles sont pertinentes. C’est comme un tableau de booléens, un par valeur remarquable présente dans l’index, qui indiquent dans quelles pages on trouve cette valeur. Par exemple qu’on trouve des annonces pour des voitures dont le prix_neuf_moyen convient dans telles et telles pages sur le disque. Vous comprenez que ce mécanisme occupe de la place mais il accélère considérablement les recherches quand on peut l'utiliser."
]
},
{
"cell_type": "code",
"execution_count": null,
"id": "85e40544-e4a3-4f43-ad6f-d41b3bad6aa5",
"metadata": {
"deletable": true,
"editable": true,
"frozen": false
},
"outputs": [],
"source": [
"%sql SELECT current_setting('block_size') AS block_size"
]
},
{
"cell_type": "markdown",
"id": "8ecc3f71-0c03-4611-949d-88afc9a21e71",
"metadata": {
"deletable": true,
"editable": true,
"frozen": false
},
"source": [
"Donc il y a d’abord cette sélection des pages contenant les données qu'on cherche, puis en remontant, il y a un « Recheck Cond » 2e ligne pour vérifier la condition individuellement sur les n-uplets des pages choisies.\n",
"\n",
"Vous trouverez tout le détail des explications dans __[la documentation de référence sur les plans d'exécution](https://www.postgresql.org/docs/current/using-explain.html)__. Et __[cette page](https://www.cybertec-postgresql.com/en/postgresql-indexing-index-scan-vs-bitmap-scan-vs-sequential-scan-basics/)__ résume le tout avec des schémas.\n",
"\n",
"La bascule entre les deux stratégies, « Seq Scan » ou « Bitmap Scan » dépend du nombre attendu de n-uplets et leur répartition dans les pages. Il vaut mieux faire un parcours exhaustif si on prévoit que beaucoup de n-uplets vont satisfaire la condition where, et utiliser le bitmap s’il y en a peu, de préférence répartis sur peu de pages différentes. Mais évidemment, il faut qu'il y ait un bitmap pour les valeurs recherchées. Les critères complets sont dans __[la documentation de référence, statistiques utilisées](https://www.postgresql.org/docs/current/planner-stats.html)__.\n",
"\n",
"On va étudier l'emploi ou non des index pour accélérer les requêtes. C'est selon les perspectives d'avoir un gain de vitesse, et donc c'est en estimant la proportion des données sélectionnées. On veut essayer de savoir si le SGBD se base sur le nombre relatif de n-uplets.\n",
"\n",
"On va dérouler l'algorithme suivant sur plusieurs requêtes et voir ce qu'il est est\n",
"\n",
"1. On demande le nombre total de n-uplets dans la table\n",
"2. On exécute la requête et on compte le nombre de n-uplets qu'elle retourne\n",
"3. On rapporte ce nombre au nombre total de n-uplets dans la table : on obtient un réel entre 0 et 1 qu'on appelle *cardinalité relative*.\n",
"4. On demande quelle est la stratégie pour sélectionner les n-uplets : Seq Scan ou Bitmap Heap Scan\n",
"\n",
"À priori, ça devrait être le Bitmap Heap Scan quand la cardinalité relative est faible.\n",
"\n",
"Complétez la fonction suivante qui déroule l'algorithme."
]
},
{
"cell_type": "code",
"execution_count": null,
"id": "8f92089f-ca5c-4cf6-a638-7810bf672ee6",
"metadata": {
"deletable": true,
"editable": true,
"frozen": false
},
"outputs": [],
"source": [
"def PrintKindOfScan(query):\n",
" \"displays the relative cardinality and the first line of the execution plan of the query\"\n",
" # 1. total number of tuples in the table\n",
" global tot_number_tuples\n",
" # print the query\n",
" print(query)\n",
" # 2. get the tuples selected by the request\n",
" results = %sql {{query}}\n",
" # 3. compute the relative cardinality\n",
" rel_card = 0 # TODO\n",
" print(f\" relative cardinality is {rel_card:.3f}\")\n",
" # 4. analyze the request and get the strategy\n",
" analysis = %sql EXPLAIN {{query}}\n",
" print(f\" {analysis[0][0]}\")"
]
},
{
"cell_type": "markdown",
"id": "a721d27e-a85a-43d3-b4d7-11fa262c21f7",
"metadata": {
"deletable": true,
"editable": true,
"frozen": false
},
"source": [
"On applique cette fonction à plusieurs requêtes."
]
},
{
"cell_type": "code",
"execution_count": null,
"id": "e4fd6305-157e-47fc-aa63-46ba76844d19",
"metadata": {
"deletable": true,
"editable": true,
"frozen": false
},
"outputs": [],
"source": [
"PrintKindOfScan(\"SELECT * FROM secondhandcars WHERE prix BETWEEN 3000 AND 7500\")\n",
"PrintKindOfScan(\"SELECT * FROM secondhandcars WHERE prix BETWEEN 3500 AND 12000\")\n",
"PrintKindOfScan(\"SELECT * FROM secondhandcars WHERE prix < 17500\")\n",
"PrintKindOfScan(\"SELECT * FROM secondhandcars WHERE prix > 9000\")\n",
"PrintKindOfScan(\"SELECT * FROM secondhandcars WHERE prix > 250000\")"
]
},
{
"cell_type": "markdown",
"id": "c5a1f7bf-e659-46eb-ba55-060d4d8455cc",
"metadata": {
"deletable": true,
"editable": true,
"frozen": false
},
"source": [
"Il semble qu'on puisse en déduire que le SGBD utilise le Bitmap Scan lorsque la cardinalité relative est inférieure à 0,5. Mais la question est alors : comment le SGBD peut-il calculer la cardinalité relative alors que la requête n'est pas encore exécutée ? Il faut impérativement estimer cette cardinalité à partir de la condition de sélection.\n",
"\n",
"### Histogramme de la distribution des données\n",
"\n",
"La réponse, c'est que le SGBD maintient des statistiques sur la distribution des données, dans une métatable. C'est par exemple l'histogramme des valeurs de l'attribut, comme le suivant qui montre la distribution des prix."
]
},
{
"cell_type": "code",
"execution_count": null,
"id": "4cba0626-c758-4f9d-83a7-a9954ad6f036",
"metadata": {
"deletable": true,
"editable": true,
"frozen": false
},
"outputs": [],
"source": [
"results = %sql SELECT prix FROM secondhandcars WHERE prix < 100000\n",
"import plotly.express as px\n",
"px.histogram(results, x=\"prix\", nbins=80)"
]
},
{
"cell_type": "markdown",
"id": "b7bce73c-bf9c-40d5-86ec-d06304e3e430",
"metadata": {
"deletable": true,
"editable": true,
"frozen": false
},
"source": [
"Avec cet histogramme, on peut estimer la cardinalité d'une condition comme prix < 3500. Il suffit de cumuler les barres entre 0 et 3500.\n",
"\n",
"Alors PostgreSQL utilise effectivement un histogramme, mais il n'a pas cette apparence. Le précédent est qualifié d'*equiwidth*, car les barres ont toutes la même largeur, et leur hauteur représente le nombre de données dans l'intervalle. Il existe aussi des histogrammes *equidepth* dont le principe est que toutes les barres représentent la même quantité de données, et donc les barres sont plus ou moins larges.\n",
"\n",
"Voici comment extraire cet histogramme de la métatable. C'est un peu compliqué, parce que la colonne `histogram_bounds` de la table `pg_stats` est un tableau -- c'est possible avec PostgreSQL. Pour obtenir ce tableau sous la forme de valeurs séparées, on utilise la fonction `unnest` __[documentée ici](https://www.postgresql.org/docs/current/functions-array.html#ARRAY-FUNCTIONS-TABLE)__ ; et il faut indiquer en détail quel est le type des valeurs recherchées, des `int` qui sont écrits dans un texte, voir __[cette explication](https://stackoverflow.com/a/70782751)__."
]
},
{
"cell_type": "code",
"execution_count": null,
"id": "ba5a78d8-ce6e-4ec3-a9d4-5473529f26d6",
"metadata": {
"deletable": true,
"editable": true,
"frozen": false,
"scrolled": true
},
"outputs": [],
"source": [
"%sql SELECT unnest(histogram_bounds::text::int[]) AS bounds FROM pg_stats WHERE tablename='secondhandcars' AND attname='prix' LIMIT 10"
]
},
{
"cell_type": "markdown",
"id": "6ee76662-acdb-48f5-92a0-b90f0a2919ae",
"metadata": {
"deletable": true,
"editable": true,
"frozen": false
},
"source": [
"NB: la requête précédente extrait seulement les 10 premières bornes, c'est à dire les 9 premiers intervalles. Le script suivant dessine les 15 premiers intervalles. "
]
},
{
"cell_type": "code",
"execution_count": null,
"id": "98e897b2-f545-46e0-bfcd-9fa03c3f5cd8",
"metadata": {
"deletable": true,
"editable": true,
"frozen": false,
"scrolled": true
},
"outputs": [],
"source": [
"# histogram extraction of the first 15 intervals (16 bounds)\n",
"query = \"\"\"SELECT unnest(histogram_bounds::text::int[]) AS bounds\n",
" FROM pg_stats WHERE tablename='secondhandcars' AND attname='prix'\n",
" LIMIT 16\"\"\"\n",
"bounds = %sql {{query}}\n",
"\n",
"# convert successive bounds to interval list\n",
"histogram_bars = []\n",
"b1 = None\n",
"for b2 in bounds:\n",
" if b1 is not None:\n",
" histogram_bars.append({'from': b1.bounds, 'to': b2.bounds, 'height': 1, 'text': f']{b1.bounds}, { b2.bounds}]'})\n",
" b1 = b2\n",
"\n",
"# convert to Pandas DataFrame to be displayed with Plotly\n",
"import pandas\n",
"df = pandas.DataFrame(histogram_bars)\n",
"\n",
"# draw a Bar Chart\n",
"import plotly.graph_objects as go\n",
"figure = go.Figure()\n",
"figure.add_trace(\n",
" go.Bar(\n",
" x=((df[\"from\"]+df[\"to\"])/2).to_list(),\n",
" y=df[\"height\"],\n",
" width=(df[\"to\"]-df[\"from\"]).to_list(),\n",
" text=df[\"text\"],\n",
" )\n",
")"
]
},
{
"cell_type": "markdown",
"id": "95bbf550-5cd1-4900-813c-c600194cb8e8",
"metadata": {
"deletable": true,
"editable": true,
"frozen": false
},
"source": [
"Dans le graphique précédent, chaque barre représente approximativement la même quantité de données. Il faut bien comprendre que ce ne sont que des estimations collectées très rapidement, donc imprécises. D'autre part, les bornes peuvent changer d'une séance à l'autre. C'est la requête SQL `ANALYZE;` qui relance le recueil des métadonnées.\n",
"\n",
"Exécutez la cellule suivante, puis ré-exécutez les cellules à partir de la [[35]](#mycell). Il est possible que vous observiez des changements (ou pas). C'est pourquoi dans la suite, vos résultats seront un peu différents de ceux des voisins."
]
},
{
"cell_type": "code",
"execution_count": null,
"id": "1dfeb318-1610-4979-8249-f9b937f50e7a",
"metadata": {
"deletable": true,
"editable": true,
"frozen": false
},
"outputs": [],
"source": [
"%sql ANALYZE;"
]
},
{
"cell_type": "markdown",
"id": "9e1cc845-2d89-4c86-9777-f60868bb6244",
"metadata": {
"deletable": true,
"editable": true,
"frozen": false
},
"source": [
"Remarquez que cette commande est très rapide. Elle utilise la manière dont les données sont rangées en mémoire sans les parcourir une à une. C'est pour cela qu'elle ne recueille que des estimations.\n",
"\n",
"### Vérification de la qualité de l'histogramme equidepth\n",
"\n",
"Par curiosité, on va regarder ce qu'il en est de la cardinalité exacte de quelques unes de ces barres. On reprend la variable `histogram_bars`. C'est un tableau de bornes `from`, `to`. On va demander le nombre de n-uplets situés dans ces bornes. Cependant, on va considérer que `from` est exclu car il ne faut pas que les mêmes n-uplets soient comptés dans deux barres, lorsque leur prix est à la frontière."
]
},
{
"cell_type": "code",
"execution_count": null,
"id": "3bd932c9-e1dd-414e-931c-6c1b83387967",
"metadata": {
"deletable": true,
"editable": true,
"frozen": false
},
"outputs": [],
"source": [
"# sum of counts\n",
"total_count = 0\n",
"# loop on bars\n",
"for bar in histogram_bars:\n",
" # query the actual cardinality of this bar\n",
" results = %sql # TODO query the number of cars that have their prix inside bar, limits are bar[\"from\"] and bar[\"to\"]\n",
" bar_count = 0 # TODO get the number of cars in results\n",
" # accumulate bar_count in total_count\n",
" # TODO update total_count\n",
" # display the results\n",
" print(f'{bar[\"text\"]:15}: {bar_count} tuples')\n",
"# average count\n",
"print(f'average count per interval = {total_count / len(histogram_bars):.3f}')"
]
},
{
"cell_type": "markdown",
"id": "20365fb7-b13f-40aa-a47a-649e6c06e528",
"metadata": {
"deletable": true,
"editable": true,
"frozen": false
},
"source": [
"On voit une liste d'intervalles. Ce sont les bornes de l'histogramme. On voit aussi le véritable nombre de tuples qu'il y a dans chaque intervalle. Les résultats semblent extrêmement bizarres, très variables, loin de la définition d'un histogramme *equidepth*, même en considérant que ce ne sont que des estimations. Normalement, on devrait avoir à peu près le même nombre de tuples par intervalle, car les bornes sont ajustées pour cela, au contraire d'un histogramme *equiwidth* dont on force les bornes à des intervalles réguliers et où le nombre de n-uplets varie beaucoup.\n",
"\n",
"Alors déjà, il est possible que les données soient très mal réparties et qu'il soit impossible de faire un tel histogramme quand il y a de très nombreuses valeurs identiques impossibles à placer dans des intervalles distincts. Ça pourrait expliquer les inégalités, car les vendeurs de voitures ont tendance à arrondir le prix.\n",
"\n",
"Ceci étant, même si l'histogramme est très approximatif, il permet quand même d'estimer des cardinalités. En effet, s'il y a 100 intervalles, (100+1 bornes) dans cet histogramme (le programme précédent n'en montre que 15. Les presque 50000 n-uplets de la table sont distribués sur ces 100 intervalles, soient presque 500 par intervalle. C'est à peu près la moyenne qu'on observe. Il semble que les bornes soient seulement un peu mal placées.\n",
"\n",
"### Valeurs absentes (null)\n",
"\n",
"Mais il semble qu'il manque quelque chose. La moyenne du nombre de n-uplets par intervalle est un peu faible, environ 465 au lieu de 495. Au niveau de l'ensemble des données, ça représente seulement 465*100 n-uplets au lieu de 49573. On va voir pourquoi dans tout ce qui suit.\n",
"\n",
"D'abord, il y a des valeurs `null` dans la colonne prix. Ces valeurs sont évidemment absentes de l'histogramme, ce qui pourrait expliquer la moyenne plus basse. Ecrivez la requête qui compte les valeurs nulles dans la colonne prix."
]
},
{
"cell_type": "code",
"execution_count": null,
"id": "a3149f22-b025-47e9-94bf-2a30ef312d41",
"metadata": {
"deletable": true,
"editable": true,
"frozen": false
},
"outputs": [],
"source": [
"actual_null_count = 0 # TODO SQL query to get the number of cars that have null prix \n",
"print(f'actual_null_count = {actual_null_count}')"
]
},
{
"cell_type": "markdown",
"id": "a5a7e418-59f9-485a-871b-60d70bc46202",
"metadata": {
"deletable": true,
"editable": true,
"frozen": false
},
"source": [
"Le nombre est assez petit, donc il manque encore autre chose pour expliquer la mauvaise disposition apparente des bornes de l'histogramme. On va le voir dans la prochaine section.\n",
"\n",
"Parmi les métadonnées de PostgreSQL, il y a aussi une estimation du nombre de valeurs nulles pour chaque colonne. Voici la requête pour le connaître."
]
},
{
"cell_type": "code",
"execution_count": null,
"id": "01d09a31-1346-4cd7-8371-b5968a28d7d4",
"metadata": {
"deletable": true,
"editable": true,
"frozen": false
},
"outputs": [],
"source": [
"results = %sql SELECT null_frac FROM pg_stats WHERE tablename='secondhandcars' AND attname='prix'\n",
"est_null_card = results[0].null_frac\n",
"est_null_count = round(est_null_card * tot_number_tuples)\n",
"print(f'est_null_count = {est_null_count}, error = {100 * abs(est_null_count - actual_null_count) / actual_null_count:.2f}%')"
]
},
{
"cell_type": "markdown",
"id": "5f335538-cdc1-472a-a429-11fe94d5332e",
"metadata": {
"deletable": true,
"editable": true,
"frozen": false
},
"source": [
"`est_null_card` est la cardinalité relative estimée des valeurs nulles. On voit que la cardinalité absolue estimée, `est_null_count` est proche de la véritable cardinalité, mais elle ne suffit pas à expliquer l'écart entre la cardinalité réelle des bornes et la répartition irrégulière des bornes de l'histogramme, car il manque environ 3000 n-uplets (46500 au lieu de 49573).\n",
"\n",
"### Valeurs fréquentes\n",
"\n",
"PostgreSQL mémorise aussi une liste des valeurs les plus fréquentes rencontrées parmi les données. Par défaut, ce sont les 100 valeurs les plus fréquentes du prix (parce qu'il y a un index sur la colonne prix). Voici comment l'obtenir. C'est une requête bien plus complexe car les valeurs fréquentes et leur cardinalités sont dans deux colonnes différentes de la table `pg_stats`."
]
},
{
"cell_type": "code",
"execution_count": null,
"id": "7fe83410-9737-416a-b408-f40d838b3ec8",
"metadata": {
"deletable": true,
"editable": true,
"frozen": false,
"scrolled": true
},
"outputs": [],
"source": [
"%%sql\n",
"SELECT * FROM (\n",
" SELECT unnest(most_common_vals::text::int[]) AS val,\n",
" unnest(most_common_freqs) AS freq,\n",
" round(unnest(most_common_freqs) * 49573) AS card --- À ENLEVER\n",
" FROM pg_stats WHERE tablename = 'secondhandcars' AND attname = 'prix'\n",
") AS val_freq_table\n",
"ORDER BY val"
]
},
{
"cell_type": "markdown",
"id": "5fe5d006-0b03-4b57-9234-e08b57971e97",
"metadata": {
"deletable": true,
"editable": true,
"frozen": false
},
"source": [
"La colonne `val` contient des valeurs qui ont été souvent rencontrées dans les données. Par exemple, un prix de 9990€ semble très fréquent, 560 fois, et 10500€ est rencontré pour 496 voitures -- Attention, vos valeurs sont probablement légèrement différentes.\n",
"\n",
"Dans la cellule suivante, mettez le prix le plus fréquent et sa cardinalité absolue estimée selon les métadonnées de votre base. C'est nettement plus facile en modifiant la requête précédente pour trier les fréquences dans l'ordre décroissant et en affichant aussi la cardinalité absolue."
]
},
{
"cell_type": "markdown",
"id": "0a3095b0-4a6a-4005-bdc5-a519590e3a3a",
"metadata": {
"deletable": true,
"editable": true,
"frozen": false
},
"source": [
"✍ \n",
"prix: ..., cardinalité absolue estimée ...\n",
"
"
]
},
{
"cell_type": "markdown",
"id": "16844f51-f242-408c-bca7-8c881076aee7",
"metadata": {
"deletable": true,
"editable": true,
"frozen": false
},
"source": [
"Comme pour la cardinalité des valeurs nulles, vérifions rapidement quelques valeurs fréquentes avec le script suivant, à compléter."
]
},
{
"cell_type": "code",
"execution_count": null,
"id": "6d197199-c6ee-4122-a519-a18d0c0ebc1e",
"metadata": {
"deletable": true,
"editable": true,
"frozen": false
},
"outputs": [],
"source": [
"# put most common values and their frequencies into an array\n",
"query = \"\"\"\n",
"SELECT * FROM (\n",
" SELECT unnest(most_common_vals::text::int[]) AS val,\n",
" unnest(most_common_freqs) AS freq\n",
" FROM pg_stats WHERE tablename = 'secondhandcars' AND attname = 'prix'\n",
") AS val_freq_table\n",
"ORDER BY val\n",
"\"\"\"\n",
"most_common_vals_freqs = %sql {{query}}\n",
"\n",
"# query the actual cardinality of some of these values\n",
"import random\n",
"for _ in range(8):\n",
" # pick a random pair of a value and its estimated relative cardinality\n",
" value, est_rel_card = random.choice(most_common_vals_freqs)\n",
" est_abs_card = round(est_rel_card * tot_number_tuples)\n",
" # TODO query its actual absolute cardinality (number of cars that have prix = value)\n",
" act_abs_card = 0 # TODO\n",
" # % of relative error\n",
" rel_error = abs(est_abs_card - act_abs_card) / act_abs_card * 100\n",
" # display results\n",
" print(f'{value:8}: estimated={est_abs_card}, actual={act_abs_card}, error={rel_error:5.2f}%')"
]
},
{
"cell_type": "markdown",
"id": "f3a8b2e3-0413-47c1-9fae-79496bdba2a3",
"metadata": {
"deletable": true,
"editable": true,
"frozen": false
},
"source": [
"On constate quelques écarts, mais globalement, c'est assez fiable. Une erreur de 10% conduirait le SGBD à choisir la mauvaise stratégie pour évaluer la requête, mais sans causer un lourd fardeau de calcul, car l'autre stratégie n'aurait pas été beaucoup plus rapide.\n",
"\n",
"Voici le calcul précédent mis dans une fonction plus générale qui servira plus loin."
]
},
{
"cell_type": "code",
"execution_count": null,
"id": "cab1e312-ae54-4440-a438-a90f6934b1d2",
"metadata": {
"deletable": true,
"editable": true,
"frozen": false,
"scrolled": true
},
"outputs": [],
"source": [
"def getMostCommonValsFreqs(tablename, attribute):\n",
" \"returns the most common values and their frequencies as a table\"\n",
" query = f\"\"\"SELECT\n",
" unnest(most_common_vals::text::int[]) AS val,\n",
" unnest(most_common_freqs) AS freq\n",
" FROM pg_stats WHERE tablename='{tablename}' AND attname='{attribute}'\"\"\"\n",
" result = %sql {{query}}\n",
" return result\n",
"\n",
"print(getMostCommonValsFreqs('secondhandcars', 'prix'))"
]
},
{
"cell_type": "markdown",
"id": "b1480add-512c-4cdb-8bb6-490c84bc7819",
"metadata": {
"deletable": true,
"editable": true,
"frozen": false
},
"source": [
"Ces valeurs fréquentes sont comme retirées des données avant de construire l'histogramme. C'est à dire qu'en rajoutant ces valeurs à l'histogramme, les cardinalités des barres redeviendraient plus régulières. Mais on va clarifier et vérifier tout cela. Nous allons vérifier ces informations et mieux comprendre comment PostgreSQL parvient à décider très rapidement s'il est préférable de faire un parcours complet ou d'utiliser les bitmaps de l'index.\n",
"\n",
"### Estimation des cardinalités\n",
"\n",
"Ainsi lorsqu'il y a un index sur une colonne, le SGBD mémorise trois types d'informations complémentaires (métadonnées) :\n",
"- la cardinalité relative estimée des valeurs null,\n",
"- les 100 valeurs les plus fréquentes et leur cardinalité relative approximative,\n",
"- 100 intervalles, chacun approximativement de même cardinalité relative, $\\text{bar\\_rel\\_card}$ qui exclut les valeurs fréquentes.\n",
"\n",
"On a donc avoir l'équation suivante entre toutes ces estimations :\n",
"\n",
"(1) $\\normalsize\\text{est\\_null\\_card} + \\sum_{\\text{most\\_common\\_vals}}\\text{most\\_common\\_freqs} + 100 * \\text{bar\\_rel\\_card} = 1$\n",
"\n",
"C'est à dire que les cardinalités relatives estimées de toutes ces catégories représentent la totalité des données.\n",
"\n",
"On peut donc obtenir $\\text{bar\\_rel\\_card}$ simplement par :\n",
"\n",
"$\\text{bar\\_rel\\_card} = \\Large\\frac{1 - \\text{est\\_null\\_card} + \\sum_{\\text{most\\_common\\_vals}}\\text{most\\_common\\_freqs}}{100}$\n",
"\n",
"NB: le dénominateur, 100 est le nombre de barres par défaut dans PostgreSQL. Il peut être modifié par l'utilisateur, voir __[default_statistics_target](https://www.postgresql.org/docs/current/runtime-config-query.html#GUC-DEFAULT-STATISTICS-TARGET)__.\n",
"\n",
"Compléter le programme suivant qui calcule $\\text{bar\\_rel\\_card}$. Notez qu'on le rend polyvalent avec des paramètres. On a placé le calcul des valeurs fréquentes dans une fonction."
]
},
{
"cell_type": "code",
"execution_count": null,
"id": "ff9c39d2-0601-441a-ab71-8e5bbee5227f",
"metadata": {
"deletable": true,
"editable": true,
"frozen": false
},
"outputs": [],
"source": [
"def getBarRelCardinality(tablename, attribute):\n",
" \"returns the estimated cardinality of each bar in the equidepth histogram of attribute in tablename\"\n",
" # get the null cardinality estimation from the metadata\n",
" est_null_card = 0 # TODO\n",
" # get only the most common values frequencies\n",
" results = %sql SELECT unnest(most_common_freqs) AS freq FROM pg_stats WHERE tablename='{{tablename}}' AND attname='{{attribute}}'\n",
" # compute 1 - null cardinality - sum(all frequencies)\n",
" est_card_sum = 1.0 # TODO\n",
" # get the number of bars in the histogram = 1 - number of bounds\n",
" query = f\"\"\"SELECT (SELECT COUNT(*)\n",
" FROM unnest(histogram_bounds::text::int[])) AS count\n",
" FROM pg_stats WHERE tablename='{tablename}' AND attname='{attribute}'\"\"\"\n",
" bar_count = 1 # TODO number of bars obtained from the query, but beware, query returns the number of bounds\n",
" # divide by the number of bars\n",
" # TODO\n",
" return est_card_sum\n",
"\n",
"bar_rel_card = getBarRelCardinality('secondhandcars', 'prix')\n",
"print(f'relative cardinality of each bar in the histogram = {bar_rel_card:.6f}')"
]
},
{
"cell_type": "markdown",
"id": "7808ae3d-960c-4977-a03b-a6cc1f2dd3e0",
"metadata": {
"deletable": true,
"editable": true,
"frozen": false
},
"source": [
"Voila la cardinalité relative estimée de chaque barre dans l'histogramme equidepth géré par PostgreSQL.\n",
"\n",
"On va maintenant vérifier la précision des estimations sur des plages de données, pour des conditions de filtrage comme `WHERE prix BETWEEN b1 AND b2`. Pour cela, il faut appliquer l'équation (1). Donc additionner toutes les cardinalités relatives des valeurs fréquentes qui font partie de l'intervalle, et y ajouter le nombre de barres qui sont dans l'intervalle.\n",
"\n",
"Voici un schéma de la situation. L'histogramme contient un certain nombre de barres pas toutes dessinées, et les bornes b1 et b2 sont quelque part dans ces barres. La barre du début d'intervalle, en rose est coupée, comme la barre de fin en orange. Les barres en vert sont entièrement incluses dans l'intervalle.\n",
"\n",
"![](data:image/svg+xml;utf8,<svg xmlns=\"http://www.w3.org/2000/svg\" width=\"400\" viewBox=\"-2 -1 60 14.2\"><g transform=\"translate(-4,-2.4)\" style=\"fill-opacity:1;stroke:black;stroke-width:0.25;stroke-linecap:round;font-size:3px;\"><rect style=\"fill:lightgray;\" width=\"11.2\" height=\"7.9\" x=\"0.8\" y=\"2.6\"/><rect style=\"fill:lightpink;\" width=\"6.6\" height=\"7.9\" x=\"12\" y=\"2.6\"/><rect style=\"fill:lightgreen;\" width=\"9\" height=\"7.9\" x=\"18.5\" y=\"2.6\"/><rect style=\"fill:lightgreen;\" width=\"10\" height=\"7.9\" x=\"27.5\" y=\"2.6\"/><rect style=\"fill:lightgreen;\" width=\"7\" height=\"7.9\" x=\"37.5\" y=\"2.6\"/><rect style=\"fill:gold;\" width=\"12\" height=\"7.9\" x=\"44\" y=\"2.6\"/><rect style=\"fill:lightgray;\" width=\"8\" height=\"7.9\" x=\"56\" y=\"2.6\"/><rect style=\"fill:chartreuse;fill-opacity:0.4;\" width=\"32\" height=\"10\" x=\"15\" y=\"1.6\"/><text x=\"13\" y=\"15.3\">b1</text><text x=\"45\" y=\"15.3\">b2</text></g></svg>)
\n",
"\n",
"Chaque barre représente la cardinalité relative obtenue plus haut, cellule #75. Il faut donc comptabiliser une partie de la barre rose, toutes les barres vertes et une partie de la barre orange. Pour ces deux barres extrêmes, on considère que les données sont réparties uniformément, et donc c'est en proportion de la couverture de la barre par l'intervalle. Il faut également ajouter les cardinalités relatives des valeurs fréquentes qui sont comprises entre b1 et b2.\n",
"\n",
"Voici un programme à compléter. Il doit retourner la cardinalité relative de la condition `WHERE attribute BETWEEN b1 AND b2`."
]
},
{
"cell_type": "code",
"execution_count": null,
"id": "7b776ba3-100c-4d44-8817-af442a871478",
"metadata": {
"deletable": true,
"editable": true,
"frozen": false
},
"outputs": [],
"source": [
"def getHistogramBounds(tablename, attribute):\n",
" \"returns the bounds of the equidepth histogram of attribute in tablename\"\n",
" # query histogram_bounds from database\n",
" query = f\"\"\"SELECT unnest(histogram_bounds::text::int[]) AS bounds\n",
" FROM pg_stats WHERE tablename='{tablename}' AND attname='{attribute}'\"\"\"\n",
" bounds = %sql {{query}}\n",
" # build histogram_bars = list of dict{from, to, height, text}\n",
" histogram_bars = []\n",
" b1 = None\n",
" for b2 in bounds:\n",
" if b1 is not None:\n",
" histogram_bars.append({'from': b1.bounds, 'to': b2.bounds, 'height': 1, 'text': f']{b1.bounds}, { b2.bounds}]'})\n",
" b1 = b2\n",
" return histogram_bars\n",
"\n",
"def getIntervalRelativeCardinalityV1(tablename, attribute, b1, b2):\n",
" \"computes the estimation of the relative cardinality of attribute between b1 and b2\" \n",
" # parameters errors check\n",
" if b1 > b2: return 0.0\n",
" # future result\n",
" cardinality = 0.0\n",
" # histogram bars and cardinality\n",
" histogram_bars = getHistogramBounds(tablename, attribute)\n",
" bar_rel_card = getBarRelCardinality(tablename, attribute)\n",
" # count histogram bars that cover interval [b1, b2]\n",
" for bar in histogram_bars:\n",
" # TODO cardinality += intersection of [b1, b2] and bar * bar_rel_card\n",
" # add cardinality of common values that are between b1 and b2\n",
" most_common_vals_freqs = getMostCommonValsFreqs(tablename, attribute)\n",
" # TODO loop on pairs (val,freq) in most_common_vals_freqs\n",
" # result\n",
" return cardinality\n",
"\n",
"\n",
"# apply this on some examples\n",
"for b1,b2 in [(0, 1000), (1000, 2000), (2000, 3000), (500, 5000), (1200, 4500), (5000, 12000), (8000, 20000)]:\n",
" # estimated cardinality, relative and absolute\n",
" est_rel_card = getIntervalRelativeCardinalityV1('secondhandcars', 'prix', b1, b2)\n",
" est_abs_card = round(est_rel_card * tot_number_tuples)\n",
" # actual cardinality\n",
" act_abs_card = 1 # TODO count cars whose prix is in [b1, b2]\n",
" # % of relative error\n",
" rel_error = abs(est_abs_card - act_abs_card) / act_abs_card * 100\n",
" # display results\n",
" print(f'prix between {b1} and {b2}:\\t{est_rel_card:.3} = {est_abs_card} tuples, actual = {act_abs_card} tuples, error={rel_error:5.2f}%')"
]
},
{
"cell_type": "markdown",
"id": "02377901-37d2-486a-96d7-e702ccafc007",
"metadata": {
"deletable": true,
"editable": true,
"frozen": false
},
"source": [
"Normalement, vos taux d'erreur doivent être assez petits, moins de 5%. Si vous avez de plus grandes erreurs, il y a des chances que ça soit votre programme qui calcule mal. Avez-vous bien compté les barres, et celles qui sont partiellement couvertes ? Ajoutez des affichages pour la mise au point.\n",
"\n",
"C'est de cette manière que PostgreSQL évalue la *sélectivité* des conditions de filtrage. Il décide si un parcours complet est préfèrable ou l'utilisation de l'index. L'algorithme est très rapide, même s'il y a 100 valeurs fréquentes et 100 barres d'histogramme.\n",
"\n",
"L'algorithme de `getIntervalRelativeCardinalityV1` fonctionne bien, mais dans certains cas de distributions très particulières des données, les bornes de l'histogramme sont confondues, comme empilées au même endroit pour représenter des densités exceptionnelles. Dans ces cas, l'algorithme ne va pas car il s'arrête au premier intervalle contenant b2, alors qu'il peut y en avoir plusieurs à la suite.\n",
"\n",
"Voici une autre idée, pour une version de la fonction. Elle consiste à écrire que la cardinalité de [b1, b2], $card(\\,[b1, b2]\\,) = card(\\,]{-\\infty}, b2]\\,) - card(\\,]{-\\infty}, b1[\\,)$. C'est à dire qu'on va calculer la cardinalité relative en dessous d'une borne, ou jusqu'à une borne, faire ça pour b1 et b2 et soustraire les deux cardinalités.\n",
"\n",
"On commence par la fonction qui calcule la cardinalité en dessous de (strict=True) ou jusqu'à (strict=False) une borne b."
]
},
{
"cell_type": "code",
"execution_count": null,
"id": "bc8e00be-7bcd-4897-a68f-b54da48aca72",
"metadata": {
"deletable": true,
"editable": true,
"frozen": false
},
"outputs": [],
"source": [
"def getEstimatedCardinalityLessThan(tablename, attribute, b, strict):\n",
" \"retourne la cardinalité estimée de ]-∞, b[ si strict=True, sinon ]-∞, b]\"\n",
" # histogram bars and cardinality\n",
" histogram_bars = getHistogramBounds(tablename, attribute)\n",
" bar_rel_card = getBarRelCardinality(tablename, attribute)\n",
" # count full and partial bars ]b1, b2] so that b2 <= b\n",
" bar_nb = 0 # TODO loop on histogram_bars\n",
" # relative cardinality of all bars before b, and including b if strict is False\n",
" cardinality = bar_nb * bar_rel_card\n",
" # common values less than (or equal to if strict is False) v\n",
" most_common_vals_freqs = getMostCommonValsFreqs(tablename, attribute)\n",
" # TODO loop on pairs (val,freq) in most_common_vals_freqs\n",
" # final result\n",
" return cardinality\n",
"\n",
"# test this on some examples\n",
"import random\n",
"for b in sorted([int(random.weibullvariate(10000, 1)) for _ in range(6)]):\n",
" # estimated cardinality, relative and absolute\n",
" est_rel_card = getEstimatedCardinalityLessThan('secondhandcars', 'prix', b, False) # try with strict=True\n",
" est_abs_card = round(est_rel_card * tot_number_tuples)\n",
" # actual cardinality, put < when strict is True\n",
" act_abs_card = 1 # TODO count cars whose prix is less or equal to b # or less than if strict is True\n",
" # % of relative error\n",
" rel_error = abs(est_abs_card - act_abs_card) / act_abs_card * 100\n",
" # display results\n",
" print(f'prix < {b}:\\t{est_rel_card:.3} = {est_abs_card} tuples, actual = {act_abs_card} tuples, error={rel_error:5.2f}%')"
]
},
{
"cell_type": "markdown",
"id": "bbdde1af-77fc-4c61-8b02-a6a8c39b3564",
"metadata": {
"deletable": true,
"editable": true,
"frozen": false
},
"source": [
"Noter que l'erreur peut être très grande lorsque la borne est basse (<100), car il n'y a qu'une seule barre dans l'histogramme pour représenter un grand nombre de voitures. Mais ce n'est pas très grave pour la suite. D'abord, il y a peu de n-uplets dans cette zone et d'autre part, si on cherche sur un intervalle [b1, b2], cette erreur sur l'une des bornes s'annulera avec celle de l'autre.\n",
"\n",
"Il reste à calculer la cardinalité d'un intervalle [b1, b2] en soustrayant la cardinalité jusqu'à b2 inclus et celle inférieure à b1."
]
},
{
"cell_type": "code",
"execution_count": null,
"id": "65f41153-ab40-4c7f-a9b6-fcbff26d7af9",
"metadata": {
"deletable": true,
"editable": true,
"frozen": false
},
"outputs": [],
"source": [
"def getIntervalRelativeCardinalityV2(tablename, attribute, b1, b2):\n",
" \"retourne la cardinalité estimée de [b1, b2]\"\n",
" cardb1 = 0 # TODO call getEstimatedCardinalityLessThan on b1\n",
" cardb2 = 0 # TODO call getEstimatedCardinalityLessThan on b2\n",
" return cardb2 - cardb1\n",
"\n",
"\n",
"# apply this on some examples\n",
"for b1,b2 in [(0, 1000), (1000, 2000), (2000, 3000), (500, 5000), (1200, 4500), (5000, 12000), (8000, 20000)]:\n",
" # estimated cardinality, relative and absolute\n",
" est_rel_card = getIntervalRelativeCardinalityV2('secondhandcars', 'prix', b1, b2)\n",
" est_abs_card = round(est_rel_card * tot_number_tuples)\n",
" # actual cardinality\n",
" act_abs_card = 1 # TODO\n",
" # % of relative error\n",
" rel_error = abs(est_abs_card - act_abs_card) / act_abs_card * 100\n",
" # display results\n",
" print(f'prix between {b1} and {b2}:\\t{est_rel_card:.3} = {est_abs_card} tuples, actual = {act_abs_card} tuples, error={rel_error:5.2f}%')"
]
},
{
"cell_type": "markdown",
"id": "4dbce867-5ea4-404b-a2dc-3b0171443df0",
"metadata": {
"deletable": true,
"editable": true,
"frozen": false
},
"source": [
"Les résultats doivent être très proches de ceux obtenus par la méthode V1. Les données de cette base ne permettent pas de justifier le bien-fondé de la seconde méthode, mais ils apparaîssent très nettement avec des distributions très inégales."
]
},
{
"cell_type": "markdown",
"id": "e6bef33f-6a3a-4cd8-aab1-64891c3d336e",
"metadata": {
"deletable": true,
"editable": true,
"frozen": false
},
"source": [
"## Partie 2 : Requêtes flexibles\n",
"\n",
"Vous allez maintenant écrire vos premières requêtes flexibles. Vous allez considérer que vous cherchez la voiture la moins chère possible, ayant le moins de kilomètres possible et la plus récente possible. Vous allez définir les fonctions caractéristiques des ensembles flous correspondant à ces trois notions en utilisant des fonctions écrites en pl/pgsql.\n",
"\n",
"Nous allons utiliser les index, afin d'optimiser le temps de calcul des requêtes. Dans la cellule suivante, faites créer deux index, l'un sur le kilométrage (colonne `km`), l'autre sur l'année (colonne `annee`). Pensez aux options qui permettent d'éviter les erreurs si ces index existent déjà."
]
},
{
"cell_type": "code",
"execution_count": null,
"id": "d4832c49-3ea3-4a38-9f11-d2483b5f5175",
"metadata": {
"deletable": true,
"editable": true,
"frozen": false
},
"outputs": [],
"source": [
"# TODO (re)create index idx_km on km\n",
"# TODO (re)create index idx_annee on annee"
]
},
{
"cell_type": "markdown",
"id": "4cf3409c-6b34-4683-a2b2-9d0adac421ac",
"metadata": {
"deletable": true,
"editable": true,
"frozen": false
},
"source": [
"### Exemple : Faible kilométrage\n",
"\n",
"Voici l'exemple d'une fonction enregistrée dans le SGBD. "
]
},
{
"cell_type": "code",
"execution_count": null,
"id": "dbae454b-1867-4afb-9378-2063bb574d7f",
"metadata": {
"deletable": true,
"editable": true,
"frozen": false
},
"outputs": [],
"source": [
"%%sql\n",
"CREATE OR REPLACE FUNCTION low_mileage(km integer) RETURNS float AS\n",
"$$\n",
"BEGIN\n",
" IF (km IS NULL) THEN \n",
" RETURN 0.0;\n",
" END IF;\n",
" IF (km >= 15000) THEN \n",
" RETURN 0.0;\n",
" END IF;\n",
" RETURN (15000 - CAST(km AS FLOAT))/15000;\n",
"END;\n",
"$$ \n",
"LANGUAGE plpgsql"
]
},
{
"cell_type": "markdown",
"id": "fb4ab9fa-57c6-4d52-b9be-5f766816540f",
"metadata": {
"deletable": true,
"editable": true,
"frozen": false
},
"source": [
"Voici l'application de cette fonction à plusieurs kilométrages."
]
},
{
"cell_type": "code",
"execution_count": null,
"id": "097edf2e-f83f-41e9-96d0-7b4489490c51",
"metadata": {
"deletable": true,
"editable": true,
"frozen": false
},
"outputs": [],
"source": [
"for km in [500, 2000, 3000, 8000, 20000]:\n",
" result = %sql SELECT low_mileage({{km}}) AS mu\n",
" print(f\"µlow_mileage({km} km) = {result[0].mu:.3f}\")"
]
},
{
"cell_type": "markdown",
"id": "73c03bfb-13f4-4945-9276-edbf3f16a088",
"metadata": {
"deletable": true,
"editable": true,
"frozen": false
},
"source": [
"C'est à dire qu'un kilométrage de 8000 km n'est pas pleinement « faible », il l'est seulement « moyennement ». La fonction $\\mu_{\\text{low mileage}}(km)$ est linéaire par morceaux, valant 1 pour 0 km et valant 0 pour 15000 km et au delà.\n",
"\n",
"
"
]
},
{
"cell_type": "markdown",
"id": "92afc5ab-9ef6-49b3-890f-b58eaef7dcbe",
"metadata": {
"deletable": true,
"editable": true,
"frozen": false
},
"source": [
"Voici un exemple d'utilisation de cette fonction dans une requête plus complète."
]
},
{
"cell_type": "code",
"execution_count": null,
"id": "d356be6c-17c5-4e5b-9993-4422840cefbb",
"metadata": {
"deletable": true,
"editable": true,
"frozen": false,
"scrolled": true
},
"outputs": [],
"source": [
"%%sql\n",
"SELECT COUNT(*), km, round(low_mileage(km)::numeric, 3) AS mu\n",
"FROM secondhandcars\n",
"WHERE low_mileage(km) > 0.9\n",
"GROUP BY km\n",
"ORDER BY mu DESC"
]
},
{
"cell_type": "markdown",
"id": "cdd5ff91-6cb8-498d-b079-a588f0356b1b",
"metadata": {
"deletable": true,
"editable": true,
"frozen": false
},
"source": [
"Notez qu'un paramètre `null` retourne 0.\n",
"\n",
"Une remarque qu'on peut se faire est que les fonctions d'appartenance ne vérifient pas la colonne qu'on leur soumet ; c'est une source d'erreurs."
]
},
{
"cell_type": "markdown",
"id": "85a6ff59-8a55-4194-a130-6ad8a3f5e157",
"metadata": {
"deletable": true,
"editable": true,
"frozen": false
},
"source": [
"### Fonctions d'appartenance floue\n",
"\n",
"Définissez maintenant, dans les cellules suivantes les fonctions demandées. Vous avez toute liberté pour définir les bornes floues : supports et noyaux.\n",
" \n",
"#### Voitures pas chères\n",
"\n",
"Il faudrait définir une fonction qui se comporte ainsi, mais à vous de choisir la borne.\n",
" \n",
"
"
]
},
{
"cell_type": "code",
"execution_count": null,
"id": "a5eef68e-6450-4dab-b339-2f6a05693024",
"metadata": {
"deletable": true,
"editable": true,
"frozen": false
},
"outputs": [],
"source": [
"%%sql\n",
"CREATE OR REPLACE FUNCTION cheap_price(prix integer) RETURNS float AS\n",
"$$\n",
"BEGIN\n",
" RETURN CASE\n",
" WHEN prix IS NULL THEN 0.0\n",
" WHEN prix < 3 THEN 1.0\n",
" ELSE 0.5\n",
" END;\n",
"END;\n",
"$$ \n",
"LANGUAGE plpgsql"
]
},
{
"cell_type": "markdown",
"id": "26d7cb3f-8b87-4631-af5f-b9c39fe9570a",
"metadata": {
"deletable": true,
"editable": true,
"frozen": false
},
"source": [
"Vous avez remarqué la forme plus compacte pour une conditionnelle multiple.\n",
"\n",
"Dans la cellule suivante, écrivez une requête SQL recherchant les voitures de la marque Saab et ayant un degré $\\mu_{\\text{cheap\\_price}}>0.8$."
]
},
{
"cell_type": "code",
"execution_count": null,
"id": "807928d2-678f-4f21-abd5-4e70b509a15c",
"metadata": {
"deletable": true,
"editable": true,
"frozen": false
},
"outputs": [],
"source": [
"%sql SELECT 'TODO'"
]
},
{
"cell_type": "markdown",
"id": "af78209a-9def-4e55-9ab8-30e863bf4086",
"metadata": {
"deletable": true,
"editable": true,
"frozen": false
},
"source": [
"#### Voitures ayant un kilométrage modéré\n",
"\n",
"On voudrait une fonction d'appartenance floue ressemblant à ce trapèze, à vous de choisir toutes les bornes.\n",
"\n",
"
"
]
},
{
"cell_type": "code",
"execution_count": null,
"id": "e84175ce-76e9-494b-8d4f-c5db395c61d7",
"metadata": {
"deletable": true,
"editable": true,
"frozen": false
},
"outputs": [],
"source": [
"%%sql\n",
"CREATE OR REPLACE FUNCTION moderate_mileage(km integer) RETURNS float AS\n",
"$$\n",
"BEGIN\n",
" RETURN CASE\n",
" WHEN km IS NULL THEN 0.0\n",
" ELSE 0.0\n",
" END;\n",
"END;\n",
"$$\n",
"LANGUAGE plpgsql"
]
},
{
"cell_type": "markdown",
"id": "b5736baa-c86c-430e-9bdb-d726c6d900a9",
"metadata": {
"deletable": true,
"editable": true,
"frozen": false
},
"source": [
"Dans la cellule suivante, écrivez une requête SQL recherchant les voitures de 2008, roulant au GPL (colonne `carburant`) et ayant un kilométrage modérée à plus de $0.8$."
]
},
{
"cell_type": "code",
"execution_count": null,
"id": "88cceed9-d035-4e2d-9044-0aefdee64632",
"metadata": {
"deletable": true,
"editable": true,
"frozen": false
},
"outputs": [],
"source": [
"%sql SELECT 'TODO'"
]
},
{
"cell_type": "markdown",
"id": "d65f9f26-95ee-48f5-9214-bc4780a1a317",
"metadata": {
"deletable": true,
"editable": true,
"frozen": false
},
"source": [
"#### Voitures récentes\n",
"\n",
"On voudrait une fonction d'appartenance floue basée sur l'année qui qualifie les voitures récentes. Cependant l'année, dans cette table, n'est pas un entier mais une chaîne de caractère, un `varchar`. Donc on ne peut pas utiliser de fonction mathématique linéaire, sauf en analysant la chaîne pour la convertir en entier ce qui ne serait pas très rapide sur une grande base de données. Il est préférable de faire des catégories.\n",
"\n",
"D'autre part, la dernière année dans la table est 2011, donc une voiture considérée comme « récente » dans ce TP, est relative à cette date."
]
},
{
"cell_type": "code",
"execution_count": null,
"id": "42a64390-b37c-4aef-9ace-33745eb353fa",
"metadata": {
"deletable": true,
"editable": true,
"frozen": false
},
"outputs": [],
"source": [
"%%sql\n",
"CREATE OR REPLACE FUNCTION recent_car(annee varchar) RETURNS float AS\n",
"$$\n",
"BEGIN\n",
" RETURN CASE\n",
" WHEN annee IS NULL THEN 0.0\n",
" WHEN annee='2011' THEN 1.0\n",
" ELSE 0.0\n",
" END;\n",
"END;\n",
"$$ \n",
"LANGUAGE plpgsql"
]
},
{
"cell_type": "markdown",
"id": "4f75909d-c377-4e96-9def-c6595ea03938",
"metadata": {
"deletable": true,
"editable": true,
"frozen": false
},
"source": [
"Dans la cellule suivante, écrivez une requête SQL recherchant les voitures récentes (µ>0.8), de moins de 90 ch et ayant 2 portes."
]
},
{
"cell_type": "code",
"execution_count": null,
"id": "4303e1a6-9641-40e1-8f7b-0253909c912e",
"metadata": {
"deletable": true,
"editable": true,
"frozen": false
},
"outputs": [],
"source": [
"%sql SELECT 'TODO'"
]
},
{
"cell_type": "markdown",
"id": "14fb0842-77e6-4107-b834-615023f79ee8",
"metadata": {
"deletable": true,
"editable": true,
"frozen": false
},
"source": [
"### Conditions de sélection floues multiples\n",
"\n",
"Dans les questions précédentes, il n'y avait qu'un seul critère d'appartenance flou recherché avec des critères non-flous. Voyons comment écrire des requêtes conjonctives floues. Si on a 3 fonctions floues, $ft1$, $ft2$ et $ft3$ sur trois attributs $a1$, $a2$ et $a3$, on peut programmer ceci pour obtenir les n-uplets qui satisfont la conjonction des trois fonctions à un degré > 0.8 :\n",
"```\n",
"SELECT * FROM secondhandcars WHERE ft1(a1) > 0.8 AND ft2(a2) > 0.8 AND ft3(a3) > 0.8\n",
"```\n",
"C'est une écriture « expansée » pour la T-norme $\\min$. En SQL, SQL, le minimum de plusieurs attributs d’un même n-uplet est obtenu par LEAST et non pas MIN qui cherche la plus petite valeur parmi des n-uplets différents. Donc voici comment écrire la requête floue avec la T-norme.\n",
"```\n",
"SELECT * FROM secondhandcars WHERE LEAST(ft1(a1), ft2(a2), ft3(a3)) > 0.8\n",
"```\n",
"\n",
"Écrivez dans la cellule suivante la requête qui affiche les voitures ayant à la fois un faible kimométrage, un prix faible et une année récente, à µ > 0.2. Il est possible qu'il n'y ait aucun résultat si vos bornes des supports et noyaux de vos fonctions d'appartenance sont trop strictes. Modifiez alors leurs définitions pour arriver à un résultat non vide. "
]
},
{
"cell_type": "code",
"execution_count": null,
"id": "f0c24047-18a8-439d-aeeb-3185c43629b0",
"metadata": {
"deletable": true,
"editable": true,
"frozen": false
},
"outputs": [],
"source": [
"%sql SELECT 'TODO'"
]
},
{
"cell_type": "markdown",
"id": "5b16eb5b-e05f-43d0-a4f4-d6fa25e8c708",
"metadata": {
"deletable": true,
"editable": true,
"frozen": false
},
"source": [
"### Analyse des plans d'exécution\n",
"\n",
"Écrivez dans la cellule suivante la requête qui affiche le plan d’exécution d’une requête retournant les voitures de faible kilométrage pour µ > 0.8 :"
]
},
{
"cell_type": "code",
"execution_count": null,
"id": "37d044fe-597f-4649-bc03-ae2b6cc66a2f",
"metadata": {
"deletable": true,
"editable": true,
"frozen": false
},
"outputs": [],
"source": [
"%sql EXPLAIN SELECT 'TODO'"
]
},
{
"cell_type": "markdown",
"id": "ced3b2a2-2c9b-4870-b30a-148e5593df0a",
"metadata": {
"deletable": true,
"editable": true,
"frozen": false
},
"source": [
"Quelle serait la stratégie pour la requête non floue qui demanderait par exemple les voitures dont le kilométrage est inférieur à 12000 km ?"
]
},
{
"cell_type": "code",
"execution_count": null,
"id": "6d4532d5-2674-4002-9796-c1ccd7b60ed2",
"metadata": {
"deletable": true,
"editable": true,
"frozen": false
},
"outputs": [],
"source": [
"%sql EXPLAIN SELECT * FROM secondhandcars WHERE km < 12000"
]
},
{
"cell_type": "markdown",
"id": "ecf63a52-ed5c-4096-a2a9-94a6eca506ff",
"metadata": {
"deletable": true,
"editable": true,
"frozen": false
},
"source": [
"On constate que la requête floue n'utilise pas l'index, au contraire de la requête non-floue.\n",
"\n",
"Faites de même avec une requête floue retournant les voitures pas chères pour µ > 0.8 :"
]
},
{
"cell_type": "code",
"execution_count": null,
"id": "fbecef12-3c3b-469c-9088-38a459b3488d",
"metadata": {
"deletable": true,
"editable": true,
"frozen": false
},
"outputs": [],
"source": [
"%sql EXPLAIN SELECT 'TODO'"
]
},
{
"cell_type": "markdown",
"id": "6da2464c-e540-4747-9793-af01e90b1f72",
"metadata": {
"deletable": true,
"editable": true,
"frozen": false
},
"source": [
"Puis à nouveau, quelle serait une requête non-floue équivalente, par exemple demandant un prix < 7000 :"
]
},
{
"cell_type": "code",
"execution_count": null,
"id": "624866a0-b9b4-4cb8-a849-4c4ac0e29ee4",
"metadata": {
"deletable": true,
"editable": true,
"frozen": false
},
"outputs": [],
"source": [
"%sql EXPLAIN SELECT 'TODO'"
]
},
{
"cell_type": "markdown",
"id": "f950a236-6949-4528-98da-d8e903808a18",
"metadata": {
"deletable": true,
"editable": true,
"frozen": false
},
"source": [
"Ici aussi, l'index est utilisé dans la requête non-floue mais pas la requête floue.\n",
"\n",
"Essayons avec une requête conjonctive, celle avec la T-norme de la cellule #124. Ajoutez-lui `EXPLAIN` dans la cellule suivante pour voir la stratégie utilisée."
]
},
{
"cell_type": "code",
"execution_count": null,
"id": "fe5de7f0-a332-4f34-b3e5-535035200dad",
"metadata": {
"deletable": true,
"editable": true,
"frozen": false
},
"outputs": [],
"source": [
"%sql EXPLAIN SELECT 'TODO'"
]
},
{
"cell_type": "markdown",
"id": "636c84b1-3dd9-4266-950f-925d97a35c80",
"metadata": {
"deletable": true,
"editable": true,
"frozen": false
},
"source": [
"Comparez avec une requête non-floue qui cherche les voitures ayant un kilométrage inférieur à 5000 et un prix inférieur à 5000 et une année supérieure à 2009."
]
},
{
"cell_type": "code",
"execution_count": null,
"id": "51261a02-466b-4539-9fb1-612952862447",
"metadata": {
"deletable": true,
"editable": true,
"frozen": false
},
"outputs": [],
"source": [
"%sql EXPLAIN SELECT 'TODO'"
]
},
{
"cell_type": "markdown",
"id": "b6d7d43b-5638-4e45-9514-8ab45642942f",
"metadata": {
"deletable": true,
"editable": true,
"frozen": false
},
"source": [
"Le problème est que PostgreSQL ne peut pas analyser le comportement des fonctions floues à l'avance. Il n'y a que vous qui sachiez que telle fonction est linéaire par morceaux, par exemple décroissante entre 0 et une certaine valeur, etc.\n",
"\n",
"### Requêtes flexibles dérivées\n",
"\n",
"Heureusement, il y a un moyen d'utiliser l'index, à minima. C'est de construire une requête flexible dérivée. Pour rappel, la dérivation d’une requête flexible consiste à construire la requête « booléenne » retournant l’ensemble des tuples pouvant satisfaire la requête flexible, au mieux ceux d'une coupe alpha, au pire du support, puis à calculer le degré de satisfaction pour ces tuples uniquement. Cela se fait avec une double condition comme ceci :\n",
"```\n",
"SELECT ... WHERE conditions booléenne sur des coupes alpha ou les supports AND conditions sur le degré d'appartenance flou\n",
"```\n",
"Écrivez dans la cellule suivante la requête qui affiche le plan d’exécution d’une requête dérivée retournant les voitures de faible kilométrage pour µ > 0.8. La meilleure réponse est celle qui sélectionne sur une coupe alpha de la fonction floue à 0.8 ; une moins bonne réponse sélectionne tout le support."
]
},
{
"cell_type": "code",
"execution_count": null,
"id": "b027f018-6a3a-41d9-be98-8c789a7b9d68",
"metadata": {
"deletable": true,
"editable": true,
"frozen": false
},
"outputs": [],
"source": [
"%sql EXPLAIN SELECT 'TODO'"
]
},
{
"cell_type": "markdown",
"id": "5a5030a0-b2a0-4563-a1c9-e19f55b3f047",
"metadata": {
"deletable": true,
"editable": true,
"frozen": false
},
"source": [
"Faites de même avec une requête floue retournant les voitures pas chères pour µ > 0.8 :"
]
},
{
"cell_type": "code",
"execution_count": null,
"id": "f1fa47fd-e2b2-4111-a721-1241c8c8a5b3",
"metadata": {
"deletable": true,
"editable": true,
"frozen": false
},
"outputs": [],
"source": [
"%sql EXPLAIN SELECT 'TODO'"
]
},
{
"cell_type": "markdown",
"id": "743c90ae-5cea-4456-8e17-f9401884e3f1",
"metadata": {
"deletable": true,
"editable": true,
"frozen": false
},
"source": [
"De même avec la requête dérivée qui affiche les voitures ayant à la fois un faible kimométrage, un prix faible et une année récente, à µ > 0.2."
]
},
{
"cell_type": "code",
"execution_count": null,
"id": "396daea9-0330-44a7-ab4c-8153b67cc30b",
"metadata": {
"deletable": true,
"editable": true,
"frozen": false
},
"outputs": [],
"source": [
"%%sql\n",
"EXPLAIN SELECT 'TODO'"
]
},
{
"cell_type": "markdown",
"id": "0491c093-c99c-46a0-a868-bc762ac9566b",
"metadata": {
"deletable": true,
"editable": true,
"frozen": false
},
"source": [
"En principe, les plans d'exécution montrent maintenant tous l'utilisation de l'index."
]
},
{
"cell_type": "markdown",
"id": "e23be585-c916-49b8-9a51-ead79dbda21b",
"metadata": {
"deletable": true,
"editable": true,
"frozen": false
},
"source": [
"### Estimation de la cardinalité d'une fonction d'appartenance floue\n",
"\n",
"On poursuit l'étude des fonctions d'appartenance floue et on se pose la question de la détermination rapide de leur cardinalité. Par exemple, combien de voitures satisfont cheap_price(prix) > 0.8 ?\n",
"\n",
"Soit une fonction d'appartenance floue, $\\mu_f(x)$ qui indique le degré d'appartenance de la valeur $x$ à $f$. On souhaite estimer le plus rapidement possible combien de n-uplets de la base de données ont la propriété $x$ qui satisfait $\\mu_f(x) \\ge \\alpha$. Par exemple, combien de voitures ont un kilométrage modéré à plus de 0.8 : $\\mu_{moderate\\_mileage}(km) \\ge 0.8$ ?\n",
"\n",
"Un des moyens de le savoir est de parcourir la table et faire le calcul. Cela donne le résultat exact. C'est ce que fait la requête suivante."
]
},
{
"cell_type": "code",
"execution_count": null,
"id": "ab5c30b5-38f7-4bf8-9303-79ed6dc46902",
"metadata": {
"deletable": true,
"editable": true,
"frozen": false
},
"outputs": [],
"source": [
"%sql SELECT COUNT(*) FROM secondhandcars WHERE moderate_mileage(km) >= 0.8"
]
},
{
"cell_type": "markdown",
"id": "1bf194a2-a97e-4416-a568-36efe031df33",
"metadata": {
"deletable": true,
"editable": true,
"frozen": false
},
"source": [
"Cette requête effectue un parcours intégral des n-uplets de la table et calcule le degré d'appartenance pour chacun. Elle est équivalente au programme suivant, à compléter.\n",
"\n",
"Ce programme commence par la définition en Python de la même fonction d'appartenance floue écrite précédemment en PL/SQL (il faut la traduire en Python en gardant les mêmes calculs). Puis il y a une boucle sur les données, l'évaluation de leur degré µ et le comptage."
]
},
{
"cell_type": "code",
"execution_count": null,
"id": "e5ab6194-76c4-4af6-827f-e09e3a2fec46",
"metadata": {
"deletable": true,
"editable": true,
"frozen": false
},
"outputs": [],
"source": [
"def getMuModerateMileage(km):\n",
" if km is None: return 0.0\n",
" # TODO all cases\n",
" return 0.0\n",
"\n",
"def getActualCardinalityModerateMileage(alpha):\n",
" count = 0\n",
" results = %sql SELECT * FROM secondhandcars\n",
" for row in results:\n",
" # TODO count rows that have getMuModerateMileage >= alpha\n",
" return count\n",
"\n",
"# actual count by the Python function\n",
"actual_count = getActualCardinalityModerateMileage(0.8)\n",
"print(f'actual_count = {actual_count}')"
]
},
{
"cell_type": "markdown",
"id": "3baea7d4-d0fd-44ec-b04e-eaa79394924e",
"metadata": {
"deletable": true,
"editable": true,
"frozen": false
},
"source": [
"Le calcul précédent, SQL ou Python, serait très long sur une grande base de données, et encore plus long si on voulait connaître ces cardinalités sur tous les termes d'un vocabulaire flou (low_mileage, medium_mileage, etc). On se propose de programmer une technique d'estimation très rapide de la cardinalité, sans parcours des données, en utilisant les métadonnées.\n",
"\n",
"Le principe est d'utiliser la fonction `getIntervalRelativeCardinalityV3` définie précédemment. On lui fournit un intervalle $[b1, b2]$ correspondant à la coupe alpha de la propriété floue au degré voulu. La difficulté est donc seulement de déterminer $b1$ et $b2$ pour `moderate_mileage` coupé à 0.8. Heureusement, la fonction d'appartenance floue est linéaire par morceaux, donc facilement inversible, sinon il faudrait résoudre l'équation $\\mu(x)=0.8$ et trouver les deux $x$ qui la satisfont.\n",
"\n",
"On commence par une fonction qui retourne les bornes $b1$ et $b2$ telles que $\\alpha = µ_{moderate\\_mileage}(b1)$ et $\\alpha = µ_{moderate\\_mileage}(b2)$ avec $b1 < b2$. La première est dans la partie gauche entre le support et le noyau, et l'autre est dans la partie droite. Il faut seulement inverser les équations."
]
},
{
"cell_type": "code",
"execution_count": null,
"id": "6c39d80b-f2d2-4d69-b21d-f2ec0dc740ec",
"metadata": {
"deletable": true,
"editable": true,
"frozen": false
},
"outputs": [],
"source": [
"def getBoundsModerateMileageForAlpha(alpha):\n",
" # parameter check\n",
" if alpha <= 0.0 or alpha > 1.0: return None\n",
" # when alpha == 1, return the core bounds\n",
" if alpha == 1.0: return (15000, 50000)\n",
" # solve b1,b2 so that getMuModerateMileage(b1) = getMuModerateMileage(b2) = alpha and b1 < b2\n",
" b1 = 0 # TODO compute b1\n",
" b2 = 1000 # TODO compute b2\n",
" return b1, b2\n",
"\n",
"# print results\n",
"b1, b2 = getBoundsModerateMileageForAlpha(0.8)\n",
"est_rel_card = getIntervalRelativeCardinalityV2('secondhandcars', 'km', b1, b2)\n",
"est_count = round(est_rel_card * tot_number_tuples)\n",
"rel_error = abs(est_count - actual_count) / actual_count * 100\n",
"print(f'est_count = {est_count}, actual_count={actual_count}, error = {rel_error:.1f}%')"
]
},
{
"cell_type": "markdown",
"id": "eec0904a-23fc-4fe0-ab4a-ce2a63936a4e",
"metadata": {
"deletable": true,
"editable": true,
"frozen": false
},
"source": [
"Cette valeur estimée est, en principe, très proche de la véritable valeur. L'intérêt, c'est qu'elle est déterminée extrêmement rapidement en comparaison d'un parcours intégral des données. Dans la base des voitures, il y a très peu de données et les calculs sont très rapides, mais on peut arriver à plusieurs minutes voire bien davantage dans du Big Data.\n",
"\n",
"Cette technique a été utilisée par l'équipe SHAMAN de l'IRISA, pour construire automatiquent et très rapidement des résumés linguistiques de grands jeux de données, c'est à dire générer des phrases décrivant les données à l'aide d'un vocabulaire flou. Par exemple, ici, on pourrait observer que « la plupart des voitures ont un prix faible et un kilométrage moyen ». C'est cela un résumé linguistique flou. Ces travaux ont été publiés, entre autres : G. Smits, P. Nerzic, O. Pivert, M.-J. Lesot. Efficient Generation of Reliable Estimated Linguistic Summaries. In Proc. of the 27th IEEE International Conference on Fuzzy Systems (Fuzz-IEEE'18), Rio de Janeiro, Brazil, 2018. *** Fuzz-IEEE 2018 Best Paper Award *** "
]
},
{
"cell_type": "markdown",
"id": "8ff2344e-d32a-4140-a6c9-3bd5573d207f",
"metadata": {
"deletable": true,
"editable": true,
"frozen": false
},
"source": [
"## Partie 3 : Une approche qualitative de gestion des préférences : « Skyline »\n",
"\n",
"En considérant un ensemble de préférences définies sous la forme de fonctions croissantes (e.g. maximiser la puissance moteur, l’année, etc.) ou décroissantes (e.g. minimiser la consommation, le prix, etc.), l’approche « Skyline » consiste à déterminer l’ensemble des tuples non dominés par un autre tuple selon les préférences exprimées. La skyline donne une liste des n-uplets les plus intéressants, vis à vis d'un ensemble de critères fournis par l'utilisateur.\n",
"\n",
"Pour commencer, rappelez la définition d’une relation de dominance entre deux tuples dans la cellule suivante."
]
},
{
"cell_type": "markdown",
"id": "d76ebeb4-0d7c-4e3e-9562-3e4c9ca510e1",
"metadata": {
"deletable": true,
"editable": true,
"frozen": false
},
"source": [
"✍ \n",
"Un tuple T1 domine un autre tuple T2 si et seulement si TODO\n",
"
"
]
},
{
"cell_type": "markdown",
"id": "cad37bb8-0d7c-4da5-b8fb-d4741186e54f",
"metadata": {
"deletable": true,
"editable": true,
"frozen": false
},
"source": [
"Vous allez implémenter, dans la cellule suivante, l’algorithme de construction de la Skyline sur les tuples de la table SecondHandCars en cherchant à minimiser km et prix, et à maximiser l’année.\n",
"\n",
"Le calcul de la skyline fait appel à la fonction `dominates(row1, row2)` qui applique la définition de la domination. On n'a pas cherché à rendre cette fonction générale, ce qui serait un peu compliqué, donc elle compare uniquement les trois attributs km, prix et année. Les paramètres sont des rangées retournées par la requête, donc ils portent directement les attributs `km`, `prix` et `annee` et on peut écrire `row1.prix`, `row2.km`, etc.\n",
"\n",
"Ensuite, la fonction `getSkyLine()` consiste en une boucle sur la totalité des n-uplets, pour construire peu à peu la liste de ceux qui dominent tous les autres, sans qu'aucun d'entre eux ne domine un autre. Cette liste partielle de n-uplets peut changer à chaque n-uplet parcouru. A chaque tour de boucle sur un n-uplet, il y a un premier filtrage de cette liste pour éliminer ceux de ses n-uplets qui sont dominés par le n-uplet courant. Ensuite, le n-uplet courant n'est conservé que si aucun de ceux de la skyline ne le domine. La liste varie continuellement, en fonction des n-uplets rencontrés et à la fin, c'est la skyline du jeu de données.\n",
"\n",
"Dans le programme ci-dessous, la fonction `getSkyLine()` retourne une paire, les noms des colonnes de la table et la liste des n-uplets. C'est pour permettre un affichage sous forme de table dans Jupyter."
]
},
{
"cell_type": "code",
"execution_count": null,
"id": "395f6646-fb0d-4886-98cf-a23df688afe9",
"metadata": {
"deletable": true,
"editable": true,
"frozen": false
},
"outputs": [],
"source": [
"def dominates(row1, row2):\n",
" \"returns True if t1 dominates t2, else False\"\n",
" # TODO everything\n",
" return False\n",
"\n",
"def getSkyLine():\n",
" \"returns a pair headers (names of the columns) and skyline (rows from the table)\"\n",
" # future list of skyline tuples\n",
" skyline = []\n",
" # loop on every tuple in the table\n",
" results = %sql SELECT * FROM secondhandcars\n",
" for row in results:\n",
" # TODO columns must not be null\n",
" # TODO previous rows will stay in skyline if not dominated by the new one\n",
" # TODO row can be added in skyline only if not dominated by any in the current skyline\n",
" # final result\n",
" return results.keys, skyline\n",
"\n",
"# run the function\n",
"headers, skyline = getSkyLine()\n",
"\n",
"# display results as a table\n",
"import tabulate\n",
"tabulate.tabulate(skyline, tablefmt='html', headers=headers)"
]
},
{
"cell_type": "markdown",
"id": "dc5fd74f-24e0-4a0c-aab9-cd2500077dec",
"metadata": {
"deletable": true,
"editable": true,
"frozen": false
},
"source": [
"Si tout va bien, vous obtiendrez 12 n-uplets. Vérifiez rapidement que chacun possède un attribut qui le rend meilleur vis à vis des critères choisis que les autres n-uplets : la voiture la moins chère, la plus récente, ayant le moins de kilomètres...\n",
"\n",
"## Rendu du TP\n",
"\n",
"Il vous suffit de déposer ce fichier .ipynb sur Moodle, dans l'espace de cours. Auparavant, il est demandé d'exécuter toutes les cellules puis d'enregistrer le cahier : menu Run, Run All Cells. Le fichier fait environ 5 à 6 Mo."
]
}
],
"metadata": {
"kernelspec": {
"display_name": "Python 3 (ipykernel)",
"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.11.2"
}
},
"nbformat": 4,
"nbformat_minor": 5
}