requête de base de données efficace pour ancêtres sur un graphe orienté acyclique

Question

LET dire de j'ai un graphe orienté acyclique, comme une famille « arbre » (pas vraiment un arbre depuis un enfant a 2 parents). Je veux placer une représentation de ce graphique dans une base de données relationnelle de sorte qu'il est rapide à calculer tous les ancêtres d'un noeud, et tous les descendants d'un noeud. Comment voulez-vous représenter ce graphique? Comment voulez-vous interroger pour tous les descendants? Comment voulez-vous insérer et de supprimer des nœuds et des relations? Quelles hypothèses vous faire sur les données?

La meilleure solution sera le meilleur grand O pour le nombre de déclarations de select/insert/delete vous exécutez aux ancêtres de la requête et descendants, avec des liens brisés par le meilleur grand O pour l'exécution totale, avec des liens brisés par les exigences de l'espace.

Mon collègue de travail m'a posé cette question. J'ai une solution mais il est de taille exponentielle dans le pire des cas, alors je voulais voir comment les autres se résoudre.

modifier

base de données relationnelle Clarifiée. Cette question est trivial (et ennuyeux) si vous utilisez des bases de données de graphique avec construit dans les fermetures transitif.

Answer 1

Si selects> manipulations, et surtout (tous les sous-arborescences sélectionne les ancêtres, tous les descendants) Je vais pour un fermeture approche -table. Oui, une explosion de chemins sur votre chemin table, mais elle fournir des résultats rapides (par opposition au modèle de contiguïté), et maintient des mises à jour limitées aux parties concernées (par opposition à la mise à jour de 50% avec des ensembles imbriqués).

Bill Karwin a une belle présentation en ligne sur les avantages et les inconvénients des différents modèles, voir http://www.slideshare.net/billkarwin/models-for-hierarchical-data (diapositive 48 est une vue d'ensemble).

Answer 2

Pour DAG dans des bases de données SQL, il semble y avoir que deux solutions:

1. récursive clause WITH.

2. transitive fermeture

Je ne suis pas au courant de tout système d'étiquetage graphique pratique (comme des ensembles imbriqués, des intervalles ou un chemin matérialisé)

Answer 3

"Comment voulez-vous représenter ce graphique?"

• VAR NŒUDS RELATION {noeud: sometype} {KEY noeud};
• VAR BORDS RELATION {parentNode: sometype childNode: sometype} {KEY parentNode childNode};
• CONTRAINTE NO_CYCLES is_empty (TCLOSE (CARRES) OÙ parentNode = childNode);

"Comment voulez-vous interroger pour tous les descendants?"

TCLOSE (BORDS) OÙ parentNode = somevalue;

« Comment voulez-vous insérer et de supprimer des nœuds et des relations? »

• INSERT INTO BORDS RELATION {{TUPLE parentNode somevalue chlidNode somevalue}};
• BORDS Rayer les mentions deleteCondition;

« Quelles hypothèses vous font sur les données? »

Quel genre d'hypothèses sont là pour faire? Vous avez indiqué tout ce qu'il ya à préciser en disant « graphe orienté acyclique ».

Answer 4

SGBDR: s ne sont pas vraiment conçus pour gérer ce genre de données. Le choix évident est d'utiliser une base de données graphique à la place, alors il n'y a pas besoin de traduire le graphique en une représentation différente, vous utilisez une API graphique tout le chemin. Il y a une bonne présentation par Marko Rodriguez expliquant l'impact du modèle de données sous-jacentes lorsqu'ils traitent avec traversals graphique, voir le graphique Traversal Programmation Motif si vous voulez regarder plus profondément dans cela.

J'ai écrit un exemple simple manipulation DAG avec la base de données graphique Neo4j il y a quelque temps qui peut être utile pour vous.

Answer 5

Dans une base de données relationnelle je stocker pour chaque noeud:

• père
• Childs
• ancêtres

Avec index sur tout et plein index sur les ancêtres

Demande:

• tous les ancêtres:
  • O (log n) (trouver le nœud, vous avez terminé)
• tous les descendants:
  • O (recherche-index complet sur les ancêtres) (dépend de la base de données)
• ajouter un nouveau noeud / nœud de suppression (sans Childs):
  • O (1) pour le père + ancêtres
  • O (log n) pour trouver le père
  • Childs O de mise à jour père (| Childs de père |)
• nœud de déplacement (difficile) :
  • O (1) pour le père de mise à jour
  • O (log n) pour trouver les anciens / nouveaux pères
  • Childs O deux fois de mise à jour père (| Childs de père |)
  • ancêtres de mise à jour de tous les descendants (simple, remplacer): O (| descendants | * | profondeur arbre max |) (profondeur max: remplacer et créer grande chaîne de longueur max (profondeur max))

volonté de complexité globale dépend de:

• profondeur de l'arbre
• arbre équilibré?
• nombre de Childs? (En moyenne, max ...)
• la complexité de l'opération dans une base de données relationnelle donnée

Pour SELECT seulement, efficace, mais difficile pour les mises à jour.

Dans la pratique: le travail sur l'arbre grandeur RAM (avec memchaed par exemple, garder tout dans la RAM) et sinon posssible acheter plus de RAM, de « roquet » vous arbre dans les arbres plus petits

.

Tous les descendants coûteront beaucoup de toute façon, avec des sous-arbres, vous pouvez avoir des descendants de max profondeur D, sans avoir tous.

« saut » forme sous-arbre sous-arbre: plus demande, mais plus rapide et le mode de les noeuds de déplacement plus rapide (seulement besoin de mettre à jour un sous-arbre)

.