Мастера 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-11 11:55:00) [1]
... и в то же самое время уменьшает возможности при написании собственно приложения. Усложняется оно.

Romkin (2006-08-11 11:53:00) [2]
ДА я понял. И ты тоже? Удовлетворяет в смысле что все влезает. Не удовлетворяет в смысле ограничений, твоя модель дает больше свободы.

Fay (2006-08-11 11:47:00) [3]
В смысле
create table T ( ID int not null, PARENT_ID int null, constraint PK_T primary key (ID), constraint FK_T_SELF foreign key (PARENT_ID) references T (ID) ); -- Вопросы create table Q ( ID int not null, T_ID int not null, -- Тема вопроса constraint PK_Q primary key (ID), constraint FK_Q_T foreign key (T_ID) references T(ID) ); -- Тесты create table S ( ID int not null, T_ID int not null, -- Тема теста constraint PK_S primary key (ID), constraint FK_S_T foreign key (T_ID) references T (ID) ) -- Билеты create table C ( ID int not null, S_ID int not null, constraint PK_C primary key (ID), constraint FK_C_S foreign key (S_ID) references S (ID) ) -- билеты связаны с вопросами отношением многие-многие: create table CQ ( C_ID int not null, Q_ID int not null, constraint PK_CQ primary key (C_ID, Q_ID), constraint FK_CQ_C foreign key (C_ID) references C (ID), constraint FK_CQ_Q foreign key (Q_ID) references Q (ID) )

Fay (2006-08-11 11:44:00) [4]
Так?
create table T ( ID int not null, PARENT_ID int null, constraint PK_T primary key (ID), constraint FK_T_SELF foreign key (PARENT_ID) references T (ID) ); --Вопросы: тоже верно, немного изменю create table Q ( ID int not null, T_ID int not null, -- Тема вопроса constraint PK_Q primary key (ID), constraint FK_Q_T foreign key (T_ID) references T(ID) ); -- Билеты - увы! Нет там вопросов. И у нее есть мастер, таблица тестов S create table S ( ID int not null, T_ID int not null, -- тема билета! constraint PK_S primary key (ID), constraint FK_S_T foreign key (T_ID) references T (ID) ) --А теперь билеты create table C ( ID int not null, S_ID int not null, constraint PK_C primary key (ID), constraint FK_C_S foreign key (S_ID) references S (ID) ) --А теперь внимание, билеты связаны с вопросами отношением многие-многие: create table CQ ( C_ID int not null, Q_ID int not null, constraint PK_CQ primary key (C_ID, Q_ID), constraint FK_CQ_C foreign key (C_ID) references C (ID), constraint FK_CQ_Q foreign key (Q_ID) references Q (ID) )

Fay (2006-08-11 11:33:00) [5]
Зачем T_ID в PK_S ?

Romkin (2006-08-11 11:23:00) [6]
Неа :) Но почти.
Разделы - верно, повторяю, PK переименую
create table T ( T_ID int not null, PARENT_ID int null, constraint PK_T primary key (T_ID), constraint FK_T_SELF foreign key (PARENT_ID) references T (T_ID) ); --Вопросы: тоже верно, немного изменю create table Q ( Q_ID int not null, T_ID int not null, -- Тема вопроса constraint PK_Q primary key (Q_ID), constraint FK_Q_T foreign key (T_ID) references T(T_ID) ); -- Билеты - увы! Нет там вопросов. И у нее есть мастер, таблица тестов S create table S ( T_ID int not null, -- тема билета! S_ID int not null, constraint PK_S primary key (T_ID, S_ID), constraint FK_S_T foreign key (T_ID) references T (T_ID) ) --А теперь билеты create table C ( T_ID int not null, -- тема билета! S_ID int not null, C_ID int not null, constraint PK_C primary key (T_ID, S_ID, C_ID), constraint FK_C_S foreign key (T_ID, S_ID) references S (T_ID, S_ID) ) --А теперь внимание, билеты связаны с вопросами отношением многие-многие: create table CQ ( T_ID int not null, -- тема билета! S_ID int not null, C_ID int not null, Q_T_ID int not null, -- тема вопроса! Q_ID int not null, constraint PK_CQ primary key (T_ID, S_ID, C_ID, Q_T_ID, Q_ID), constraint FK_CQ_C foreign key (T_ID, S_ID, C_ID) references C (T_ID, S_ID, C_ID), constraint FK_CQ_Q foreign key (Q_T_ID, Q_ID) references Q (Q_T_ID, Q_ID) )
Сейчас так. А собственно постановка - в [36]

Fay (2006-08-11 06:11:00) [7]
2 Romkin © (10.08.06 10:45) [36]
Я понял так : -- Разделы create table T ( ID int not null, PARENT_ID int null, constraint PK_T primary key (ID), constraint FK_T_SELF foreign key (PARENT_ID) references T (ID) ) -- Вопросы create table Q ( ID int not null, T_ID int not null, -- Тема вопроса constraint PK_Q primary key (ID), constraint FK_Q_T foreign key (T_ID) references T(ID) ) -- Билеты create table C ( ID int not null, Q_ID int not null, T_ID int not null, -- Уточнённая тема, должна входить в ветку темы вопроса Q.T_ID constraint PK_Q primary key (ID), constraint FK_C_Q foreign key (Q_ID) references Q (ID), constraint FK_C_T foreign key (T_ID) references T (ID) )

Правильно?

Desdechado (2006-08-10 11:34:00) [8]
> Объемы теперь в "аптаймах" измеряются...
Думаю, ты понял, о чем я. О значительном времени, когда юзеры долбят/читают данные. Оттуда и объемы.

Romkin (2006-08-10 10:45:00) [9]
Fay © (10.08.06 07:04) [35] Из всех таблиц? В первом же абзаце сказано: вопрос принадлежит разделу. То есть, первоначально есть запись в THEME (раздел), и в него вводятся вопросы (и учебные материалы, кстати. Но они отношения не имеют). Далее в любом разделе можно сделать тестовое задание (SCRIPT), которое включает в себя некоторое количество билетов. И каждый билет содержит, в свою очередь, несколько вопросов, как из того раздела, которому принадледит тест, так и из нижележащих по дереву (подразделы). Логически это понятно: допустим, курс предмета разбивается на части, по каждой из которых будет экзамен. Плюс экзамен за весь курс, в билетах которого вопросы из всех частей.
Конечно, более естественной выглядит структура CARDQUESTION следующего вида: CREATE TABLE CARDQUESTION ( THEME_ID INTEGER NOT NULL, SCRIPT_ID INTEGER NOT NULL, CARD_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_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 ( THEME_ID, QUESTION_ID) REFERENCES QUESTION (THEME_ID, QUESTION_ID) ON DELETE CASCADE ON UPDATE CASCADE;
То есть, со слиянием ключей (см [16]), но это - явное указание на то, что у билета (CARD) могут быть вопросы только из его раздела, а это не проходит по условию :)

А сейчас, сделав правильное наследование ключей, я могу легко перефразировать задачу: есть таблица THEME
(THEME_ID integer not null primary key,
OWNER_ID integer references THEME(THEME_ID)); - дерево.
есть таблица 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
);
Поля этой таблицы THEME_ID и QUESTION_THEME_ID опосредованно ссылаются на THEME (THEME_ID).
Задача: Для заданного значения THEME_ID выяснить, имеется ли в таблице CARDQUESTION строка, в которой THEME_ID указывает на предка данного значения, а QUESTION_THEME_ID - на него или одного из его потомков. Через процедуру.

Увы, теперь я жалею, что не причесал структуру раньше. Думаю, многих вопросов бы не было :)))
Впрочем, именно структура и дает подсказку, буду идти по потомкам, брать из CARDQUESTION соответствующий THEME_ID этого потомка и проверять принадлежность того, что QUESTION_THEME_ID также входит в то же множество раздела и его потомков.
Получается даже более свободно, никаких предков.
Правда, фактически это вычитание множеств: берем множество потомков, и проверяем, что все вопросы этого множества входят в билеты только этого же множества :(

Fay (2006-08-10 07:04:00) [10]
2 афтар
Роман, объясните, пожалуйста, зачем в F(Р?)K_QUESTION входит THEME_ID? Я не могу понять.
Слова "связывающая вопрос и тему через билет" ваще не дают мне заснуть...

P.S.
Было бы славно полностью приводить все ключи...

Fay (2006-08-10 06:25:00) [11]
2 Desdechado © (09.08.06 19:50) [33]
> И объемы - не 24*7, конечно, но нехилые.
Прикольно... Объемы теперь в "аптаймах" измеряются...

Desdechado (2006-08-09 19:50:00) [12]
Я не предлагаю составных ключей...
Я предлагаю искусственные ключи, уникальные для каждой таблицы...

Практикую свой подход уже лет 10, ни разу не было проблем ни с масштабированием, ни с развитием, ни с быстродействием. А системы создавались немаленькие, минимум в 100 таблиц. И объемы - не 24*7, конечно, но нехилые.

Romkin (2006-08-09 19:43:00) [13]
Просто у меня был уже случай, когда пришлось делать составной ключ из искуственного (то есть, твою структуру приводить к моей). Только потому, что я когда-то заложился на уникальность поля. А потом потребовалось снять это требование. Учитывая, что это была одна из таблиц ядра - слышал бы ты ругань!
Сразу говорю: был выбран оптимальный путь, в других ситуациях колбаситься пришлось бы гораздо дольше.
Поэтому я крайне отрицательно отношусь к подобным инициативам. Как минимум это замедление работы, как максимум - постоянный геморрой в будущем. Минимум ограничений, максимум информации - вот что нужно.

Desdechado (2006-08-09 19:41:00) [14]
> Так справочников или мастеров?
?

> нет необходимости в первичном ключе? Это основа.
Например, протокол каких-то действий. Они могут быть одинаковые, даже в одно время, разница только в некоем блобе, который не включишь в ключ, да и не надо...
Правда, редкость, но такое бывает...

Все, я устал спорить. В конце концов "каждый идет к истине своей дорогой, а на перекрестке сижу я, Будда"
:)

Romkin (2006-08-09 19:35:00) [15]
Так справочников или мастеров? :) Справочники (неидентифицирующая связь) в первичный ключ не идут. И не понимаю я, что значит нет необходимости в первичном ключе? Это основа. И, кстати, если у тебя два мастера - это связь многие-многие. А если больше - то тут нужно подумать, а не повысить ли нормализацию до 4-5 формы?
И необходимость у меня эта есть постоянно. А "нельзя сделать простыми шагами" - да на многих структурах можно делать что-то по шагам. Вопрос в скорости, и в удобстве.

Desdechado (2006-08-09 19:30:00) [16]
> Идентифицирующую связь накладываешь - так сразу в первичный
> ключ детали идет первичный ключ мастера.
Если у тебя в детали ссылки на 15 справочников-мастеров, у тебя будет первичный ключ детали из 15 полей? Бред. Особенно, если нет необходимости в первичном ключе.
А если даже и пошло 15 полей, но эта таблица является мастером еще для какой-то, в которой тоже пара-тройка мастеров 15-польных, у тебя ключ в ней вырастет до 30-50 полей. Та хай меня покрасят тогда с такими правилами...

> Эта необходимость - постоянно есть
Нет. Она есть только при разворачивании всей связки, а это нужно не всегда.
Приведи пример действия, которое нельзя сделать на моей структуре простыми шагами.

Romkin (2006-08-09 19:20:00) [17]
Desdechado © (09.08.06 19:07) [27] Не догма, а инструмент с контролем структуры. И не поверю, что ложится. Либо все связи non-identify у тебя получаются, аэто - совсем не то. Идентифицирующую связь накладываешь - так сразу в первичный ключ детали идет первичный ключ мастера.

У билета есть вопрос, у вопроса есть тема. 3 таблицы.
Никаких ключей восстанавливать не надо.

А этот join - это и есть, по сути, восстановление ключа. И смотри, что получается: фактически, у тебя есть требование уникальности, допустим, на question_id. А у меня нет. Оно - дополнительное, и не нужно.

Модель - это и сущности и связи между ними. И все это вместе рассматривается.

>О, да! Она связана сразу со всеми таблицами.
Не сразу, а с двумя. Четко видны идентифицирующие связи, два foreign key. И четко по одной этой таблице я вижу всю иерархию, сразу предполагая, что над CARD есть еще два владельца (не справочника, а именно владельца), а над question - один. Модель читабельна даже по частям. И сразу видно, что эта таблица - соединение. Что еще нужно?!

И что значит "объединяем по необходимости"? Эта необходимость - постоянно есть, это во-первых. Во-вторых, я не вижу преимуществ твоей схемы, а недостатки - есть.

Desdechado (2006-08-09 19:07:00) [18]
> Ты свою структуру даже в ErWin не нарисуешь правильно.
ErWin - догма?
Кстати, ложится она туда хорошо. Что он должен пресечь, интересно?

> Мне как раз надо получить две THEME_ID из CARDQUESTION.
> Если там альтернативные, то я должен делать join 5 таблиц?!
Ничего подобного. У билета есть вопрос, у вопроса есть тема. 3 таблицы.
Никаких ключей восстанавливать не надо.

> Модель должна отражать реальное положение вещей, а не то,
> что удобно программисту.
Двумя руками за! Сущности - сами по себе, их взаимосвязи - сами. У тебя же в одну кучу намешано.

> четко видно, с чем связана CARDQUESTION и как.
О, да! Она связана сразу со всеми таблицами. Но ведь сам же рисовал цепочку:
темы, в которых тесты, в которых билеты, в которых вопросы, которые по темам
Вот они - 5 сущностей, по таблице на сущность, как и полагается. Соединяем требуемые при необходимости, а не храним все в одной таблице, как у тебя.

Сорри, не хочу ругаться, но, кажется, ты не хочешь понять...

Romkin (2006-08-09 18:52:00) [19]
Desdechado © (09.08.06 18:47) [25] Не надо! Ты свою структуру даже в ErWin не нарисуешь правильно. Он это дело пресекает.
Удобно?! Мне как раз надо получить две THEME_ID из CARDQUESTION. Если там альтернативные, то я должен делать join 5 таблиц?! Фактически, восстанавливая составные ключи?! Это, простите, маразм, а не удобство. Модель должна отражать реальное положение вещей, а не то, что удобно программисту. И как раз моя структура прозрачна, четко видно, с чем связана CARDQUESTION и как.

Desdechado (2006-08-09 18:47:00) [20]
> QUESTION_ID - альтернативный ключ?
Да, подзабыл. Я ведь уже уточнял по этому поводу...
Но я не вижу смысла генерировать ID вопроса внутри темы. Гораздо удобнее использовать QUESTION_ID как сквозной по всей таблице. Что я и предлагал в своем видении структуры.
А многокомпонентные первичные и внешние ключи мне неприятны, тем более, что в твоей ситуации легко можно обойтись и без них. От них только геморрой лишний и запутывание. Какой же это QUESTION_ID, если он неуникальный?
Размер - он, может, и не важен тут. Но вот прозрачности и легкопонимаемости у твоей структуры нет. Она тяжела для понимания.

Ладно, не буду больше давить. Я написал свое мнение.
А в JOIN нет ничего плохого. Зачем ты его боишься, не знаю...

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

Наверх

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