Discussion :

[Montaigne]

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 le tutoriel de SQLpro 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 !

[SQLpro]

Il n'existe pas de modèle particulier pour les graphes. Il faut donc créer une table d'adjacence avec deux colonnes (départ, arrivée) et les éventuels attributs.

Si votre SGBDR implémente la CTE (norme SQL:1999) alors il est possible de faire des parcours de graphes avec SQL.
A ma connaissance la CTE est implémentée sur SQL server 2005 et IBM DB2.
Lisez l'article que j'ai écrit à ce sujet :
http://www.sqlservercentral.com/columnists/fBROUARD/recursivequeriesinsql1999andsqlserver2005.asp

A +

[Montaigne]

Merci pour ta réponse.

Je me rend compte, suite à ta réponse, qu'un SGBD traditionnel deviendra rapidement problématique.
Il va falloir que je développe un petit SGBDR adapté aux graphes....

Vu que je viens de me poser le problème il ya 5 minutes, je vois ça comme ça (je pense le faire en GPL).

1/ Un système à noeud avec seeking, en faisant en sorte que les noeuds proches soient en série sur le disque. (en fait c un problème de projection de dimension N en dimension 1). Cela nécessitera de réorganiser le graphe régulièrement.

2/ Chaque noeud est géolocalisé dans un espace vectoriel en dimension N (N à fixer : 3,4,5 ?). On utilise un découpage en zone hypercubique arborescente. On localise grâce à un logarithme.
3/ Un système de hashage, afin de faire des recherches
4/ Un minimum de fonction méta graphe (liste de sous-graphes/domaines, découpage, jointure, etc...)


Et zut... Moi qui voulait éviter ça.
Je pense quand même utilser Postgre, au début.

L'article est très intéressant.

Il n'existe pas de modèle particulier pour les graphes. Il faut donc créer une table d'adjacence avec deux colonnes (départ, arrivée) et les éventuels attributs.

Si votre SGBDR implémente la CTE (norme SQL:1999) alors il est possible de faire des parcours de graphes avec SQL.
A ma connaissance la CTE est implémentée sur SQL server 2005 et IBM DB2.
Lisez l'article que j'ai écrit à ce sujet :
http://www.sqlservercentral.com/colu...server2005.asp

A +

[SQLpro]

Si tes données sont très graphes et peu gestion, laors le mieux est de faire une appli dédiée effectivement.

A +

[Montaigne]

Mes données, sont effectivement exclusivement graphe et pas du tout gestion...

Cela m'étonne tout de même : il y a bien quelqu'un qui a inventé un sgbd et un langage "à la SQL" pour manipuler des graphes tout de même ?

Ce genre de choses devrait avoir une grande utilité en entreprise, non ?

Si tes données sont très graphes et peu gestion, laors le mieux est de faire une appli dédiée effectivement.

A +

[SQLpro]

non !

peu...


A +

[Montaigne]

C'est un débat passionant ça ;-)

Dans une entreprise, les informations contenues dans le SI sont en générales arborescente, non ?
Pour ma part, c'est ce que j'ai toujours constaté...
(voir aussi le formidable succès de XML)

Quand on connecte des arbres entre eux, on constitue parfois des graphes. Il est vrai qu'en entreprise on a une forte prédominance des arbres sur les graphes.

Donc, les SGBD gérant des arborescences (eventuellement des graphes) devraient être très utile en entreprise...
Et je me demande si le modèle relationnel n'est pas un inadapté pour cela.

non !

peu...


A +