 |
|
Модераторы: LSD |
 
|
|
Создание дерева с неогр. уровнем вложенности, MySQL. Проектирование БД, 
| Wowa |
|
|||
 Эксперт  Профиль Группа: Админ Сообщений: 15017 Регистрация: 14.9.2000 Где: Винград Репутация: 1 Всего: 290 |
Создать дерево с неограниченным уровнем вложенности - не проблема, но мне необходмо, чтобы содержимое какой-то ветки могло находится одновременно в нескольких ветках(разного уровня вложенности). Как посоветуете хранить данные и какую структуру выбрать?
P.S. программировать на PHP буду. |
|||
|
||||
Загрузка ...
| Akina |
|
|||
|
Советчик  Профиль Группа: Модератор Сообщений: 20581 Регистрация: 8.4.2004 Где: Зеленоград Репутация: 13 Всего: 454 |
Ввести тип "алиас". Или, если хочешь, "ярлык". Как это сделано с мягкими ссылками в файловой системе.
Или разделить таблицу на "Объекты" и "Зависимости". -------------------- О(б)суждение моих действий - в соответствующей теме, пожалуйста. Или в РМ. И высшая инстанция - Администрация форума. |
|||
|
||||
| Се ля ви |
|
|||
 Java/SOAрхитектор Профиль Группа: Модератор Сообщений: 2016 Регистрация: 5.6.2004 Где: place without tim e and space Репутация: нет Всего: 127 |
ИМХО, подойдёт любая реальзация связи "многие ко многим" между сущностями внутри одной таблицы.
Вообще-то такие структуры лучше делать в XML и обращаться при помощи XQL или XQuary - поддержка этого есть в Оракле и некоторых других БД (собственно, для таких задачь и создаётся XML-ные БД, по-моему). -------------------- |
|||
|
||||
| Vyacheslav |
|
|||
|
Эксперт Профиль Группа: Экс. модератор Сообщений: 2124 Регистрация: 25.3.2002 Где: Москва Репутация: нет Всего: 59 |
Первая таблица Items (листья дерева )
ID - уникальный идентифкатор Name - имя ... Вторая таблица Tree(структура) ID - уникальный идентифкатор ParentID - индентифкатор владельца (ParentID->Tree.ID) ItemID - идентификатор листа (ItemID->Items.ID) ... Добавлено @ 13:07 Кстати есть и другие подходы Вот посмотри на это http://sdm.viptop.ru/articles/sqltrees.html -------------------- С уважением, Вячеслав Ермолаев |
|||
|
||||
| Vit |
|
|||
 Vitaly Nevzorov Профиль Группа: Экс. модератор Сообщений: 10964 Регистрация: 25.3.2002 Где: Chicago Репутация: 14 Всего: 207 |
Id|Parent|Level|Type|Context
Id - уникальный номер Parent - ссылка на родительский узел Level - уровень (не обязательно но деревья рисовать помогает) Type - тип узла: узел, конечная статья, ярлык на другой узел, корневой узел Context - содержимое -------------------- With the best wishes, Vit I have done so much with so little for so long that I am now qualified to do anything with nothing Самый большой Delphi FAQ на русском языке здесь: www.drkb.ru |
|||
|
||||
| Се ля ви |
|
|||
|
Java/SOAрхитектор Профиль Группа: Модератор Сообщений: 2016 Регистрация: 5.6.2004 Где: place without tim e and space Репутация: нет Всего: 127 |
Насколько я понял Admin`а, елементу нельзя задасть однозначный уровень, лишь в контексте одного пути обхода дерева такой уровень будет иметь смысл... -------------------- |
|||
|
||||
| skyboy |
|
|||
|
неОпытный Профиль Группа: Модератор Сообщений: 9820 Регистрация: 18.5.2006 Где: Днепропетровск Репутация: 5 Всего: 260 |
А если для каждого "листа" может быть несколько значений - как из хапомнить? Ну, чтоб можно было восстановить? В моём случае дерево только хранит структуру ввода и отображения, а данных может быть много. Не создавать же каждый раз для каждого случая дерево-дубликат, но с конкретными данными!
|
|||
|
||||
| Wowa |
|
|||
|
Эксперт Профиль Группа: Админ Сообщений: 15017 Регистрация: 14.9.2000 Где: Винград Репутация: 1 Всего: 290 |
несколько это сколько? |
|||
|
||||
| skyboy |
|
|||
|
неОпытный Профиль Группа: Модератор Сообщений: 9820 Регистрация: 18.5.2006 Где: Днепропетровск Репутация: 5 Всего: 260 |
Wowa, неограничено. Структура деревянная хранит структуру полей объявления. Некоторые поля могут быть продублированы. Но суть не в том. А в том, что мне надо хранить данные отдельно от структуры, иначе получается дублирование данных. Идентификаторы полей я использовать не могу, потому как в дереве данных объявления(пускай будет раздел "обмен квартир") поле, к примеру, "количество комнат" будет входить не менее двух раз(кол-во комнат в меняемой квартире и в предполагаемой), но по дереву данных мы приходим к одному и тому же идентификатору поля, а ведь по смыслу это совсем разное. А по структуре они(поля) отличаются только путём достижения от корня - к количеству комнат целевой квартиры подходим через узел "квартира, которую ищу", а к количеству комнат имеющейся квартиры через узел "меняю квартиру"....
|
|||
|
||||
| LSD |
|
|||
 Leprechaun Software Developer Профиль Группа: Модератор Сообщений: 15719 Регистрация: 24.3.2004 Где: Dublin Репутация: 24 Всего: 538 |
Используй кросс и добавь туда поле с указанием типа связи: например указание, что это комнаты для меняемой квартиры или наоборот, для предполагаемой.
-------------------- Disclaimer: this post contains explicit depictions of personal opinion. So, if it sounds sarcastic, don't take it seriously. If it sounds dangerous, do not try this at home or at all. And if it offends you, just don't read it. |
|||
|
||||
| Cashey |
|
|||
 Бессмертный Профиль Группа: Завсегдатай Сообщений: 3441 Регистрация: 13.11.2002 Где: в столице Репутация: нет Всего: 60 |
Связь много-ко-многим. Храни сожержимое в отдельной таблице и еще в одной таблице храни идентификаторы записей из таблицы структуры и из таблицы с содержимым -------------------- библия учит любить ближнего, а камасутра обучает как именно |
|||
|
||||
| skyboy |
|
|||
|
неОпытный Профиль Группа: Модератор Сообщений: 9820 Регистрация: 18.5.2006 Где: Днепропетровск Репутация: 5 Всего: 260 |
давайте попробуем абстрагироваться от ТЗ и всяких там объявлений. И придумаем "универсальную" структуру для хранения данных уже не в дереве, а в графе с циклами. Вот на схеме набросал возможный вариант структуры. Как в этом случае хранить данные? Сам я реализовал вроде предложенного LSD, только храню не тип, а, фактически, весь путь по дереву(графу), который надо пройти, чтоб добраться до значения. Например для значения d я могу указать "1*1 3*1 7*1 8*1 d*1" или "1*1 2*1 4*1 7*1 8*1 d*1". "*1" надо для того, чтоб разрешить коллизии в случае, если ветка дерева может дублироваться(как можно ввести, например, в базу несколько телефонов, неограниченного количества). Если я захочу продублировать ветку 3, то данные будут в
"1*1 3*1 7*1 8*1 d*1" и "1*1 3*2 7*1 8*1 d*1" - для поля "d" и так же для остальных полей... Вот только парсить строку потом долго. Но если разбить на пары и хранить в базе в числовом виде, то: а) будет фактически копия исходной структуры - зачем дублировать информацию б) для работы всё равно придётся собирать дерево - а SQL слабо подготовлен к подобным операциям Вобщем, тупик  Добавлено @ 11:19
как мне определить однозначно каждую вариацию листа? всё-таки, неверно я деревом свою структуру назвал Это граф. Однозначно - направленный. Но с возможными циклами. Присоединённый файл ( Кол-во скачиваний: 13 ) 
graph.png 5,30 Kb |
|||
|
||||
| chief39 |
|
||||
 карманная тигра Профиль Группа: Участник Клуба Сообщений: 1631 Регистрация: 20.5.2005 Где: Киев Репутация: 8 Всего: 77 |
Переведём на аналог - файловую систему.
Имеется в виду, "содержимое" - это "лист" или "в т.ч. и ветка", которая содержит ветви? То есть: а) есть дерево, и любой "лист" может копировать значение иного листа. б) ветка может содержать в себе другую ветку, которая ещё до неё кем-то содержалась? В варианте а) лучше сделать по примеру жёстких ссылок в линуховых FS В варианте б) - многие-ко-многим "ребёнок-родитель". Правда... могут быть зацикленности.... "когда папа является сыном соседа, а сын соседа - твоим папой".... -------------------- Люди - это свечи. Они либо горят, либо их - в жопу!(с) |
||||
|
|||||
| Cashey |
|
|||
|
Бессмертный Профиль Группа: Завсегдатай Сообщений: 3441 Регистрация: 13.11.2002 Где: в столице Репутация: нет Всего: 60 |
skyboy, я так и не понимаю в чем тупик? У тебя практически обычное дерево, с наследованием. Единственное только у тебя один наследник может быть от разных "родителей". Для этого создаем связь много-ко-многим. Реализуя либо связующей таблицей, либо хранением guid через разделитель. Но второй способ явно неконструктивный.
Тебе надо создать (лучше использовать уже созданные) алгоритм присваения уникального значения. И у тебя получится 4 таблицу В первой у тебя будет хранится структура дерева, где у кадой записи будет уникальный идентификатор, уровень вложенности. Во второй будет 2 поля guid каждой записи из первой таблицы и guid "родительской" записи из той же таблицы. Это нужно, что бы отследить несколько "родителей" каждой ветви дерева. В третей таблице будут хранится описания для каждой ветви И четвертая будет по структуре копия второй, только хранить она будет guid из первой и привязанный к нему guid из третий таблицы. Понятно? -------------------- библия учит любить ближнего, а камасутра обучает как именно |
|||
|
||||
| skyboy |
|
|||
|
неОпытный Профиль Группа: Модератор Сообщений: 9820 Регистрация: 18.5.2006 Где: Днепропетровск Репутация: 5 Всего: 260 |
не "от разных", а от "нескольких". Причём - одновременно. Например, структура номера телефона может наследоваться от ветви "Я" и от ветви "Мой брат". Т.к. структура всё равно едина, то уникальный идентификатор листа "телефон" в пределах структуры будет неуникален. И, запомнив телефон, будет неясно, к какой подветви относятся данные. Потому - либо делать все листья уникальными(в общем случае - бессмысленно, т.к. одна и та же структура может входить в родительскую структуру в разных вариациях, и дублировать структуру - нерационально), либо же каким-то образом запоминать весь путь восстановления данных - т.е. фактически запоминать структуру. И опять же про телефон - у каждого из нас с братом может быть не один номер телефона. Это аргумент в пользу динамической структуры в противовес жестко заданной, но с уникальными идентификаторами. |
|||
|
||||
| Cashey |
|
|||
|
Бессмертный Профиль Группа: Завсегдатай Сообщений: 3441 Регистрация: 13.11.2002 Где: в столице Репутация: нет Всего: 60 |
Боже, ну чего не понятно?!
Таблица 1 GUID Название Уровень g1 Папа 1 g2 Я 2 g3 Мой брат 2 Таблица 2 child_guid parent_guid g2 g1 g3 g1 Таблица 3 GUID Содержание g11 01 g12 02 g13 03 Таблица 4 child_guid parent_guid g11 g2 g12 g2 g12 g3 g13 g3 Ну и тянем 2-мя JOIN'ами
Добавлено @ 23:09 Вторая таблица будет служить для поиска множества "потомков" млм "родителей". Хотя можно обойтись и без нее, храня "родительский" GUID в Таблице 1 -------------------- библия учит любить ближнего, а камасутра обучает как именно |
|||
|
||||
| xml |
|
||||||||||
|
Новичок Профиль Группа: Участник Сообщений: 2 Регистрация: 21.7.2006 Репутация: нет Всего: нет |
Согласен, чисто реляционные БД - очень неудобный инструмент для работы с иерархическими структурами. Дело не только в ручной идентификации каждой вершины. Поиск вершин по их относительному расположению в SQL-БД сводится к полному перебору дерева. Языковые инструменты также слабоваты. Все сводится к чему-то типа SELECT LEVEL, name FROM employees START WITH name = 'Mary' CONNECT BY PRIOR emp_no = mgr_no Больше подходит XQuery и Zigzag. Последний мне даже кажется более выразительным. Например, то что в XML выглядит так
На Zigzag можно представить
На Zigzag запросы и утверждения, задающие новые связи, выглядят почти одинаково: = A:B A:B = Сравните запросы "найти все вершины с атрибутом a='b'" XQuery
Zigzag
На сколько мне известно для Zigzag и XQuery созданы очень мощные средства индексации, позволяющие обходиться без полного перебора дерева при выполнении запроса. |
||||||||||
|
|||||||||||
| skyboy |
|
|||
|
неОпытный Профиль Группа: Модератор Сообщений: 9820 Регистрация: 18.5.2006 Где: Днепропетровск Репутация: 5 Всего: 260 |
Cashey, я, видимо, плохо обьяснил. Ты мне привел в пример структуру дерево, в котором только как для меня, так и для брата, значеник g12 будет одинаковым, т.е. "02". А мне надо хранить в g12 со стороны родителя g2 одно значение(05), а со стороны родителя g3 - другое значение. Если не сложно, загляни в файл-схему приклреплённую к одному из предыдущих постов. Впрочем, её тоже можно понять неверно. a,b,c,d ... - это не значения. Это место для значения. Там должен стоять уникальный идентификатор значения, что-то типа указателя в ЯВУ. Так вот, этот "указатель" должен иметь разные значения, в зависимости от того, каким путём достигли его.
Добавлено @ 18:07 например, по пути 1-3-7 в "с" хранится 21, а по пути 1-2-4-7 в том же "с" "хранится" уже -48. |
|||
|
||||
| Cashey |
|
|||
|
Бессмертный Профиль Группа: Завсегдатай Сообщений: 3441 Регистрация: 13.11.2002 Где: в столице Репутация: нет Всего: 60 |
ну так я так и понял и мой пример именно это и реализует. g12 это идентификатор именно значения "02". А "05" это уже другое знаечение и у него должен быть свой уникальный идентификатор, например g15. А вот то какое значение будет у родителя определяется уже в 4-й таблице/ У одного значения никак не может быть одинаковый идентификатор, да и не может быть задачи, которая этого может потребовать. А вот получить различные значения можно определив к одному родителя несколько значений -------------------- библия учит любить ближнего, а камасутра обучает как именно |
|||
|
||||
| skyboy |
|
||||||
|
неОпытный Профиль Группа: Модератор Сообщений: 9820 Регистрация: 18.5.2006 Где: Днепропетровск Репутация: 5 Всего: 260 |
Cashey, ты понял постановку не мою, а Wowa. Я же эту постановку расширил. Потому специально прикрепил схему и описал, что и как.
Я понял. Потому и сказал, что это - не моё. Это, если я правильно понял, nested sets, да? А мне надо более универсальное решение. Впрочем, как мне кажется уж лучше хранения пути не будет ничего
Чего-чего? 
Да ну?  Надо же: думать-думаю, решать-решаю, а задачи - нет... |
||||||
|
|||||||
| Cashey |
|
|||
|
Бессмертный Профиль Группа: Завсегдатай Сообщений: 3441 Регистрация: 13.11.2002 Где: в столице Репутация: нет Всего: 60 |
skyboy, ты должен понять одну вещь. Значение ВСЕГДА либо одно, либо несколько. Если их несколько, то они ВСЕГДА отличаются друг от друга (т.е. "2", "2", "2" - это все одно значение; а "01", "02", "03" - это 3 разных значения). И здесь не может и не должно быть ничего другого. А вот то, какое из этих значений будет соответсвовать ветвям твоего дерева, при каких-то условиях описывается отдельно.
-------------------- библия учит любить ближнего, а камасутра обучает как именно |
|||
|
||||
| skyboy |
|
||||
|
неОпытный Профиль Группа: Модератор Сообщений: 9820 Регистрация: 18.5.2006 Где: Днепропетровск Репутация: 5 Всего: 260 |
Это ты к чему? А 1 - в любой системе счисления = 1? поясни, что ты имел в виду. Если касательно моей задачи, то мне надо разделить граф, как структуру и сами данные, связанные с разными полями. Граф был раньше деревом, но т.к. в нём были полностью идентичные ветви, то я эти ветви "свернул"(как сам сказал
И после этого потерялась уникальность узлов: те данные, которые раньше относились к разным узлам после сворачивания стали относится к одним и тем же. В этом заключалась проблема, и я искал решение, альтернативное запоминанию полного пути. Вот. И всё. |
||||
|
|||||
| Cashey |
|
||||
|
Бессмертный Профиль Группа: Завсегдатай Сообщений: 3441 Регистрация: 13.11.2002 Где: в столице Репутация: нет Всего: 60 |
я имел ввиду, что единиц может быть сколько угодно, но это все равно останется единица ( я не имею ввиду сложение).
Я упорно не могу тебя понять (или понять, чего не понимаешь ты) Тебе достаточно будет хранить только идентификатор родительских ветвей. А зачем весь путь не понимаю, это ты их будешь раскручивать на каждом шаге формирования дерева. А вообще, давай сначало. Тебе надо сформировать свой граф снизу или сверху т.е. от корней или от ветвей? -------------------- библия учит любить ближнего, а камасутра обучает как именно |
||||
|
|||||
| skyboy |
|
||||||
|
неОпытный Профиль Группа: Модератор Сообщений: 9820 Регистрация: 18.5.2006 Где: Днепропетровск Репутация: 5 Всего: 260 |
в смысле - я сам себя не понимаю? 
мне надо храниться не для узлов дерева(точнее, графа), а для каждого хранимого значения.
Граф я формирую сверху. По мере формирования, набираю в эту структуру значения. Вот тут-то мне и приходится(приходилось?) хранить полный путь. Потому как при формировании дерева на узел с условным идентификатором 222 я могу выйти и на втором уровне рекурсии, и на 42, причём, узел будет один и тот же(характеристики, свойственные именно этому узлу будут общие, вне зависимости от уровня рекурсии - уровня графа), но данные в этом узле будут разные. |
||||||
|
|||||||
| Cashey |
|
|||
|
Бессмертный Профиль Группа: Завсегдатай Сообщений: 3441 Регистрация: 13.11.2002 Где: в столице Репутация: нет Всего: 60 |
Ну вот ты сам пишешь правильные слова - с условным идентификатором. Я так понимаю, что хоть на 2-м, хоть на 42-м, хоть на 142-м шаге ты выходишь все равно на этот идентификатор? Данные будут разные? Не проблема, а по какому принципу они будут отличатся? -------------------- библия учит любить ближнего, а камасутра обучает как именно |
|||
|
||||
| skyboy |
|
||||||
|
неОпытный Профиль Группа: Модератор Сообщений: 9820 Регистрация: 18.5.2006 Где: Днепропетровск Репутация: 5 Всего: 260 |
Дать тебе ещё ссылки на "правильные слова" вроде "дерево" или "граф"? А что, раньшене правильно говорил?
не совсем "шаг". Это - почти "уровень". С той лишь разницей, что один и тото же узел может иметь одновременно несколько различных значений этого "уровня", те. будет достигаем за различное количество шагов, принимая за точку отсчёта вершину графа.
данные-то? а данные - произвольны Это могут быть адреса, номера телефонов, фамилии... По какому принципу могут отличаться друг от друга две фамилии?  |
||||||
|
|||||||
| Cashey |
|
||||||
|
Бессмертный Профиль Группа: Завсегдатай Сообщений: 3441 Регистрация: 13.11.2002 Где: в столице Репутация: нет Всего: 60 |
а мне уже показалось, что ты начал понимать то, что я хочу донести
фамилии то пусть будут произвольными, а вот по какому принципу конкретная фамилия должна соответствовать конкретному узлу? т.е почему
? -------------------- библия учит любить ближнего, а камасутра обучает как именно |
||||||
|
|||||||
| skyboy |
|
|||
|
неОпытный Профиль Группа: Модератор Сообщений: 9820 Регистрация: 18.5.2006 Где: Днепропетровск Репутация: 5 Всего: 260 |
если у меня НЕ дерево, а граф(скажем так, направленный: т.е. как такого направления в логике структуры нет, но когда я обрабатываю структуру, я не могу "идти против потока", во время перебора узлов), то в этом графе одного и того же узла можно достигнуть разными "путями"(пройдя через различную последовательность узлов). Так вот, в заваисимости от этого "пройденного" пути, как раз и выбираются те или иные данные.
да я-то понял, что ты хочешь донести. Именно потому уже неоднократно говорил, что это - не то. Ты мне предлагаешь дерево, с однозначной структурой и однозначной привязкой данных. Моя же структура НЕ дерево. Однозначна только изначально. В каждой своей "реализации"(наполнении данными) структура будет(может быть) уже другой. Не кардинально, но значительно: некоторые узлы продублируются, некоторые - отбросятся... |
|||
|
||||
| Cashey |
|
|||
|
Бессмертный Профиль Группа: Завсегдатай Сообщений: 3441 Регистрация: 13.11.2002 Где: в столице Репутация: нет Всего: 60 |
skyboy, у меня складывается впечатление, что идет разговор глухого с немым
то, что ты нарисовал на схеме является деревом, а ни каким не графом. и, как я понял, определение значения идет по тому, кто я вляется уровнем +1 для выбранной ветви данных. почему тебя клинит на каких-то графах я никак не пойму. думаю, будет лучше если ты опишешь всю задачу. тогда будет легче помочь тебе с алгоритмом ее решения. -------------------- библия учит любить ближнего, а камасутра обучает как именно |
|||
|
||||
| pythonwin |
|
|||
 Эксперт Профиль Группа: Участник Сообщений: 2529 Регистрация: 18.4.2006 Где: за компом Репутация: 1 Всего: 36 |
Ничего не понимаю...
Вы тут, что ли рекурсию в БД обсуждаем? |
|||
|
||||
|
|
| Правила форума "Общие вопросы по базам данных" | |
|
|
Данный форум предназначен для обсуждения вопросов о базах данных не попадающих под тематику других форумов:
Данный форум не предназначен для:
Если вы не соблюдаете эти правила, не удивляйтесь потом не найдя свою тему/сообщение.
Полезные советы: Если Вам понравилась атмосфера форума, заходите к нам чаще! С уважением, LSD, Zloxa. |
| 0 Пользователей читают эту тему (0 Гостей и 0 Скрытых Пользователей) | |
| 0 Пользователей: | |
| « Предыдущая тема | СУБД, общие вопросы | Следующая тема » |
[ Время генерации скрипта: 0.1183 ] [ Использовано запросов: 22 ] [ GZIP включён ]
Реклама на сайте Информационное спонсорство
|
|
По вопросам размещения рекламы пишите на vladimir(sobaka)vingrad.ru
Отказ от ответственности Powered by Invision Power Board(R) 1.3 © 2003 IPS, Inc. |