ReSQL.ru
     
powered by simpleCommunicator - 2.0.61     © 2026 Programmizd 02
Мобильная версия    Контакт    Правила    FAQ    Помощь
Целевая тема:
Создать новую тему:
Автор:
Закрыть
Цитировать
Доб. в избранное | Игнор. тему | Прикреп. тему | Пометить прочит. / непрочит. | Фильтр
Форумы / Проектирование БД [игнор отключен] [закрыт для гостей] / Древовидная структура БД основанная на связанном списке.
22 сообщений из 22, страница 1 из 1
Древовидная структура БД основанная на связанном списке.
    #35046328
Страдалецъ
Скрыть профиль Поместить в игнор-лист Сообщения автора в теме
Страдалецъ
Участник
Вот такая мысль меня посетила. (скорее всего это уже где-то было)
Представим себе, что в БД есть только 2 таблицы.
1. Словарь (Код:Number,Понятие:Varchar,Словарь:Varchar)
2. Связь (Предок:Number,Потомок:Number) в которой Предок и Потомок справочные значения из таблицыСправочник. Добавим еще связь Связь.Потомок->Словарь.Код и связь Словарь.Код->Связь.Предок

Тогда получается интересная связка в которой можно описать, если не все, то очень много.
Например так выглядит такая схема в Кроносе.
...
Рейтинг: 0 / 0
06.01.2008, 14:15
| Ответить | Цитировать | Написать  
Древовидная структура БД основанная на связанном списке.
    #35046574
Румата
Скрыть профиль Поместить в игнор-лист Сообщения автора в теме
Румата
Участник
Надо еще оценить, наверное, время операций основных. Вставка, удаление, поиск...

А что хотели получить? Просто способ представление адреса?
...
Рейтинг: 0 / 0
06.01.2008, 19:56
| Ответить | Цитировать | Написать  
Древовидная структура БД основанная на связанном списке.
    #35046588
Страдалецъ
Скрыть профиль Поместить в игнор-лист Сообщения автора в теме
Страдалецъ
Участник
Верно, начинал именно под адрес, а в итоге получилось более интересное решение. Под эту схему спокойно подпадает любой транспорт, любой товар/предмет, оружие и т.д. Даже Лицо и его связи в принципе можно рассматривать в таком представлении. Получилась этакая гиперлинковая база, где через ссылку на предка/потомка можно получить всю возможную информацию об объекте.
Вот такакя загогулина 8-D
...
Рейтинг: 0 / 0
06.01.2008, 20:17
| Ответить | Цитировать | Написать  
Древовидная структура БД основанная на связанном списке.
    #35046627
Фотография softwarer
Скрыть профиль Поместить в игнор-лист Сообщения автора в теме
softwarer
Участник
Страдалецъскорее всего это уже где-то было

Тогда получается интересная связка в которой можно описать, если не все, то очень много.
Да, было, без малого полвека назад. Если добавить к этой замечательной идее мало-мальски адекватную реализацию, Вы получите иерархическую БД. Потом, если помните, вместо нее придумали более продвинутую - сетевую, потом еще более продвинутую - реляционную.
...
Рейтинг: 0 / 0
06.01.2008, 21:38
| Ответить | Цитировать | Написать  
Древовидная структура БД основанная на связанном списке.
    #35046634
Страдалецъ
Скрыть профиль Поместить в игнор-лист Сообщения автора в теме
Страдалецъ
Участник
А теперь на Реляционной модели я построил древовидную, что подтверждает теорию эволюции по спирали. :-)
...
Рейтинг: 0 / 0
06.01.2008, 21:59
| Ответить | Цитировать | Написать  
Древовидная структура БД основанная на связанном списке.
    #35046657
Бабай
Скрыть профиль Поместить в игнор-лист Сообщения автора в теме
Бабай
Участник
мало понятно существо мысли.
в зависимости от способа чтения она (мысль) либо тривиальна либо высказана не полностью.

в той части, что связи между сущностями ( в предположении, что таблица [Словарь] представляет некую сущность) существуют в реляционной бд в виде таблиц - мысль тривиальна.
Что называется - откройте учебник.
(Это не в целях излишнего менторства, - я не нашел удачной формы для обозначения того факта,
что таблица связи к таблице сущностей не стоила начала отдельного топика.)

В той части, что представляемая схема описывает "если не все, то очень много" все становится неясно и недосказанно.

Предположительно либо поле Словарь таблицы [Словарь] : [Словарь](Словарь:Varchar)
либо поле Категория: [Словарь](Категория: Varchar)
должно сегментировать таблицу Словарь на логически разные классы, которые можно мысленно представить находящимися в разных таблицах-представлениях сущностей
В данном случае вероятная экономия состоит в экономии количества таблиц связей.

Главный вопросы к такой схеме:
- какой арности отношения описываются этой схемой в целом?
- (если любой, то) каков механизм объявления и поддержки заявленной арности?

Отсутствие (если вдруг) такого механизма означает отсутствие системы поддержки целостности информации в такой БД.
Попытка использования стандартных, встроенных в БД механизмов (индексы + FK) наложит ограничение на тип связи и сведет применимость схемы от "очень много" до конкретного случая.


вообще же, по сабжу много Garya размышлял. на русьимпорте есть картинки ( и вроде тезисы - лень искать) к его докладу, в котором он пытается вдохнуть жизнь в подобного сорта схематику.

Но главного - платить рождением собственных механизмов управления в ответ на отказ от, говоря неформально, принипов разлождения информации по полкам, "даже он" не может избежать.
...
Рейтинг: 0 / 0
06.01.2008, 22:41
| Ответить | Цитировать | Написать  
Древовидная структура БД основанная на связанном списке.
    #35046708
Фотография softwarer
Скрыть профиль Поместить в игнор-лист Сообщения автора в теме
softwarer
Участник
СтрадалецъА теперь на Реляционной модели я построил древовидную, что подтверждает теорию эволюции по спирали. :-)
Да, в одном прискорбно частом варианте. Проиллюстрирую его примером:

Шаг 1. Берем молоток и забиваем гвоздь
Шаг 2. Придумываем более удобные для автоматизации методы соединения (например, клепку и сварку) и оборудование для них.
Шаг 3. Придумываем робота, умеющего соединять детали десятком разных техник.
Шаг 4. Даем ему в руки молоток.
...
Рейтинг: 0 / 0
07.01.2008, 00:30
| Ответить | Цитировать | Написать  
Древовидная структура БД основанная на связанном списке.
    #35046736
Страдалецъ
Скрыть профиль Поместить в игнор-лист Сообщения автора в теме
Страдалецъ
Участник
А я и не претендую на роль революционера в этой области. Это скорее просто вариант который может быть кому-то, где-то пригодится. Сваять что-то законченное только на подобной модели мне и самому затруднительно. Мне пока тоже непонятен механизм удобного поиска по такому дереву. Что касается ввода, удаления и т.д - здесь все нормально, я ведь схему брал из живой БД.
Но что мне нравиться, это то что более удобного и гибкого способа хранения адресной информации я пока невидел.
...
Рейтинг: 0 / 0
07.01.2008, 01:47
| Ответить | Цитировать | Написать  
Древовидная структура БД основанная на связанном списке.
    #35046740
Румата
Скрыть профиль Поместить в игнор-лист Сообщения автора в теме
Румата
Участник
СтрадалецъА я и не претендую на роль революционера в этой области. Это скорее просто вариант который может быть кому-то, где-то пригодится. Сваять что-то законченное только на подобной модели мне и самому затруднительно. Мне пока тоже непонятен механизм удобного поиска по такому дереву. Что касается ввода, удаления и т.д - здесь все нормально, я ведь схему брал из живой БД.
Но что мне нравиться, это то что более удобного и гибкого способа хранения адресной информации я пока не видел.

Дерево будет несбалансировано, а значит и ряд проблем возникнет... Гибко - может быть, но вот время доступа - непонятно пока.
...
Рейтинг: 0 / 0
07.01.2008, 02:25
| Ответить | Цитировать | Написать  
Древовидная структура БД основанная на связанном списке.
    #35047081
nik_x
Скрыть профиль Поместить в игнор-лист Сообщения автора в теме
nik_x
Участник
СтрадалецъА теперь на Реляционной модели я построил древовидную, что подтверждает теорию эволюции по спирали. :-)

Эволюция велосипеда???
Буквари читать пробовал?
Хотя бы на примере Oracle.
Для начала с фразы CONNECT BY PRIOR.
...
Рейтинг: 0 / 0
07.01.2008, 14:55
| Ответить | Цитировать | Написать  
Древовидная структура БД основанная на связанном списке.
    #35047152
apapacy
Скрыть профиль Поместить в игнор-лист Сообщения автора в теме
apapacy
Участник
softwarer Если добавить к этой замечательной идее мало-мальски адекватную реализацию, Вы получите иерархическую БД. Потом, если помните, вместо нее придумали более продвинутую - сетевую, потом еще более продвинутую - реляционную.
По топу - согласен с Вами на все 100%. Но по оценке моделей данных - нет. Реляционная модель сейчас имеет отличную теоретическую базу, выдающиеся реализации и повсеместное распространение. Но не является вершиной "от иерархических к сетевым и реляционным БД".
В частности, отсутствие удобной реализации работы с tree в реляционных БД (ANSI-SQL) - симптом того, что операторы работы с иерархическими данными нужны и не получили адекватную замену иерархии на реляцию.
Хотя по сути иерархические отношения - это один из частных случаев отношений. Но запросы такого вида как "получить всех потомков для данного узла вглубину/вширину", "получить всех родителей", "получить корневой элемент", "проверить на ацикличность", "получить уровень листа" и т.п. в ANSI-SELECT не выражаются. (Хотя реализации я мельком где-то встречал в качестве расширения ANSI - не знаю насколько эффективные)
...
Рейтинг: 0 / 0
07.01.2008, 16:02
| Ответить | Цитировать | Написать  
Древовидная структура БД основанная на связанном списке.
    #35047285
Фотография softwarer
Скрыть профиль Поместить в игнор-лист Сообщения автора в теме
softwarer
Участник
apapacyВ частности, отсутствие удобной реализации работы с tree в реляционных БД (ANSI-SQL) - симптом того, что операторы работы с иерархическими данными нужны и не получили адекватную замену иерархии на реляцию.
Если коротко, Вы укоряете реляционные реализации тем, что работа с иерархиями в них реализована не лучше , чем в иерархических. Подчеркиваю: не "хуже", а "не лучше".

apapacyХотя по сути иерархические отношения - это один из частных случаев отношений.
Факт. И?

apapacyНо запросы такого вида как "получить всех потомков для данного узла вглубину/вширину", "получить всех родителей", "получить корневой элемент", "проверить на ацикличность", "получить уровень листа" и т.п. в ANSI-SELECT не выражаются.
Во-первых, если мне не изменяет память, в SQL2003 уже выражаются. Во-вторых, апелляция к ANSI SQL в таком контексте здорово напоминает капитуляцию. Ну и наконец, допустим, не выражаются - и что из этого? В иерархических БД это тоже отнюдь не атомы, а "подпрограммы".
...
Рейтинг: 0 / 0
07.01.2008, 17:54
| Ответить | Цитировать | Написать  
Древовидная структура БД основанная на связанном списке.
    #35047555
apapacy
Скрыть профиль Поместить в игнор-лист Сообщения автора в теме
apapacy
Участник
Штудирую SQL2003. Пока не нашел способа запрашивать деревья. Если кто может просветить подробнее - сделайте это.

Тут ведь дело не только в синтаксисе - важнее эффективность запросов. Tree - должно поддерживаться как 1) Тип данных 2) Язык запросов 3) Поддержка ускорения доступа к операциям над деревьями (что-то вроде индексов).

Кстати IMS по-прежнему жива и, более того, используется - судя по наличным вакансиям - у нас. И IMS v10 идет в сторону ООБД.
...
Рейтинг: 0 / 0
07.01.2008, 23:42
| Ответить | Цитировать | Написать  
Древовидная структура БД основанная на связанном списке.
    #35047643
Фотография softwarer
Скрыть профиль Поместить в игнор-лист Сообщения автора в теме
softwarer
Участник
apapacyШтудирую SQL2003. Пока не нашел способа запрашивать деревья.
Я не помню термина, суть - рекурсивная ссылка в кляузе WITH. Что-то типа

Код: plaintext
1.
2.
3.
with
  a as (select t.id from table t, a where t.parent_id = a.id)
select
  ...

Мне так кажется, это уже включено в стандарт, хотя клясться не буду.

apapacyТут ведь дело не только в синтаксисе - важнее эффективность запросов.
Если мы говорим про эффективность, ANSI SQL тем более совершенно не при чем :)

apapacyTree - должно поддерживаться как 1) Тип данных
Спорно, весьма спорно. Деревья могут быть представлены несколькими разными реляционными структурами, у каждой свои достоинства. Будет ли "специальный тип данных" соединять эти достоинства и избегать недостатков - спорный вопрос.
...
Рейтинг: 0 / 0
08.01.2008, 01:51
| Ответить | Цитировать | Написать  
Древовидная структура БД основанная на связанном списке.
    #35047659
Бабай
Скрыть профиль Поместить в игнор-лист Сообщения автора в теме
Бабай
Участник
автор1) тип данных...
так кажется, что применительно к задаче Страдальца, как я ее впонял на текущий момент,
заявление дерева как типа данных полностью эквивалентно записи адреса в виде простой строки:

"г. Гатчина, Ингерманландской губернии, ул. Бульварная д xx/yy, Коробочке Настасье Петровне."

с присобаченными к этой строке операциями вида "Извлечь из адреса город", "Извлечь ... улицу" и т.п.

Сам по себе такой тип в любом представлении (напр. хемеель) имеет право быть.
Вот только воспользоваться именно им в качестве верификатора/построителя его же содержимого вряд ли получится. Понадобится либо еще один тип, либо та или иная реляционно-множественная конструкция, задающая мир допустимых адресов.
...
Рейтинг: 0 / 0
08.01.2008, 02:56
| Ответить | Цитировать | Написать  
Древовидная структура БД основанная на связанном списке.
    #35049236
_мод
Скрыть профиль Поместить в игнор-лист Сообщения автора в теме
_мод
Гость
Страдалецъскорее всего это уже где-то было
Ессно - мумпс называется.
...
Рейтинг: 0 / 0
09.01.2008, 10:16
| Ответить | Цитировать | Написать  
Древовидная структура БД основанная на связанном списке.
    #35049251
_мод
Скрыть профиль Поместить в игнор-лист Сообщения автора в теме
_мод
Гость
apapacyКстати IMS по-прежнему жива
В IMS нет средств для работы с деревьями (а в оракле есть).
зы вы путаете ИМД и возможность работы с деревьями - это вещи не связанные.
...
Рейтинг: 0 / 0
09.01.2008, 10:22
| Ответить | Цитировать | Написать  
Древовидная структура БД основанная на связанном списке.
    #35050015
KGP
Скрыть профиль Поместить в игнор-лист Сообщения автора в теме
KGP
Участник
softwarer apapacyВ частности, отсутствие удобной реализации работы с tree в реляционных БД (ANSI-SQL) - симптом того, что операторы работы с иерархическими данными нужны и не получили адекватную замену иерархии на реляцию.
Если коротко, Вы укоряете реляционные реализации тем, что работа с иерархиями в них реализована не лучше , чем в иерархических. Подчеркиваю: не "хуже", а "не лучше".


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

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

ps: по аналогии полнотекстовый поиск реализуется не через некий продвинутый оператор like, а отдельным сервисом.
...
Рейтинг: 0 / 0
09.01.2008, 14:05
| Ответить | Цитировать | Написать  
Древовидная структура БД основанная на связанном списке.
    #35050164
Фотография softwarer
Скрыть профиль Поместить в игнор-лист Сообщения автора в теме
softwarer
Участник
KGPдля меня очевидно, что все же отдельная ветка объектно-ориентированных серверов баз данных (в том числе и с поддержкой иерархий) будет развиваться.
Бесспорно. Хотя иерархии тут имхо особо не при чем :)

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

KGPps: по аналогии полнотекстовый поиск реализуется не через некий продвинутый оператор like, а отдельным сервисом.
Ну, в Oracle это называется именно оператором

Мне кажется, тут Вас очень неудачно перекашивает. SQL - декларативный язык, решения на нем подчеркнуто дистанциированы от реализации и допускают разные варианты физической реализации. Это то требование, которое должно быть сохранено и при реализации полнотекстового поиска, и при реализации деревьев. Появление в языке "операторов работы с деревьями" - в принципе независимо от появления в архитектуре "продвинутого хранилища деревьев", хотя в идеале они должны уметь особенно хорошо работать в паре.
...
Рейтинг: 0 / 0
09.01.2008, 14:45
| Ответить | Цитировать | Написать  
Древовидная структура БД основанная на связанном списке.
    #35050213
KGP
Скрыть профиль Поместить в игнор-лист Сообщения автора в теме
KGP
Участник
softwarer
Мне кажется, тут Вас очень неудачно перекашивает. SQL - декларативный язык, решения на нем подчеркнуто дистанциированы от реализации и допускают разные варианты физической реализации. Это то требование, которое должно быть сохранено и при реализации полнотекстового поиска, и при реализации деревьев. Появление в языке "операторов работы с деревьями" - в принципе независимо от появления в архитектуре "продвинутого хранилища деревьев", хотя в идеале они должны уметь особенно хорошо работать в паре.

не заметил, да и в праздники воздерживался
имхо в ms sql 2005 поддержка именно 'операторная', или вы уверены, что при работе с иерархией применяется что-то архитектурно новое?
...
Рейтинг: 0 / 0
09.01.2008, 15:00
| Ответить | Цитировать | Написать  
Древовидная структура БД основанная на связанном списке.
    #35050692
Фотография LR
Скрыть профиль Поместить в игнор-лист Сообщения автора в теме
LR
Участник
Кстати, в mssql2008 появился _тип данных_ hierarchyid, со всеми необходимыми "деревянными" методами ("императивными", т.е. поддержка не 'операторная', если я правильно понял смысл этого термина как "декларативность"), инкапсулирующий иерархические отношения (между записями одной таблицы).
Т.е. еще один, помимо рекурсивных CTE, "инструментарий", если здесь
KGPимхо в ms sql 2005 поддержка именно 'операторная'они имелись в виду.
...
Рейтинг: 0 / 0
09.01.2008, 16:47
| Ответить | Цитировать | Написать  
Древовидная структура БД основанная на связанном списке.
    #35050726
KGP
Скрыть профиль Поместить в игнор-лист Сообщения автора в теме
KGP
Участник
LR
Кстати, в mssql2008 появился _тип данных_ hierarchyid, со всеми необходимыми "деревянными" методами ("императивными", т.е. поддержка не 'операторная', если я правильно понял смысл этого термина как "декларативность"), инкапсулирующий иерархические отношения (между записями одной таблицы).
Т.е. еще один, помимо рекурсивных CTE, "инструментарий", если здесь
KGPимхо в ms sql 2005 поддержка именно 'операторная'они имелись в виду.

кратно и имхо удачно

hierarchyid уже шаг более архитектурный, чем что-то типа

Код: plaintext
1.
2.
with
  a as (select t.id from table t, a where t.parent_id = a.id)
select
...
Рейтинг: 0 / 0
09.01.2008, 16:55
| Ответить | Цитировать | Написать  
22 сообщений из 22, страница 1 из 1
Форумы / Проектирование БД [игнор отключен] [закрыт для гостей] / Древовидная структура БД основанная на связанном списке.
Найденые пользователи ...
Разблокировать пользователей ...
Читали тему (0):
Читали форум (0):
Пользователи онлайн (0):
Польз. соглашение   Полит. конфиден.  
NoSQL.ru       Кролег: Проекты, Новости, Чат       РЕД ФОРУМ       Фотоальбом: Участники, Встречи
Закрыть
start [/forum/topic.php?fid=32&msg=35047081&tid=1544100]:
 0ms
get settings:
 7ms
get forum list:
 16ms
check forum access:
 3ms
check topic access:
 3ms
track hit:
 23ms
get topic data:
 9ms
get forum data:
 3ms
get page messages:
 71ms
get tp. blocked users:
 1ms
others: 225ms
total:  361ms
созд. / загр.: 361ms
x
x
Закрыть


Просмотр
0 / 0
Close
Debug Console [Select Text]