Мастера DELPHI (документация, исходники, скачать)

Основная («Начинающим»)/ Базы / WinAPI / Компоненты / Сети / Media / Игры / Corba и COM / KOL / FreePascal / .Net / Прочее / RSDN.ORG

« предыдущая ветвь | форум | следующая ветвь »

Дерево. Определение принадлежности узлов. [Firebird 1.5]

Страницы: < 1 2 3 >
Romkin © (2006-08-09 11:53:00)
Проблема появилась, сижу голову ломаю. Есть у меня БД вопросов, которые разделяются по древовидной структуре разделов, то есть, есть таблица разделов
CREATE TABLE THEME ( THEME_ID INTEGER NOT NULL, THEME_NAME VARCHAR(80), OWNER_ID INTEGER, ); ALTER TABLE THEME ADD CONSTRAINT PK_THEME PRIMARY KEY (THEME_ID); alter table THEME add constraint FK_THEME_THEME foreign key (OWNER_ID) references THEME(THEME_ID) on delete CASCADE on update CASCADE;
В общем, обычное дерево. Есть таблица вопросов:
CREATE TABLE QUESTION ( QUESTION_ID INTEGER NOT NULL, QUESTION_NAME VARCHAR(80), THEME_ID INTEGER NOT NULL ); ALTER TABLE QUESTION ADD CONSTRAINT FK_QUESTION PRIMARY KEY (THEME_ID, QUESTION_ID);
И есть таблица (на самом деле две), связывающая вопрос и тему через билет (утрировал, не особо принципиально):
CREATE TABLE CARDQUESTION ( CARD_ID INTEGER NOT NULL, SCRIPT_ID INTEGER NOT NULL, QUESTION_ID INTEGER NOT NULL, constraint PK_CARDQUESTION primary key (SCRIPT_ID, CARD_ID, QUESTION_ID) ); еще есть таблица SCRIPT (THEME_ID, SCRIPT_ID, ...) (показан PK)
То есть, у каждой ветви дерева может быть список вопросов, из которых формируются билеты теста (два поля SCRIPT_ID, CARD_ID - как раз идентификатор билета, SCRIPT - тест). Тест такде принадлежит определенному разделу (THEME_ID). Пока все замечательно.
Все дело в том, что в тест, а именно в CARDQUESTION, можно вставлять вопросы из того раздела, которому принадлежит тест и из любого его потомка. То есть, встав в дереве на какой-либо узел, я вижу все вопросы, которые принадлежат этому узлу, плюс вопросы его потомков. Соответственно, выбрать я тоже могу любой.
Вопрос состоит в том, что мне нужна процедура, которая быстро и оптимально может определить "изолированность" узла раздела (таблица THEME). То есть, мне нужна процедура, которая получает на вход THEME_ID и возвращает RET integer >0 в том случае, когда ни один вопрос из данного раздела и его потомковне используется в тестах его предков.
Кто-нибудь может посоветовать? Есть процедура, выводящая QUESTION_ID для данного THEME_ID и его потомков. Есть процедура, выводящая всех предков для данного THEME_ID. Как бы так поуютнее спарить? join процедур делать не хочется. Предков мало, высота дерева 20 от силы, а вопросов в разделе может быть и под тысячу...

Romkin (2006-08-09 18:39:00) [21]
Desdechado © (09.08.06 18:35) [22] А зачем мне городить постоянно join? Какая выгода от пользования того, как ты предлагаешь? Место? Мне хватает. Блюсти согласованность? Дык foreign key есть. Что еще?

Romkin (2006-08-09 18:38:00) [22]
Понимаешь, простой вопрос на засыпку: а почему ты решил, что QUESTION_ID - альтернативный ключ? :) Вопрос однозначно идентифицируется своим первичным ключем, (THEME_ID, QUESTION_ID). CARD тоже идентифицируется своим ключем, (THEME_ID, SCRIPT_ID, CARD_ID). И на данный момент у меня в БД нет альтернативных ключей для этих таблиц, не объявлены они, понимаешь? ;)
Следовательно, соединение многие-многие должно содержать полную комбинацию первичных ключей.
И даже если есть альтернативные - на каком основании я должен делать соединение по ним?! Такого требования нет.

Desdechado (2006-08-09 18:35:00) [23]
Требований точно не помню.
Но повторения взаимосвязей сущностей, AFAIR, быть не должно. А у тебя все перечисленное в [20] дублируется в "доработанной" таблице.
Зачем? Это ведь можно соединить каскадно JOIN'ами при необходимости.

Romkin (2006-08-09 18:32:00) [24]
Desdechado © (09.08.06 18:24) [20] Вот уж неправда. Приведи форму и требование, которому не удовлетворяет ;)
Вот именно, что есть. И поэтому в соединении все эти взаимоотношения учитываются.

Desdechado (2006-08-09 18:24:00) [25]
> Где там кольцо?! :)
В таблице QUESTIONS уже есть взаимоотношения вопросов и тем.
В таблице SCRIPT уже есть взаимоотношение тестов и тем.
В таблице THEME уже есть взаимоотношение тем более высокого и более низкого порядка.
Типичнейшая денормализация.

Romkin (2006-08-09 18:19:00) [26]
Desdechado © (09.08.06 17:47) [17] Где там кольцо?! :) Как раз нормальная форма, причем не ниже четвертой ;) И именно в этом случае - полностью оправданно.
MsGuns © (09.08.06 17:58) [18] Э. Надо было сразу делать дерево разделов на вложенных множествах, там проще проверки делать потомок-предок.
Ничего, уже примерно вырисовалось: во-первых, триггер, во-вторых, буду выяснять, а не потомок ли данного узла... Так, похоже, проще. То есть, взять всех предков, и для каждого посмотреть, а нет ли в CARDQUESTION у этого предка потомков данного узла и его самого. Похоже, наименьший лаг получится.

MsGuns (2006-08-09 17:58:00) [27]
>Romkin © (09.08.06 17:44) [16]

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

Desdechado (2006-08-09 17:47:00) [28]
> привел к нормальному виду:
ИМХО, сплошная денормализация. Закольцевал ключи, как только можно...
Иногда это оправдано, но, имхо, не в этом случае.

Romkin (2006-08-09 17:44:00) [29]
Все, таки привел к нормальному виду: CREATE TABLE CARDQUESTION ( THEME_ID INTEGER NOT NULL, SCRIPT_ID INTEGER NOT NULL, CARD_ID INTEGER NOT NULL, QUESTION_THEME_ID INTEGER NOT NULL, QUESTION_ID INTEGER NOT NULL, ORD_NUM INTEGER ); ALTER TABLE CARDQUESTION ADD CONSTRAINT PK_CARDQUESTION PRIMARY KEY (THEME_ID, SCRIPT_ID, CARD_ID, QUESTION_THEME_ID, QUESTION_ID); ALTER TABLE CARDQUESTION ADD CONSTRAINT FK_CARDQUESTION_CARD FOREIGN KEY (THEME_ID, SCRIPT_ID, CARD_ID) REFERENCES CARD (THEME_ID, SCRIPT_ID, CARD_ID) ON DELETE CASCADE ON UPDATE CASCADE; ALTER TABLE CARDQUESTION ADD CONSTRAINT FK_CARDQUESTION_QUESTION FOREIGN KEY (QUESTION_THEME_ID, QUESTION_ID) REFERENCES QUESTION (THEME_ID, QUESTION_ID) ON DELETE CASCADE ON UPDATE CASCADE;
И вот тут как раз и видна связь: два поля THEME_ID и QUESTION_THEME_ID. Первое - какой теме принадлежит тест, второе - какой теме принадлежит вопрос. Существует ограничение: QUESTION_THEME_ID - строго потомок (неважно, через сколько детей) THEME_ID или они равны.
Нужна процедура, которая для данного ID (THEME_ID) определяет, есть ли в его предках ссылки через эту таблицу на него или его потомков. То есть, есть ли записи в CARDQUESTION, где THEME_ID - предок ID, а QUESTION_THEME_ID - либо потомок ID, либо он сам. О как :)
Вопрос в том, как лучше повернуть.

Desdechado (2006-08-09 17:43:00) [30]
> есть QUESTION_ID, надо вывести все SCRIPT_ID, в которых
> он употребляется. И как в твоей структуре это будет смотреться?
SELECT DISTINCT C.script_id FROM Card C, CardQuestion CQ WHERE CQ.question_id = :Q AND CQ.card_id = C.card_id
Вроде совсем не сложно...

evvcom (2006-08-09 17:32:00) [31]
Ну так вопрос исчерпан или как? Мой [10] помог, или я его тоже туманно изложил? Или остановился на реконструкции таблиц?

Romkin (2006-08-09 17:24:00) [32]
MsGuns © (09.08.06 16:26) [12] Наверно, можно сказать и так. Условие - через CARD узел может владеть вопросом только своих потомков.

MsGuns (2006-08-09 16:26:00) [33]
Я, возможно, чего-то недопонял, но мне показалось, что вся загвоздка в том, что один и тот же узел может принадлежать одновременно нескольким родителям. В этом случае вместо дерева имеем граф и, соответственно цепочки вхождений каждого узла в вершины графа.
Если так, то вопрос упирается в алгоритмы разузлования вверх и вниз ?

Romkin (2006-08-09 14:22:00) [34]
Desdechado © (09.08.06 13:36) [9] НУ да, ну да, конечно. Особенно в свете того, что мне сейчас надо делать join CARDQUESTION именно потому, что у нее не полный составной ключ! Был бы полный - я бы сразу взял оттуда пару THEME_ID, первая - которой принадлежит скрипт, вторая - которой принадлежит вопрос. А то, что ты предлагаешь - вообще приводит к непрерывным join!
Простой вопрос: есть QUESTION_ID, надо вывести все SCRIPT_ID, в которых он употребляется. И как в твоей структуре это будет смотреться?! У меня это - простой запрос к CARDQUESTION

evvcom (2006-08-09 14:02:00) [35]
В Оракле есть такая замечательная функция SYS_CONNECT_BY_PATH. Приведу описание для пущей ясности:
Syntax
SYS_CONNECT_BY_PATH ( column , char )
Purpose
SYS_CONNECT_BY_PATH is valid only in hierarchical queries. It returns the path of
a column value from root to node, with column values separated by char for each
row returned by CONNECT BY condition.
Both column and char can be any of the datatypes CHAR, VARCHAR2, NCHAR, or
NVARCHAR2. The string returned is of VARCHAR2 datatype and is in the same
character set as column.
Examples
The following example returns the path of employee names from employee
Kochhar to all employees of Kochhar (and their employees):
SELECT LPAD(’ ’, 2*level-1)||SYS_CONNECT_BY_PATH(last_name, ’/’) "Path"
FROM employees
START WITH last_name = ’Kochhar’
CONNECT BY PRIOR employee_id = manager_id;
Path
---------------------------------------------------------------
/Kochhar
/Kochhar/Greenberg
/Kochhar/Greenberg/Faviet
/Kochhar/Greenberg/Chen
/Kochhar/Greenberg/Sciarra
/Kochhar/Greenberg/Urman
/Kochhar/Greenberg/Popp
/Kochhar/Whalen
/Kochhar/Mavris
/Kochhar/Baer
/Kochhar/Higgins
/Kochhar/Higgins/Gietz

Пробелы в результате удалились :( Таков уж HTML и IE.
Далее идея:
Разворачиваем дерево от потомков к предкам и используем вышеупомянутую функцию. Таким образом получаем для каждой THEME_ID несколько записей с путями, которые легко можно преобразовать к виду флага "есть child" или "нет". А далее агрегатным запросом получить конечное значение нужного флага.
Поскольку функцию или ее некий аналог придется реализовывать в FB самому, то и о флаге соответственно можно позаботиться уже в ней.

Desdechado (2006-08-09 13:36:00) [36]
Мне кажется, чтотакая структура более удобна для твоей задачи.
CREATE TABLE THEME ( THEME_ID INTEGER NOT NULL, THEME_NAME VARCHAR(80) NOT NULL, OWNER_ID INTEGER NOT NULL, ); ALTER TABLE THEME ADD CONSTRAINT PK_THEME PRIMARY KEY (THEME_ID); ALTER TABLE THEME ADD CONSTRAINT FK_THEME_THEME FOREIGN KEY (OWNER_ID) REFERENCES THEME(THEME_ID); CREATE TABLE QUESTION ( QUESTION_ID INTEGER NOT NULL, QUESTION_NAME VARCHAR(80) NOT NULL, THEME_ID INTEGER NOT NULL ); ALTER TABLE QUESTION ADD CONSTRAINT PK_QUESTION PRIMARY KEY (QUESTION_ID); ALTER TABLE QUESTION ADD CONSTRAINT FK_QUESTION_THEME FOREIGN KEY( THEME_ID ) REFERENCES THEME( THEME_ID ); CREATE TABLE SCRIPT ( SCRIPT_ID INTEGER NOT NULL, SCRIPT_NAME VARCHAR(80) NOT NULL, THEME_ID INTEGER NOT NULL ); ALTER TABLE SCRIPT ADD CONSTRAINT PK_SCRIPT PRIMARY KEY( SCRIPT_ID ); ALTER TABLE SCRIPT ADD CONSTRAINT FK_SCRIPT_THEME FOREIGN KEY( THEME_ID ) REFERENCES THEME( THEME_ID ); CREATE TABLE CARD ( CARD_ID INTEGER NOT NULL, CARD_NO VARCHAR(30) NOT NULL, SCRIPT_ID INTEGER NOT NULL ); ALTER TABLE CARD ADD CONSTRAINT PK_CARD PRIMARY KEY( CARD_ID ); ALTER TABLE CARD ADD CONSTRAINT FK_CARD_SCRIPT FOREIGN KEY( SCRIPT_ID ) REFERENCES SCRIPT( SCRIPT_ID ); CREATE TABLE CARDQUESTION ( CARD_ID INTEGER NOT NULL, QUESTION_ID INTEGER NOT NULL ); ALTER TABLE CARDQUESTION ADD CONSTRAINT UQ_CARDQUESTION UNIQUE (CARD_ID, QUESTION_ID); ALTER TABLE CARDQUESTION ADD CONSTRAINT FK_CARDQUESTION_CARD FOREIGN KEY( CARD_ID ) REFERENCES CARD( CARD_ID ); ALTER TABLE CARDQUESTION ADD CONSTRAINT FK_CARDQUESTION_QUESTION FOREIGN KEY( QUESTION_ID ) REFERENCES QUESTION( QUESTION_ID );
Но при условии, конечно, что тест толькопо одной теме, а билет может включать вопросы одной темы и присутствовать только в одном тесте.

evvcom (2006-08-09 13:04:00) [37]
> [7] Romkin © (09.08.06 13:01)

После [4] прояснилось. Когда я писал, [4] еще не видел.

Romkin (2006-08-09 13:01:00) [38]
Неужели туманно?

Вот есть цепочка THEME -> QUESTION (вопрос принадлежит разделу). Прошу учесть, что THEME - дерево.
и есть вторая цепочка THEME -> SCRIPT -> CARD -> QUESTION (В разделе может быть тест, который состорит из билетов, которые могут включать в себя вопросы данного раздела и любого из его потомков). Связь CARD и QUESTION - многие-многие, поэтому есть CARDQUESTION.
Нужно выяснить, можно ли, допустим, убрать раздел. При удалении раздела удаляются и все его потомки. Раздел нельзя убрать, если вопросы используются в остающихся разделах (то есть, есть вопрос раздела или его потомков, который используется в тестах предка). Вот и сижу. Это касается не только удаления, просто сказать пользователю, можно ли переместить ветку и тд...

Sergey13 (2006-08-09 13:01:00) [39]
Не знаю поможет ли, мне в свое время здорово помогло.
В таблицу THEME можно добавить поле с головной родительской темой. Основываясь на нем можно многие запросы переделать на шустрые и плоские, минуя разбор дерева или хотя бы здорово ограничить число рабираемых записей.

evvcom (2006-08-09 12:50:00) [40]
> [1] zdm © (09.08.06 12:08)
> [3] zdm © (09.08.06 12:26)

Где ты увидел вопрос о коде на паскале?

> [0] Romkin © (09.08.06 11:53)
> [2] Desdechado © (09.08.06 12:13)

Да, с тестами туманно. Как недавно кто-то говорил про английский, если непонятен смысл слова игнорируй его. Аналогично игнорирую "тест" и отношу все сказанное про него на "билет". Не зная все ж возможностей FB работы с деревьями, думаю, как бы это сделал на оракле без древовидных запросов и функций.

Страницы: < 1 2 3 >

Наверх

	« предыдущая ветвь \| форум \| следующая ветвь »