Проблема рекурсивного подкаталога SQL - PullRequest
Новая
       17

Проблема рекурсивного подкаталога SQL

2 голосов
/ 28 февраля 2010

Это умственное упражнение, которое беспокоило меня некоторое время. Какую стратегию вы бы использовали для решения такого рода проблем?

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

create table directory ( 
 directoryId integer generated always as identity primary key,
 parentId integer default null,
 directoryName varchar(100)
);

create table content (
 contentId integer generated always as identity primary key,
 directory integer references directory(directoryId),
 contentTitle varchar(100),
 contentText varchar(32000)
);

Теперь давайте предположим, что наше дерево каталогов огромно, а объем контента огромен. Решение должно хорошо масштабироваться.

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

На мой взгляд, SQL не может быть использован для простого получения всех directoryIds для подвыбора. Я прав?

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

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

Моим самым любимым решением было бы, вероятно, добавить новую таблицу, такую ​​как 

create table subdirectories (
 directoryId integer,
 subdirectoryId integer,
 constraint thekey primary key (directoryId,subdirectoryId)
)

и убедитесь, что я всегда буду обновлять его вручную при перемещении / удалении / создании каталогов. Таким образом, я всегда мог сделать выбор с помощью directoryId и получить все идентификаторы для подкаталогов, в том числе в качестве подвыбора для более сложных запросов. Мне также нравится тот факт, что rdbms может хорошо оптимизировать запросы.

Что вы, ребята, думаете?

Ответы [ 2 ]

4 голосов
/ 28 февраля 2010

В SQL Server 2005, PostgreSQL 8.4 и Oracle 11g: 

WITH    
        -- uncomment the next line in PostgreSQL
        -- RECURSIVE
        q AS
        (
        SELECT  directoryId
        FROM    directories
        WHERE   directoryId = 1
        UNION ALL
        SELECT  d.directoryId 
        FROM    q
        JOIN    directories
        WHERE   parentId = q.directoryId
        )
SELECT  c.*
FROM    q
JOIN    content c
ON      c.directory = q.directoryId

В Oracle до 11g: 

SELECT  c.*
FROM    (
        SELECT  directoryId
        FROM    directories
        START WITH
                directoryId = 1
        CONNECT BY
                parent = PRIOR directoryID
        ) q
JOIN    content c
ON      c.directory = q.directoryId

Для PostgreSQL 8.3 и ниже см. Эту статью:

Для MySQL см. Эту статью:

1 голос
/ 28 февраля 2010

Это стандартная и хорошо понимаемая "трудная проблема" в SQL.

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

Существуют стандартные решения.

  1. Циклы с явным стеком, используемые для управления списком не посещенных узлов дерева.

  2. рекурсии. Это удивительно эффективно. Это не "требует сложного кеширования". Это действительно просто и действительно эффективно. Стек рекурсии - это список не посещенных узлов.

  3. Создание « транзитивного замыкания » дерева каталогов.

  4. Расширения SQL для обработки переходных отношений, таких как дерево каталогов.

...