Эффективный запрос к базе данных для предков на ациклическом ориентированном графе - PullRequest
Новая
       1

Эффективный запрос к базе данных для предков на ациклическом ориентированном графе

8 голосов
/ 21 сентября 2010

Допустим, у меня есть ациклический ориентированный граф, такой как семейное «дерево» (на самом деле это не дерево, так как у ребенка 2 родителя).Я хочу поместить представление этого графа в реляционную базу данных, чтобы можно было быстро вычислить всех предков узла и всех потомков узла.Как бы вы представили этот график?Как бы вы запросили всех потомков?Как бы вы вставили и удалили узлы и отношения?Какие предположения вы делаете в отношении данных?

Лучшее решение будет иметь лучший большой O для числа операторов select/insert/delete, которые вы выполняете для запроса предков и потомков, с связями, разорванными лучшим большим O для общего времени выполнения.с разорванными связями из-за нехватки места.

Мой коллега задал мне этот вопрос.У меня есть решение, но в худшем случае оно имеет экспоненциальный размер, поэтому я хотел посмотреть, как его решат другие люди.

edit

Уточненная реляционная база данных.Этот вопрос тривиален (и скучен), если вы используете графовые базы данных со встроенными транзитивными замыканиями.

Ответы [ 5 ]

7 голосов
/ 21 сентября 2010

Если selects> manipulations и, в особенности, выбирается поддерево (все предки, все потомки), я бы выбрал Closure -табильный подход. Да, набор путей в вашей таблице путей, но он обеспечивает быстрое получение результатов (в отличие от модели смежности) и ограничивает обновления соответствующими частями (в отличие от 50% -ного обновления с вложенными наборами).

У Билла Карвина есть хорошая презентация в Интернете о плюсах и минусах различных моделей, см. http://www.slideshare.net/billkarwin/models-for-hierarchical-data (слайд 48 - обзор).

3 голосов
/ 23 сентября 2010

Для групп обеспечения доступности баз данных в базах данных SQL существует только два решения:

  1. Рекурсивное предложение WITH.

  2. Переходное замыкание

Мне неизвестна какая-либо практическая схема маркировки графа (например, вложенные множества, интервалы или материализованный путь)

2 голосов
/ 21 сентября 2010

"Как бы вы представили этот график?"

  • ОТНОШЕНИЕ VAR NODES {узел: sometype} KEY {узел};
  • ОТНОШЕНИЕ VAR EDGES {parentNode: sometype childNode: sometype} KEY {parentNode childNode};
  • CONSTRAINT NO_CYCLES IS_EMPTY (TCLOSE (EDGES) WHERE parentNode = childNode);

"Как бы вы запросили всех потомков?"

TCLOSE (EDGES) WHERE parentNode = somevalue;

"Как бы вы вставили и удалили узлы и отношения?"

  • ВСТАВЬТЕ В ОТНОШЕНИЕ EDGES {TUPLE {parentNode somevalue chlidNode somevalue}};
  • DELETE EDGES WHERE deleteCondition;

«Какие предположения вы делаете относительно данных?»

Какие предположения существуют?Вы указали все, что нужно указать, сказав "ориентированный ациклический граф".

1 голос
/ 21 сентября 2010

RDBMS: на самом деле не предназначены для обработки такого рода данных. Очевидный выбор - вместо этого использовать графовую базу данных , тогда нет необходимости переводить граф в другое представление, вы все время используете API API для графов. Хорошая презентация Марко Родригеса, объясняющая влияние базовой модели данных при работе с обходами графиков, см. Шаблон программирования обхода графиков , если вы хотите углубиться в это.

Я недавно описал простой пример обработки DAG с базой данных графов Neo4j , который может быть полезен для вас.

0 голосов
/ 23 сентября 2010

В реляционной базе данных я бы сохранил для каждого узла:

  • Отец
  • Чайлдс
  • 1008 * предки *

С индексом на все и полным индексом на предках

Запрос на:

  • все предки:
    • O (log n) (найдите узел, тогда все готово)
  • все потомки:
    • O (полный индексный поиск по предкам) (зависит от базы данных)
  • добавить новый узел / удалить узел (без дочерних элементов):
    • O (1) для отца + предков
    • O (войти n), чтобы найти отца
    • обновить отцовских детей O (| отцовских детей |)
  • переместить узел (сложный) :
    • O (1), чтобы обновить отца
    • O (войти n), чтобы найти старых / новых отцов
    • дважды обновить дочерние элементы отца O (| дочерние элементы отца |)
    • обновить предков всех потомков (простая замена): O (| потомки | * | глубина макс. Дерево |) (глубина-максимум: заменить и создать большую строку максимальной длины (глубина-максимум))

Общая сложность зависит от:

  • Глубина дерева
  • сбалансированное дерево?
  • количество детей? (в среднем, макс ...)
  • сложность работы в данной реляционной базе данных

Только для SELECT, эффективно, но сложно для обновлений.

На практике: работайте с деревом размером в ОЗУ (например, с memchaed, сохраняйте все в ОЗУ) и, если это невозможно, покупайте больше ОЗУ, чтобы "обрезать" дерево в меньших деревьях.

Все-потомки будут стоить дорого в любом случае, с поддеревьями вы можете иметь потомков с максимальной глубиной D, не имея их всех.

Вы «перепрыгиваете» из поддерева формы в поддерево: больше запросов, но быстрее и И перемещаете узел намного быстрее (нужно только обновить поддерево).

...