Представление многосвязных списков в SQL

Question

У меня есть структура данных, состоящая из набора объектов, которые объединены в многосвязный список, который также (изоморфно) является действительным DAG. Его можно рассматривать как один единый многосвязный список или как серию n двусвязных списков, которые могут совместно использовать участников. (Это та же структура данных из Алгоритм для быстрого получения частичного упорядочения по нескольким связанным спискам , для тех из вас, кто следит за моими вопросами.)

Я ищу общий метод, без какого-либо конкретного диалекта SQL, для выражения этого многосвязного списка / DAG в SQL, чтобы можно было легко взять данный узел и получить:

• Предыдущая и следующая ссылки в DAG с учетом топологического порядка DAG
• Предыдущая и следующая ссылки в каждом двусвязном списке, к которому принадлежит этот узел

Используя пример данных из этого другого вопроса:

first  = [a, b,    d,    f,    h, i];
second = [a, b, c,       f, g,    i];
third  = [a,          e, f, g, h, i];

Я бы хотел иметь возможность, учитывая узел f, получить [(c|d|e), g] из общей топологии DAG, а также {first: [d, h], second: [c, g], third: [e, g]} из каждого порядка списков.

Вот забавная часть: n , число двусвязных списков, не является фиксированным и может расти в любое время. Я бы не хотел переделывать схему каждый раз, когда это происходит.

Все алгоритмы, которые я до сих пор придумал, либо (а) запихивают большой DBL в БД и вытаскивают его для вычисления порядков, либо (б) требуют, чтобы списки были явно перечислены как рекурсивные отношения в БД.

Я пойду с опцией в (b), если я не смогу найти что-то лучше, но я надеюсь, что есть что-то волшебное, чтобы облегчить это.

Answer 1

Pre: Это форум вопросов и ответов, а не форум «давайте сядем, немного подумай и решим всю проблему».

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

Я помню хорошую статью об этом (пару лет назад), но не могу найти банкомат с закладками, поэтому начните с поиска в Google.

EDIT / UPDATE:

ссылка: http://www.sitepoint.com/hierarchical-data-database/

Независимо от того, что из широкого рассмотрения этого вопроса, вам придется выбирать, взять ли на себя основной удар работы, видения или изменения. В зависимости от размера «главного» дерева, вы можете (как и я) решить разбить дерево на части и использовать дерево, ограничив стоимость обновления.