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

Question

У меня есть таблица, содержащая иерархические данные.В настоящее время в этой иерархии ~ 8 уровней.

Мне действительно нравится, как структурируются данные, но производительность неутешительна, когда мне нужно знать, является ли запись на уровне 8 дочерней по отношению к записи на уровне 1.

У меня есть хранимые функции PL / SQL, которые выполняют эти поиски для меня, каждая из которых имеет оператор select * from tbl start with ... connect by....Это прекрасно работает, когда я запрашиваю несколько записей, но сейчас я нахожусь в ситуации, когда мне нужно запросить ~ 10 тысяч записей одновременно, и для каждой из них запустить эту функцию.Требуется 2-3 минуты, чтобы запустить его всего за несколько секунд.

Используя некоторую эвристику, основанную на моих знаниях текущих данных, я могу избавиться от функции поиска и просто выполнить childrecord.key || '%' LIKE parentrecord.keyно это действительно грязный хак и не всегда будет работать.

Так что теперь я думаю, что для этой иерархически определенной таблицы мне нужно иметь отдельную таблицу parent-child, которая будет содержать все отношения ...для иерархии, идущей от уровня 1-8, было бы 8!записи, связывающие 1 с 2, 1 с 3, ..., 1 с 8 и 2 с 3, 2 с 4, ..., 2 с 8. И т. д.

Я думаю, что япотребуется триггер вставки, где он будет в основном выполнять запрос connect by, и для каждого совпадения, идущего вверх по иерархии, он будет вставлять запись в таблицу поиска.А чтобы справиться со старыми данными, я просто настрою внешние ключи для основной таблицы с каскадным удалением.

Есть ли варианты получше, чем этот?Я скучаю по другому способу, которым я мог бы быстрее определить эти отношения далеких предков / потомков?

РЕДАКТИРОВАТЬ: Кажется, именно это я и думаю: http://evolt.org/working_with_hierarchical_data_in_sql_using_ancestor_tables

Answer 1

Итак, вы хотите материализовать переходные замыкания.То есть, учитывая эту таблицу приложения ...

 ID   | PARENT_ID
------+----------
    1 | 
    2 |         1
    3 |         2
    4 |         2
    5 |         4

... таблица графиков будет выглядеть следующим образом:

 PARENT_ID | CHILD_ID
-----------+----------
         1 |        2
         1 |        3
         1 |        4
         1 |        5
         2 |        3
         2 |        4
         2 |        5
         4 |        5

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

Я не думаю, что вы можете поддерживать такую ​​графическую таблицу с запросами CONNECT BY и каскадными внешними ключами.Слишком много косвенной активности, слишком сложно, чтобы получить право.Также отсутствует материализованное представление, потому что мы не можем написать запрос SQL, который уберет запись 1->5, когда мы удаляем исходную запись для ID=4.

Так что я предлагаю вам прочитать статью под названием Поддержание транзитивного замыкания графов в SQL по Донгу, Либкину, Су и Вонгу.В нем содержится много теории и несколько грубых (Oracle) SQL, но это даст вам основу для построения PL / SQL, необходимого для поддержки графической таблицы.

---

"Можете ли вы подробнее рассказать о том, что его слишком сложно поддерживать с помощью CONNECT BY / каскадных FK? Если я контролирую доступ к таблице и все вставки / обновления / удаления происходят черезхранимые процедуры, какие сценарии существуют, где это может сломаться? "

Рассмотрим запись 1->5, которая является коротким замыканием 1->2->4->5.Что произойдет, если, как я уже говорил, мы удалим исходную запись для ID=4?Каскадные внешние ключи могут удалить записи для 2->4 и 4->5.Но это оставляет 1->5 (и даже 2->5) в таблице графа, хотя они больше не представляют действительное ребро в графе .

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

 ID   | PARENT_ID | NEW_KEY
------+-----------+---------
    1 |           | AAA
    2 |         1 | BBB
    3 |         2 | CCC
    4 |         2 | DDD
    5 |         4 | EEE

Теперь графическая таблица будет выглядеть следующим образом:

 PARENT_ID | CHILD_ID | NEW_KEY
-----------+----------+---------
         1 |        2 | BBB
         1 |        3 | CCC
         1 |        4 | DDD
         1 |        5 | DDD
         2 |        3 | CCC
         2 |        4 | DDD
         2 |        5 | DDD
         4 |        5 | DDD

Таким образом, графическая таблица имеет внешний ключ, ссылающийся на отношение в исходной таблице, которая его сгенерировала, а не на ссылку наID.Тогда удаление записи для ID=4 приведет к каскадному удалению всех записей в графической таблице, где NEW_KEY=DDD.

Это будет работать, если любой заданный идентификатор может иметь только ноль или один родительский идентификатор.Но это не сработает, если это допустимо:

 ID   | PARENT_ID
------+----------
    5 |         2
    5 |         4

Другими словами, ребро 1->5 представляет собой 1->2->4->5 и 1->2->5.Итак, что может сработать, зависит от сложности ваших данных.