Différences

Ci-dessous, les différences entre deux révisions de la page.

--- site:enseignement:master:bdle:tmes:sqlrecursif [08/12/2016 17:41] – créée amann
+++ site:enseignement:master:bdle:tmes:sqlrecursif [19/10/2017 11:06] (Version actuelle) – hubert
@@ Ligne 1: / Ligne 1: @@
-====== Requêtes hiérarchiques, Récursivité ======
+{{indexmenu_n>70}}
+====== SQL et récursion ======
 ===== Connexion Oracle =====
-[[http://www-bd.lip6.fr/ens/bdmd2013/index.php/ConnexionOracle]]
+<del>[[http://www-bd.lip6.fr/ens/bdmd2013/index.php/ConnexionOracle]]</del>
+[[site:enseignement:documentation:oracle:connexionoracle]]
+Quelques liens intéressants:
+  * [[https://docs.oracle.com/cd/B19306_01/server.102/b14200/queries003.htm|Requetes hiérarchiques]]
 ===== Chargement de Données =====
-Conectez vous à Oracle et exécutez la commande:
+Conectez vous à Oracle et
+===== Premiers pas =====
+Créez la table myedges:
 <code SQL>
-SQL> @facebook-bdle
+drop table myedges;
+create table myedges (
+       source integer, target integer);
+insert into myedges values (1,2);
+insert into myedges values (2,3);
+insert into myedges values (2,4);
+insert into myedges values (4,5);
 </code>
+==== Questions ====
+----
+**Question 1**: Dessinez le graphe G stocké dans la graphe myedges;
+----
+**Question 2**: Exécutez la requête suivante et expliquez ce qu'elle affiche.
+<code sql>
+SELECT DISTINCT target, level, SYS_CONNECT_BY_PATH(SOURCE, '/') path
+FROM myedges
+START WITH SOURCE=1
+CONNECT BY prior target=SOURCE;
+</code>
+----
+**Question 3**: Affichez tous les pairs de noeuds dans G et la longueur des chemins entre eux (il faut utiliser [[https://docs.oracle.com/cd/B14117_01/server.101/b10759/operators004.htm|CONNECT_BY_ROOT]]). Triez le résultats sour les attributs source et target. Ensuite, affichez également les chemins.
+----
+**Question 4**: Insérez les deux arcs suivants et évaluez à nouveaux les requêtes précédentes (il faudra ajouter le mot clé [[https://docs.oracle.com/cd/B19306_01/server.102/b14200/queries003.htm|NOCYCLE]] après CONNECT BY):
+<code SQL>
+insert into myedges values (5,1);
+insert into myedges values (4,1);
+</code>
+----
+**Question 5**: Affichez tous les pairs de noeuds dans G et la longueur des chemins entre eux ainsi l'information si le chemin est un cycle (.
+----
+**Question 6**: Affichez que tous les cycles (source=target) et leur longueur (utilisez la possibilité de mettre une sous-requête SQL dans la clause FROM d'une requête ou créez une vue). Affichez le nombre de cycles.
+----
+**Question 7**: Affichez pour chaque noeud le nombre de cycles.
+----
+***Question 8**: Exécutez la requête suivante et analysez le résultat. Changez la stratégie de parcours (DEPTH FIRST, BREADTH FIRST) et l'attribut utilisé pour la détection du cycle.
+<code SQL>
+with R2(source,target,l)
+as (
+   select source,target,1 from myedges
+   union all
+   select r.source, m.target, r.l+1  from R2 r, myedges m where m.source=r.target
+)
+search breadth first by source set o1
+cycle target set end to 1 default 0
+select * from R2
+order by o1;
+</code>
+----
+**Question 9**: Ecrivez une requête qui retourne tous les pairs de noeuds et la longueur du plus court chemin.
 ===== Graphe Facebook : =====
@@ Ligne 21: / Ligne 101: @@
 Les clés primaires sont soulignées. Les attributs usr et neighbor dans la table Edges
-sont des clés étrangères. La table Users  contient 4039 utilisateurs, la table Edges contient 88234 arcs.  Le graphe contient 1612010 triangles (voir ce site pour plus d'informations: [[http://snap.stanford.edu/data/egonets-Facebook.html]]). Une description de ces tables peut être obtenue avec les commandes suivantes:
+sont des clés étrangères. La table Users  contient 4039 utilisateurs, la table Edges contient 88234 arcs.  Le graphe contient 1612010 triangles (voir ce site pour plus d'informations: [[http://snap.stanford.edu/data/egonets-Facebook.html]]). Exécutez la commande suivante:
 <code SQL>
+@facebook-bdle
 desc Users
 desc Edges
@@ Ligne 30: / Ligne 110: @@
 Par défaut le graphe est dirigé (e.g on stocke dans Edges seulement les arcs a → b sans stocker aussi les arcs b → a).
-==== Question 1 : ====
+==== Questions ====
-Écrivez une requête SQL sans récursivité qui retourne les voisins de l'utilisateurs 'Kendall' (il existe une seule personne avec ce nom), en considérant que le graphe est dirigé. Écrivez la même requête en considérant que le graphe est non-dirigé.
+----
+**Question 1** :
+Écrivez une requête SQL sans récursivité qui retourne le nom des amis (voisins) de l'utilisateur 'Kendall' (il existe une seule personne avec ce nom), en considérant que le graphe est dirigé. Écrivez la même requête en considérant que le graphe est non-dirigé.
 Résultat: graphe dirigé 7 lignes, graphe non dirigé 9 lignes
-==== Question 2 : ====
-Écrivez une requête SQL sans récursivité pour connaître les noms des amis des amis de Kendall (à distance 2 de Kendall), en considérant d'abord que le graphe est dirigé. Même question pour un graphe non dirigé.
-Résultat: graphe dirigé 52 lignes, graphe non dirigé 548 lignes
+----
+**Question 2 **:
+Écrivez une requête SQL sans récursivité pour connaître les noms des amis des amis de Kendall (à distance 2 de Kendall), en considérant d'abord que le graphe est dirigé et ensuite non dirigé.
+Résultat: graphe dirigé 52 lignes, graphe non dirigé 521 lignes
+----
+**Question 3** :
+Donnez une requête hiérarchique (clause CONNECT BY) qui retourn les noms des utilisateurs atteignables dans le graphe dirigé à une distance donnée à partir de l'utilisateur 'Kendall'.
+Essayez la requête pour plusieurs distances (pour distance 2 vérifiez que vous obtenez le même résultat que pour la question 2).
-==== Question 3 : ====
-Donnez les noms des utilisateurs atteignables à une distance donnée  à partir de l'utilisateur 'Kendall'. Essayez la requête pour plusieurs distances (pour distance 2 vérifiez que vous obtenez le même résultat que pour la question 2).  Donnez une solution avec une requête hiérarchique (clause CONNECT BY) et une version récursive (clause WITH). Le graphe est considéré comme étant dirigé.
 Résultat: 52 lignes pour la profondeur 2
-==== Question 4 : ====
-Affichez tous les chemins de longueur inférieure ou égale à une distance donnée entre 'Kendall' et 'Ricci' en utilisant CONNECT BY.  Les requêtes doivent afficher pour chaque chemin sa description et sa longueur.  A titre d'exemple, un chemin possible entre Kendall et Ricci est :  /Kendall/Shamika/Ricci de longueur 2.  Le graphe est considéré comme étant dirigé (Indication : utiliser SYS_CONNECT_BY_PATH dans la requête hiérarchique). Même question en utilisant une requête récursive (clause WITH). Pour construire le chemin on peut concaténer deux chaînes de caractères en utilisant  || (Exemple: '/' || chaîne  ajoute '/' devant chaîne).
+----
+**Question 3.1** : La question 3 avec une requête récursive (clause WITH).
+----
+**Question 4** :
+Affichez tous les chemins de longueur inférieure ou égale à une distance donnée entre 'Kendall' et 'Ricci' en utilisant CONNECT BY.  Les requêtes doivent afficher pour chaque chemin sa description et sa longueur.  A titre d'exemple, un chemin possible entre Kendall et Ricci est :  /Kendall/Shamika/Ricci de longueur 2.  Le graphe est considéré comme étant dirigé (Indication : utiliser WITH et SYS_CONNECT_BY_PATH dans la requête hiérarchique).
 Résultat: 13 lignes pour profondeur<= 4
-==== Question 5 : ====
+----
-Donnez une requête qui affiche, pour les utilisateurs 'Kendall' et 'Baylee' l'identifiant de chaque utilisateur atteignable à une profondeur d'exploration de maximum 3, avec la longueur du plus court chemin vers cet utilisateur (les degrés de séparation entre Kendall ou Baylee et les autres utilisateurs).   Donnez une solution en utilisant la clause CONNECT BY. (Indication : utiliser la clause CONNECT_BY_ROOT dans la requête hiérarchique). Même question en utilisant  une quête récursive (clause WITH). Le graphe est considéré comme étant dirigé.
+**Question 4.1** : Question 4 en utilisant une requête récursive (clause WITH et sans CONNECT_BY). Pour construire le chemin on peut concaténer deux chaînes de caractères en utilisant  || (Exemple: '/' || chaîne  ajoute '/' devant chaîne).
+----
+**Question 4.2** : Au lieu d'exécuter la requête, on veut obtenir des statistiques sur les coûts. Pour cela, il faut exécuter d'abord la commande suivante, avant de reexécuter la requête:
+<code>
+SET autotrace trace stat
+</code>
+Exécutez la requête précédente (ou d'autres requêtes) et étudiez les statistiques observées:
+Explications :{{https://docs.oracle.com/cd/B10500_01/server.920/a96533/autotrac.htm}}
+Avant de conteinuer, il faut faire:
+<code>
+SET autotrace off
+</code>
+----
+**Question 5** :
+Donnez une requête qui affiche, pour les utilisateurs 'Kendall' et 'Baylee' l'identifiant de chaque utilisateur atteignable à une profondeur d'exploration de maximum 3, avec la longueur du plus court chemin vers cet utilisateur (les degrés de séparation entre Kendall ou Baylee et les autres utilisateurs).   Donnez une solution en utilisant la clause CONNECT BY. (Indication : utiliser la clause CONNECT_BY_ROOT dans la requête hiérarchique). Le graphe est considéré comme étant dirigé.
 Résultat: 154 lignes
-==== Question 6 : ====
+----
+**Question 5.1**: Question 5 en utilisant  une quête récursive (clause WITH).
+----
+**Question 6** :
 Écrivez une requête qui affiche les noms des utilisateurs qui sont atteignables à la fois à partir de 'Kendall' et de 'Donny' par des parcours à une profondeur maximum 3.  Donnez une solution en utilisant la clause WITH.
 Résultat: 223 ligne(s) sélectionnée(s).
-==== Question 7 : ====
+----
+**Question 7** :
 Écrivez en SQL sans récursivité la requête qui calcule le nombre total de triangles contenant l'utilisateur 'Kendall'.  Le graphe sera transformé d'abord dans un graphe non dirigé avec la commande suivante :
 <code SQL>
-Create VIEW edges_view(usr, neighbor) AS( SELECT usr, neighbor FROM edges UNION ALL SELECT neighbor,usr FROM edges);
+Create VIEW edges_view(usr, neighbor) AS (
+   SELECT usr, neighbor FROM edges
+ UNION ALL
+   SELECT neighbor,usr FROM edges
+);
 </code>
 Résultat: 1612010
-==== Question 8 : ====
+----
+**Question 8** :
 Calculez le nombre de triangles contenant 'Kendall' avec une requête hiérarchique (CONNECT BY) et une requête récursive (WITH).
 Résultat: 34
-==== Question 9 (Optionnel) : ====
+----
-Écrivez le code PL/SQL permettant de calculer les noeuds atteignables à partir d'un  utilisateur donné comme paramètre. Vérifiez la procédure avec le script read_start_node_fermeture.sql.
+***Question 8bis**: Calculez l'histogramme du graphe Facebook.
-Créer une table temporaire pour stocker les noeuds distincts rencontrés pendant la traversée:
-On s'arrête lorsqu'il n'y a plus de nouveau noeud à ajouter à la table temporaire.
+----
+**Question 9** (Optionnel) :
+Écrivez le code [[http://infolab.stanford.edu/~ullman/fcdb/oracle/or-plsql.html|PL/SQL]] permettant de calculer les noeuds atteignables à partir d'un  utilisateur donné comme paramètre.
+Le code sera écrit dans le fichier <ff sans-serif>proc_fermeture_transitive.sql</ff>
+Vérifiez la procédure avec le script <ff sans-serif>read_start_node_fermeture.sql</ff>.
+<fc #ff0000>Conseil:</fc> Créer une table temporaire pour stocker les noeuds distincts rencontrés pendant la traversée. Le calcul s'arrête lorsqu'il n'y a plus de nouveau noeud à ajouter à la table temporaire.
 <code SQL>
 CREATE GLOBAL TEMPORARY TABLE fermeture (id INTEGER PRIMARY KEY);
 @proc_fermeture_transitive
 @read_start_node_fermeture
 DROP TABLE fermeture;
 DROP TABLE fermeture;
@@ Ligne 88: / Ligne 227: @@
 Le fichier read_start_node_fermeture.sql est donné à la fin de l'énoncé.
-==== Question 10(Optionnel) : ====
-Écrivez  le code PL/SQL permettant de calculer le nombre de triangles qui contiennent un utilisateur donné comme paramètre. Le code sera écrit dans le fichier proc_compter_triangles.sql. Afin de le tester, utilisez les commandes suivantes :
+----
+**Question 10** (Optionnel) :
+Écrivez  le code [[http://infolab.stanford.edu/~ullman/fcdb/oracle/or-plsql.html|PL/SQL]] permettant de calculer le nombre de triangles qui contiennent un utilisateur donné comme paramètre. Le code sera écrit dans le fichier <ff sans-serif>proc_compter_triangles.sql</ff>. Afin de le tester, utilisez les commandes suivantes :
 <code SQL>
 @proc_compter_triangles
 @read_start_node_triangles
+</code>
-read_start_node_fermeture.sql :
+==== Scriptes d'exécution ====
+<ff sans-serif>read_start_node_fermeture.sql</ff> :
+<code SQL>
 ACCEPT start_user PROMPT "Donnez un nom d'utilisateur : "
 SET SERVEROUTPUT ON
 SET VERIFY OFF
 execute fermeture_transitive('&start_user');
+</code>
-read_start_node_triangles.sql :
+<ff sans-serif>read_start_node_triangles.sql</ff> :
+<code SQL>
 ACCEPT start_user PROMPT "Donnez un nom d'utilisateur : "
 SET SERVEROUTPUT ON
@@ Ligne 109: / Ligne 256: @@
+===== Mandelbrot en SQL récursif =====
+Téléchargez le fichier [[http://canali.web.cern.ch/canali/res/All_Files/SQL_color_Mandelbrot/Mandelbrot_SQL_Oracle_text.sql]] et exécutez le dans un terminal **sqlplus** en plein écran (<ff sans-serif>@Mandelbrot_SQL_Oracle_text</ff>):
-http://www-bd.lip6.fr/wiki/lib/images/smaller.gif
+<code SQL>
+-- Mandelbrot set visualization in SQL for Oracle
+--
+-- Ported to Oracle from the PostgreSQL version https://wiki.postgresql.org/wiki/Mandelbrot_set
+-- Author: Luca.Canali@cern.ch, August 2015
+--
+-- Additional references:
+-- http://thedailywtf.com/articles/Stupid-Coding-Tricks-The-TSQL-Madlebrot
+-- https://en.wikipedia.org/wiki/Mandelbrot_set
+-- https://www.sqlite.org/lang_with.html
+-- https://community.oracle.com/message/3136057
+-- http://xoph.co/20130917/mandelbrot-sql/
+--
+-- Tested on Oracle (SQL*plus) 11.2.0.4 for Linux using Putty as terminal emulator
+--
+-- Oracle SQL*plus page setup and formatting parameters
+set verify off
+set lines 250
+set pages 999
+-- Configuration parameters for the Mandelbrot set calculation
+-- Edit to change the region displayed and/or resolution by changing the definitions here below
+-- Edit your terminal screen resolution and/or modify XPOINTS and YPOINTS so that the image fits the screen
+define XMIN=-2.0
+define YMIN=-1.4
+define XMAX=0.5
+define YMAX=1.4
+define XPOINTS=150
+define YPOINTS=80
+define XSTEP="(&XMAX - &XMIN)/(&XPOINTS - 1)"
+define YSTEP="(&YMAX - &YMIN)/(&YPOINTS - 1)"
+-- Visualization parameters
+define PALETTESTRING=" .,,,-----++++%%%%@@@@#### "
+define MAXITER="LENGTH('&PALETTESTRING')"
+define ESCAPE_VAL=4
+WITH
+   XGEN AS (                            -- X dimension values generator
+        SELECT CAST(&XMIN + &XSTEP * (rownum-1) AS binary_double) AS X, rownum AS IX FROM DUAL CONNECT BY LEVEL <= &XPOINTS),
+   YGEN AS (                            -- Y dimension values generator
+        SELECT CAST(&YMIN + &YSTEP * (rownum-1) AS binary_double) AS Y, rownum AS IY FROM DUAL CONNECT BY LEVEL <= &YPOINTS),
+   Z(IX, IY, CX, CY, X, Y, I) AS (     -- Z point iterator. Makes use of recursive common table expression
+        SELECT IX, IY, X, Y, X, Y, 0 FROM XGEN, YGEN
+        UNION ALL
+        SELECT IX, IY, CX, CY, X*X - Y*Y + CX, 2*X*Y + CY, I+1 FROM Z WHERE X*X + Y*Y < &ESCAPE_VAL AND I < &MAXITER),
+   MANDELBROT_MAP AS (                       -- Computes an approximated map of the Mandelbrot set
+        SELECT IX, IY, MAX(I) AS VAL FROM Z  -- VAL=MAX(I) represents how quickly the values reached the escape point
+        GROUP BY IY, IX)
+SELECT LISTAGG(SUBSTR('&PALETTESTRING',VAL,1)) WITHIN GROUP (ORDER BY IX) GRAPH  -- LISTAGG concatenates values into rows
+FROM MANDELBROT_MAP                                                              -- PALETTESTRING provides the map values
+GROUP BY IY
+ORDER BY IY DESC;
+</code>
+© [[http://canali.web.cern.ch/canali/res/All_Files/SQL_color_Mandelbrot/Mandelbrot_SQL_Oracle_text.sql]]