База данных Parent / Child содержит циклические ссылки

Question

У меня есть таблица ключевых слов, где каждому ключевому слову присваивается уникальный идентификатор. У меня есть вторая таблица, которая связывает идентификаторы родительских ключевых слов с идентификаторами дочерних ключевых слов. Одно ключевое слово может иметь до 800 детей или вообще не иметь их. Дети могут быть родителями еще большего количества ключевых слов (и так далее ...)

Проблема, с которой я сталкиваюсь, это то, что ребенок (или внук, или правнук) может быть родителем исходного ключевого слова, вызывая циклическую структуру. Я пытаюсь построить древовидную структуру данных для исходного ключевого слова, используя рекурсивную функцию, но функция либо никогда не заканчивается, либо выходит за пределы рекурсии уровня 1000 в Python.

Есть ли лучший способ спроектировать мою родительскую / дочернюю таблицу, чтобы предотвратить это (или выполнить предварительную проверку во время вставок), или есть лучший способ написать рекурсивную функцию для предотвращения возникновения этого условия? Я пытался ограничить глубину функции рекурсии, но столкнулся с проблемами на одном уровне (то есть дочерний элемент является родителем родительского элемента). Опять же, моя цель - создать древовидную структуру для исходного ключевого слова.

Table Keyword:
    id int(11) not null primary key auto_increment (id of keyword)
    text varchar(255) unique (keyword text e.g. "computer help desk")

Table Keyword_Relation:
    id int(11) not null primary key auto_increment (id for parent/child combo, not keyword id)
    parent int(11) (id of parent keyword)
    child int(11) (id of child keyword)

Answer 1

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

В вашем случае это звучит так, как будто у вас нет родителя с несколькими родителями. Но то, как я справился с этим программно, - это начать с листовых узлов (то есть без дочерних узлов) и подняться на дерево. Во время подъема сохраняйте коллекцию встреченных вами узлов. Если вы когда-либо повторяете встречу, тогда существует цикл, и топологическая сортировка невозможна.

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

РЕДАКТИРОВАТЬ: Чтобы ответить на ваш вопрос о "лучшем дизайне" .... Если возможно, может быть полезно сохранить идентификатор корневого узла. То есть: дано родителю, ребенку, внуку, правнуку, великому великому .... внуку

Каждая строка будет содержать не только непосредственный идентификатор родителя, но также корневой узел Родительский идентификатор ... или какой-либо "заведомо исправный" корневой узел

Если вы сделаете это, вы можете ускорить методы топологической сортировки, поднявшись только до корневого узла, и включив в него только наборы, имеющие одинаковый корневой узел.

Answer 2

Вы можете начать с вершины дерева, просто отслеживать уже найденные узлы и игнорировать их.

def getchildren(node, ignore_nodes=[]):
    child_nodes = []
    for child in node.children():
        if child in ignore_nodes:
            continue
        child_nodes.append(child)
        ignore_nodes.append(child)
        nodes, ignore_nodes = getchildren(child, ignore_nodes)
        child_nodes.extend(nodes)
    return child_nodes, ignore_nodes