Деревья SQL

← →
User_OKA (2002-07-04 07:52) [0]

Прочитал на ibase.ru статью Joe Celco "Деревья SQL". Все красиво получается, когда у потомка один родитель. А как так же красиво описать структуру базы, когда у потомка может быть несколько родителей, причем принадлежать им он может одновременно?
Например, задвижка принадлежит газопроводу, расположенному в колодце, т.е. принадлежит как колодцу, так и газопроводу. Другая задвижка принадлежит только газопроводу. Как быть?

← →
User_OKA (2002-07-04 07:57) [1]

Статья на ib.demo.ru!...

← →
jonik pegas (2002-07-04 08:33) [2]

Можно попробовать ввести дополнительное поле типа ссылки (если оно равно идентификатору то это сам обьект,если не равно то это ссылка на другой обьект на который указывает поле ссылки

колодец
задвижка1
газопровод
ссылка на задвижку1
задвижка2

← →
User_OKA (2002-07-04 09:36) [3]

to jonik pegas
Обязательно попробую.
Однако, с нетерпением жду других предложений или ссылочку на соответствующую литературу.

← →
Sergey13 (2002-07-04 09:54) [4]

2jonik pegas © (04.07.02 08:33)
Идея правильная, но лучше (ИМХО) что бы ссылка на объект всегда была. Т.е. есть таблица с объектами и есть таблица со структурой вхождения этих объетков (т.е. само дерево). Это упрощает работу с данными - не надо постоянно анализировать - объект это или ссылка на него. Я это реализовал (пройдя через этап описанный тобой) и проблем с деревьями не имею - целый лес уже. 8-)

← →
Desdechado (2002-07-04 10:20) [5]

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

← →
Sergey13 (2002-07-04 10:30) [6]

2Desdechado © (04.07.02 10:20)
Это работает если есть только один газопровод и колодец (я уже запутался что чему принадлежит 8-). Но когда есть НЕСКОЛЬКО газопроводов, в каждом есть НЕСКОЛЬКО колодцев, в каждом есть НЕСКОЛЬКО задвижек - однозначной иерархии вы не получите.

← →
Desdechado (2002-07-04 11:02) [7]

тогда не иерархия, а списки:
1. газопровод - список колодцев, где проходит
2. газопровод - список задвижек
3. колодец - список задвижек
логика усложняется. деревьев нет, но есть однозначная идентификация связей объектов.

← →
Sergey13 (2002-07-04 11:19) [8]

2Desdechado © (04.07.02 11:02)
Дык можно и так, но
>логика усложняется. деревьев нет
а по моей структуре (Sergey13 © (04.07.02 09:54)) - наоборот - логика простая, деревья есть 8-). Хотя наличие деревьев в IB наверное минус - там вроде нет конструкции "Connect By" как в Оракле(я на нем делал) или я не прав?

← →
kaif (2002-07-04 12:30) [9]

С деревьями, ИМХО, можно иметь дело только если мы просто дробим некий континуум ради нашего удобства. Например, папки Fat32 разбивают однородное пространство диска. Если же мы храним существенную информацию, то на то существуют таблицы, поля, Entity-Relationship модель и вся эта реляционная теория, ради реализауии которой SQL-сервера создавались. Превращение всего на свете в деревья, ИМХО выхолащивает из объектов всякий смысл и делает невозможными нормальные запросы к такой базе.

← →
User_OKA (2002-07-04 12:55) [10]

to Desdechado
На одном газопроводе может быть много колодцев. Поэтому колодец я подчинил газопроводу, а не наоборот.
В любом случае, это просто пример. Хотелось бы получить ответ для общего случая.

to всем
А, вообще, проблема в следующем.
Создал я таблицу Object, в которую поместил список всех объектов:
id - первичный ключ,
name - русское имя объекта,
nametable - имя таблицы InterBase.
Затем создал таблицу Link:
id - первичный ключ,
master - код главного объекта,
detail - код подчиненного объекта.
Таким образом, я могу определить и количество родителей( не всех, начиная с корневого, а только, так сказать, прямых (непосредственных)) у конкретного потомка и количество потомков ( тоже непосредственных) у конкретного родителя.
Теперь я создаю таблицу для какого-нибудь потомка. В этой таблице нужно предусмотреть поля, в которых будут храниться коды родителей данного потомка (причем потоиок может принадлежать всем родителям одновременно). Но родителей может быть в общем случае сколько угодно много. Соответственно, нужно столько же полей.
Некрасиво все это. Тем более система будет со временем расширяться. Вот и думаю, как получше извратиться. Возможно, подход мой дилетантский. Научите, буду рад!

← →
Desdechado (2002-07-04 13:45) [11]

имхо, деревья тут ни к чему (kaif © (04.07.02 12:30)
а то, что на газопроводе много колодцев - нормально.
в одном колодце много газопроводов - тоже нормально.
типичная связь "многие-ко-многим".
аналогично с задвижками. это не дерево, а граф с циклами.

← →
Леша (2002-07-04 13:55) [12]

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

Однако еще про зодвижку. Если колодец пренадлежит газопроводу, а задвижка колодцу, то получается что и газопровод и колодец для нее родители, толко на разной уровне иерархии.

← →
User_OKA (2002-07-04 14:12) [13]

to Desdechado
А как такой граф с циклами описать в терминах таблицы, поля, строки? Грубо говоря, как получить таблицу с описанием подобной структуры, чтобы при добавлении/удалении объекта или изменении его уровня иерархии можно было соответствующим образом изменить структуру такой таблицы, а не перелопачивать всю базу в целом и клиенсткое приложение в частности?

to Леша
"Если колодец пренадлежит газопроводу, а задвижка колодцу, то получается что и газопровод и колодец для нее родители, толко на разной уровне иерархии"
Совершенно верно!

← →
SergSuper (2002-07-04 16:12) [14]

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

Не нужно. Потомки и их предки будут храниться в одной таблице Object. А выяснить кто из них кому потомок, а кому родитель можно только из таблицы Link. Если например объект имеет много родителей, то будет несколько записей с одинаковым detail, но разным master.

А вобще я бы советовал не торопиться при разработке структуры.

← →
Nebula (2002-07-04 16:43) [15]

http://sdm.viptop.ru/articles/sqltrees.html

← →
Desdechado (2002-07-04 17:20) [16]

2 User_OKA © (04.07.02 14:12)
способ описания сильно зависит от решаемых задач. Очень часто жертвуем стройностью концепции во имя скорости и наоборот. как было сказано, не стоит торопиться.
предлагаю 2 варианта:
1. все объекты в одной таблице + отдельная таблица перекрестных ссылок с 2 полями, которые оба являются внешними ключами на код объекта. Минус: невысокая скорость, сложность поддержания логических связей. Плюс: "все-в-одном", просто добавлять новые классы.
2. под каждый класс завести по табличке, создать таблицы перекрестных ссылок между ними. Минус: развивать сложнее, если добавляются новые классы. Плюс: скорость и строгость лучше.

← →
User_OKA (2002-07-05 06:44) [17]

to SergSuper
Теперь я создаю таблицу для какого-нибудь потомка. В этой таблице нужно предусмотреть поля, в которых будут храниться коды родителей данного потомка (причем потоиок может принадлежать всем родителям одновременно). Но родителей может быть в общем случае сколько угодно много. Соответственно, нужно столько же полей.
Я имел ввиду таблицу, в которой будут хранится сами данные объекта (как бы экземпляры конкретного объекта), а не описание связей объектов. Так вот для связи экземпляра объекта-потомка с экземпляром объекта-родителя в этой таблице должно присутствовать поле, в котором хранится первичный ключ экземпляра родителя. И чем больше родителей, тем больше таких полей потребуется.
Например, в данном случае, в таблице "Задвижка" будет два поля типа integer, первое будет зарезервировано под код газопровода, второе - под код колодца. И если потребуется ввести еще одного родителя для задвижки, в таблицу "Задвижка" придется ввести третье поле и т.д.
Можно как-то по другому извратиться?
Например, завести вместо множества полей одно, которое будет ссылаться на какую-нибудь таблицу связи. Так вот проблема, как такую таблицу связи соорудить!

to Desdechado
Первый вариант я и пытаюсь реализовать. Во втором варианте поясни, пожалуйста, что подразумевается под словом "класс". Если то, что в соих вопросах я называю объектом, тогда получается на каждый объект по таблице? Но у меня их около 70, не считая тех, кто появится в будущем. Не слишком много?

← →
User_OKA (2002-07-05 08:38) [18]

to Nebula
Был я там. Поэтому вопрос и возник. У меня потомок имеет несколько родителей. "многие-ко-многим".

← →
SergSuper (2002-07-05 09:59) [19]

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

Например, в данном случае, в таблице "Задвижка" будет два поля типа integer, первое будет зарезервировано под код газопровода, второе - под код колодца. И если потребуется ввести еще одного родителя для задвижки, в таблицу "Задвижка" придется ввести третье поле и т.д.
Можно как-то по другому извратиться?

Нужно :)
У нас будет одна таблица с четырьмя записями
id name 1 задвижка 2 колодец 3 газопровод 4 нечто новое
и есть таблица со связями. Допустим задвижка принадлежит и колодцу и газопроводу, а колодец только газопроводу
key id parint_id 0 1 2 1 1 3 2 2 3

и теперь появляется еще нечто, что будет родителем для задвижки. Мы просто добавляем в таблицу связей еще одно поле
key id parint_id 0 1 2 1 1 3 2 2 3 3 1 4

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

если что всё еще непонятно - можете по почте спросить

С приветом Сергей

← →
Sergey13 (2002-07-05 10:12) [20]

2User_OKA © (05.07.02 08:38)
>У меня потомок имеет несколько родителей. "многие-ко-многим".
Вот от этого я и предлагал избавляться. Это такое геморойное соотношение, что не дай бог.
Предлагаю
таблица OBJECTS
id -ключ
name -имя
bla-bla-bla -бла-бла-бла

id name bla-bla-bla
1 газопровод1 .......
2 газопровод2 ........
3 колодец1 ........
4 колодец2
5 задвижка

таблица LINKS
id -ключ
parent_id -родитель
id_objects -id из OBJECTS (FK)
kol -количество вхождения

id parent_id id_objects kol
1 null 1 1
2 1 3 2
3 2 5 10
4 1 4 1
5 4 5 5

и т.д и т.п.
По таблице LINKS строится нормальное сбалансированное дерево. Правда проходы по нему в IB это другой геморой (нет CONNECT BY). Но зато имеем единый подход к любому множеству родитель-потомок.

← →
Nebula (2002-07-05 10:31) [21]

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

(2User_OKA) Используй деревья на основе МНОЖЕСТВ, а не прямых ссылок на родителей. Таблица дерева ОДНА. И SQL-ем из такой таблици можно выбрать все что нужно в отличии от структуры со ссылками на родителй.

← →
User_OKA (2002-07-05 13:06) [22]

to Sergey13
Можешь пояснить насчет количества вхождений?

to Nebula
Вот еще бы почитать чего-нибудь про деревья на основе множеств...

to всем
А в инете есть что-нибудь на такую тему?

← →
AlexSV (2002-07-05 14:00) [23]

> User_OKA

ИМХО здесь вопрос не столько по построению деревьев, сколько по построению обектной базы.
Рекомендую почитать статью База данных — хранилище объектов на interface.ru http://www.interface.ru/fset.asp?Url=/borland/hran_01.htm
Надеюсь поможет решить Ваши проблемы.

← →
Nebula (2002-07-05 14:03) [24]

есть, е мое,
http://sdm.viptop.ru/articles/sqltrees.html
Именно про построение деревьев на основе множеств.
Сам использую подобную структуру. Добавлять хлопотно, согласен. Но большие удобства в создании всевозможных запросов.

← →
AlexSV (2002-07-05 14:05) [25]

> User_OKA

Предыдущая ссылка на первую часть.
А это вторая часть - http://www.interface.ru/fset.asp?Url=/borland/hran_02.htm

← →
User_OKA (2002-07-05 14:38) [26]

to AlexSV
спасибо большое! Ценная информация!

to Nebula
да что ж ты меня все время на sqltrees посылаешь? :)
был я там, прочитал статью и поэтому эту веточку организовал!
непонятно мне стало после прочтения, как описать с помощью предложенной там методики связь "многие-ко-многим".

← →
Nebula (2002-07-05 14:48) [27]

Приведи маленький пример дерева которое тебе нужно в виде

node
- subnode
- subnode
- subnode
- subnode
- subnode

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

Деревья SQL Найти похожие ветки