Forum Programmation.SQL Modéliser un gros graphe

Posté par Ontologia (site web personnel) le 27 février 2006 à 16:41.

Étiquettes :

fév.

2006

Bonjour, j'ai l'intention de créer un gros graphe, doté de plusieurs millions de sommets (voir plus, peut-être, un jour) et je compte utiliser PostGreSQL (mais c'est un détail).

J'ai lu avec attention qq tutoriels sur les représentation intervalaires d'arborescences, mais évidemment, le concept ne s'applique pas dans mon cas, étant donné que le chemin est de taille non fixé.

Ce graphe devra répondre au cahier des charges suivant :
- Beaucoup d'update
- Beaucoup de select
- Pas mal de delete
- Une base pouvant à terme compter plusieurs Go de données.

Pour info, les sommets comporteront une information pesant peu en taille.

Donc questions :
- PSQL possède t-il un type graphe, ou un type spécial pouvant aider (j'ai pas trouvé dans la doc)
- Parmi les liens que l'on peu trouver sur google, quel sont ceux qui paraissent le plus sérieux ?
- Des conseils éventuels ?
- Comment optimiser les indexs ?

Merci !

# le modele relationnel est peu compatible avec la gestion des graphes

Posté par Mouns (site web personnel) le 28 février 2006 à 06:06. Évalué à 4.

le modele relationnel est incompatible avec ce que tu souhaites faire.

un peu de lecture sur le sujet :
http://linuxfr.org/comments/676329.html#676329
http://linuxfr.org/comments/677172.html#677172
http://linuxfr.org/comments/434244.html#434244 ( thread )

comme je l'est deja expliqué ( mais je ne retrouve plus mon commentaire ), google ne va pas utiliser du SQL mais a du construire un moteur adapté à son besoin.

maintenant si en plus tu veux des ecritures frequentes, cela implique une reconstruction fréquente des indexs ... si le volume d'entrée est suffisament important pour risquer des collisions ... tu risques de passer plus de temps à calculer ton index qu'a en profiter.

je rappelle qu'un quelconque SGBD est essentiellement Read Only ... cas où l'on sait gerer la concurrence. la concurrence en écriture n'est pas encore un sujet maitrisé puisque les solutions tienne en : on écrit à la queuleuleu et si ca merde on previens gentillement le DBA.

Mon conseil va etre au choix :
- soit tu précise ce que tu veux faire pour le faire autrement
- soit tu te tape énormement de livres d'algo et de math
- [^] # Re: le modele relationnel est peu compatible avec la gestion des graphes
  
  Posté par Ontologia (site web personnel) le 28 février 2006 à 17:08. Évalué à 3.
  
  Après réflexions, je vais devoir concevoir un petit SGBD conçu pour faire un graphe.
  
  J'ai commencé à réflechir dessus. J el coderai quand j'aurai le temps. Ca sera du GPL.
  « Il n’y a pas de choix démocratiques contre les Traités européens » - Jean-Claude Junker
  - [^] # Re: le modele relationnel est peu compatible avec la gestion des graphes
    
    Posté par Mouns (site web personnel) le 28 février 2006 à 20:19. Évalué à 3.
    
    il en existe deja un et il est libre ( il y a diverses mentions de son existence dans les commentaires ci-dessus ).
    
    Par contre, je maintiens le fait que si tu précisais ce que tu voulais, tu pourrais avoir des moyens d'eviter de te farcir de la théorie.
    
    si tu souhaites ecrire un SGBD , tu devras lire énormément d'ouvrage sinon tu risque "plein de gros problemes" .
    
    si en plus, tu veux le baser sur des bases de graphes, tu devras en plus savoir transformer une loi mathématique en algorithme "valable".
    - [^] # Re: le modele relationnel est peu compatible avec la gestion des graphes
      
      Posté par Ontologia (site web personnel) le 28 février 2006 à 21:33. Évalué à 3.
      
      En gros, ce que je veux faire, c'est un gros graphe, avec des mots comme sommet. Un petit graphe sémantique, avec plein de relations diverses entre les mots.
      
      Un super dictionnaire en quelque sorte :-)
      
      Ca risque donc de devenir assez gros.
      
      J'ai bien compris que tu pralai d'un SGBD libre sur les graphes, mais j'ai pas trouvé de liens... que des euphémismes (a moins que j'ai pas vu..)
      
      As-tu un lien ?
      
      Merci :)
      « Il n’y a pas de choix démocratiques contre les Traités européens » - Jean-Claude Junker
      - [^] # Re: le modele relationnel est peu compatible avec la gestion des graphes
        
        Posté par Mouns (site web personnel) le 01 mars 2006 à 00:34. Évalué à 2.
        
        J'ai ecrit un SGBD libre se basant uniquement sur des graphes . Actuellement, il y a un CVS qui n'est plus a jour sur savannah .
        
        Actuellement, je suis le seul developpeur et il y a quelques sociétés qui l'utilisent.
        
        Le gros probleme est que te lacher sur l'interface sans accompagnement risque de te faire peur.
        
        Je suis OK pour te faire une présentation du truc de visu de l'appli et/ou d'envoyer par mail la doc.
        
        Pour le CVS il est par ici : http://savannah.nongnu.org/cvs/?group=xvii maintenant, c'est comme acceder au CVS de MySQL , cela ne sert que si tu veux patcher MySQL.
        
        je suis en train mettre à jour http://www.mouns.net/devel/XVII/ .
        
        Je te fairai des paquets deb si ce que je t'aurai présenté t'aura plus. :)
        
        [^] # Re: le modele relationnel est peu compatible avec la gestion des graphes
        
        Posté par Ontologia (site web personnel) le 01 mars 2006 à 01:00. Évalué à 3.
        
        Je viens de regarder, ça à l'air d'être dur à maîtriser mais intéressant :)
        
        Tu es sûr que le fait que ce soit codé en perl le rend plus lent ?
        
        J'imaginait pour ma part le faire en Lisaac, parce que ce serait un bonne occasion de faire un beau projet libre avec, sachant que je suis assuré d'avoir des performances proche du C avec un langage aussi haut niveau que perl (avec les types en plus).
        
        Ce graphe risque de devoir gérer quelques dizaines de millions de sommets, à terme. Tu penses que ça tiendra ?
        « Il n’y a pas de choix démocratiques contre les Traités européens » - Jean-Claude Junker
        
        [^] # Re: le modele relationnel est peu compatible avec la gestion des graphes
        
        Posté par Mouns (site web personnel) le 01 mars 2006 à 02:34. Évalué à 2.
        
        Le fait qu'il soit codé en perl n'a aucune influence sur les performances actuelles.
        
        Il a été en production avec des graphes ayant quelques centaines de milliers de noeuds.
        
        Je compte faire des benchs contre MySQL sur de la lecture de données et des écritures.
        
        Si cela t'interesse, je peux t'aider. Par contre, il y a plein de petits trucs à peaufiner pour que cela soit tip-top ... mais en l'état il peut faire deja plein de choses :)
        
        Je vais retrouver toutes les docs que j'avais faite et les mettre sur le site pour expliquer.
        
        [^] # Re: le modele relationnel est peu compatible avec la gestion des graphes
        
        Posté par Ontologia (site web personnel) le 01 mars 2006 à 17:15. Évalué à 2.
        
        Bah merci, ça peut m'intéresser, mais il faudrait que je sache en quelques lignes en quoi cela consiste.
        
        D'après ce que j'ai compris, il s'agit d'un système permettant de gérer des graphes stockés dans des fichiers.
        
        D'où question : comment le manipule t-on : s'agi t-il d'un langage à la SQL adapté au graphe, ou faut-il manipuler des fonction au travers d'une lib en perl ?
        Cela prend t-il beaucoup de mémoire ?
        « Il n’y a pas de choix démocratiques contre les Traités européens » - Jean-Claude Junker
        
        [^] # Re: le modele relationnel est peu compatible avec la gestion des graphes
        
        Posté par Mouns (site web personnel) le 02 mars 2006 à 02:28. Évalué à 2.
        
        dans le XVII tu trouves en fonctionnel :
        - un moteur en client/serveur pour gerer des graphes et collections de graphes
        - une API de requetes pour interoger le moteur
        - un ensemble d'objets pour mapper des objets perl sur des sous-graphes
        - un langage de templating pour faire du rendu de contenu
        - un modele de donnée pour le rendu via des templates
        - un toolkit SJAX/AJAX
        - un ensemble d'objets pour mapper des objets JS sur des sous-graphes
        - une GUI web assez moche mais tres efficace pour presque tout faire sans un shell
        
        par contre, il peut manquer plein de petits trucs cool comme outils pour que cela soit tip-top :(
        
        le probleme du SQL est qu'il n'est pas adapté à ce type d'usage.
        
        un noeud dans un graphe contient un ensemble d'attribut typé.
        
        le typage est dynamique par l'intermédiaire des classes d'objets pour le mapping.
        
        [^] # Re: le modele relationnel est peu compatible avec la gestion des graphes
        
        Posté par Ontologia (site web personnel) le 02 mars 2006 à 11:19. Évalué à 2.
        
        Bon ça me donne envie tes features ;-)
        
        Je ne parlais pas d'un langage à la SQL, mais d'un langage, tout simplement. On doit bien pouvoir créer un langage intéressant ?
        En se basant sur l'API, dont doit bien pouvoir batir un langage intéressant ?
        
        On est en train d'étudier l'intégration d'un langage à la SQL dans Lisaac, ça pourrait être une intéressante expérience, un langage de manipulation de graphe.
        
        Bon en tout cas, je vais pouvoir étudier ton système, maintenant que je sais ce que ça fait, même si le code me fait assez peur.
        
        Qu'entend-tu par "- un ensemble d'objets pour mapper des objets JS sur des sous-graphes" ?
        « Il n’y a pas de choix démocratiques contre les Traités européens » - Jean-Claude Junker
        
        [^] # Re: le modele relationnel est peu compatible avec la gestion des graphes
        
        Posté par Mouns (site web personnel) le 02 mars 2006 à 13:58. Évalué à 2.
        
        evite d'etudier le code du SGBD comme ca , c'est comme regarder le source de MySQL pour savoir comment l'utiliser ;)
        
        par contre, comme je t'ai dit, je m'active pour remettre en ligne les docs & tutoriaux que j'avais fait il y a longtemps ... il ne seront pas up to date mais ils te présenteront correctement l'idée de l'ensemble.
        
        Pour ce qui est du JS , cela permet de rendre executable un truc du genre :
        
        ajax_check( "RemoteClassRequester" );
        
        var mon_ajax = new RemoteClassRequester();
        
        mon_ajax.link( "ajax_configuration", "Conf" );
        
        var conf = new Conf( { defdeep:1 } );
        
        alert( conf.getDocumentation( "get" ) );
        
        avec pour le noeud "ajax_configuration" dans le template "code" :
        
        /*
        * Constructeur
        */
        
        _CONSTRUCTOR(
        function ( cookedvar ) {
        this.__cookedvar = cookedvar;
        for( o in cookedvar ) this[o] = new ConfValue( cookedvar[o] );
        }
        , "ceci est un constructeur assez con"
        );
        
        /* lit une cle de configuration */
        _METHOD( "get",
        function ( cle ) { return this[cle].value; }
        , "retourne la valeur de la cle demande"
        );
        
        /* pose une cle de configuration */
        _METHOD( "set",
        function ( cle, val ) { return this[cle].value = val; }
        );
        
        /*
        * genere une chaine contenant la configuration
        */
        _METHOD( "toString",
        function() {
        var ret = "";
        for( o in this.__cookedvar ) ret += " [" + o + "]->[" + this[o].value + "]";
        
        return ret;
        }
        );

Suivre le flux des commentaires

Note : les commentaires appartiennent à celles et ceux qui les ont postés. Nous n’en sommes pas responsables.