ReSQL.ru
     
powered by simpleCommunicator - 2.0.61     © 2026 Programmizd 02
Мобильная версия    Контакт    Правила    FAQ    Помощь
Целевая тема:
Создать новую тему:
Автор:
Закрыть
Цитировать
Доб. в избранное | Игнор. тему | Прикреп. тему | Пометить прочит. / непрочит. | Фильтр
Форумы / Проектирование БД [игнор отключен] [закрыт для гостей] / Быстрый сложный поиск по большому дереву
14 сообщений из 39, страница 2 из 2
  2  все
Быстрый сложный поиск по большому дереву
    #34661230
Бред
Скрыть профиль Поместить в игнор-лист Сообщения автора в теме
Бред
Участник
Sev_ReoУважаемые коллеги!
Прошу Вас, многопытных, помочь мне в следующей задаче.
Есть такая структура данных:
Код: plaintext
1.
2.
3.
4.
5.
6.
7.
8.
9.
10.
11.
12.
13.
14.
15.
create table Node (
	ID int,
	ParentNodeID int,
	Name varchar( 10 ),
	Attribute1 varchar( 10 ),
	Attribute2 varchar( 10 ),
	...
	Attribute10 varchar( 10 )
)

create table NodeProperty (
	ID int,
	NodeID int,
	Name varchar( 10 ),
	Value varchar( 10 )
)

Думаю, здесь очевидно, что колонки ID - это PK, а NodeProperty.NodeID - это FK на Node.ID.

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

Предполагается, что таблицы Node и NodeProperty будут заполнятся с интенсивностью ~ 1M и 10M записей в день соответственно.

Внимание, вопрос! Что нужно сделать с приведенной структурой и/или какие подходы к реализации самого процесса поиска использовать, чтоб после месяца работы приложения пользователь смог все-таки дождаться ответа на свой вопрос?

Заранее спасибо.

Наверное, можно попробовать Cache. Но творчески, а не как реляционный сервер.
...
Рейтинг: 0 / 0
16.07.2007, 14:23
| Ответить | Цитировать | Написать  
Быстрый сложный поиск по большому дереву
    #34661245
Sev_Reo
Скрыть профиль Поместить в игнор-лист Сообщения автора в теме
Sev_Reo
Гость
To guest_20040621 & Васильев Андрей :
Да с задачей все просто. Есть XML документы, которые надо хранить в базе и делать по ним различные поиски. This is it. Если вы желаете еще подробностей - спрашивайте.

To drev :
Спасибо за сцылку на хелп - обязательно вникну. Поддержка MSSQL2005 у нас случилась совсем недавно, так что XML data type не был еще достаточно изучен. Кстати, если Вам не составит труда, сориентируйте пожалуйста меня на оракловские аналоги - они тоже пригодятся, а опыта с ним (с ораклом) у меня тоже почти нет.
Специфика приложения такова, что оно должно поддерживать работу с MSSQL2005 и с Ораклом (молюсь, чтоб к этому не добавились всякие DB2, Информиксы и прочие монстры). Естественно, что, чем меньше различий будет в имплементации, тем лучше.
Что касается структуры данных. XML документы содержат ветки глубиной 3-7 уровней. Примерно такой структуры:
Код: plaintext
1.
2.
3.
4.
5.
6.
7.
A
+-B
  +-C
    +-D
      +-E
      +-E
      ...
      +-E
Проблема в том, что узлов Е в документе может быть от 1 до десятков/сотен тысяч. С определенной долей вероятности можно предсказать, что большинство узлов будет приходиться на документы, в которых большое количество листьев на одну ветку. Но количество документов с одним листом на одну ветку тоже может быть весьма значительным - тысячи/десятки тысяч (в день).
Насколько, по Вашему мнению, в этих условиях будет эффективно применение XML data type?
...
Рейтинг: 0 / 0
16.07.2007, 14:25
| Ответить | Цитировать | Написать  
Быстрый сложный поиск по большому дереву
    #34661302
guest_20040621
Скрыть профиль Поместить в игнор-лист Сообщения автора в теме
guest_20040621
Гость
> Есть XML документы, которые надо хранить в базе и делать по ним различные поиски.

Незачем хранить XML документы - и файлы вообще - в базе данных (за исключением очень специфичных случаев, о которых речь в данном случае не идет).
...
Рейтинг: 0 / 0
16.07.2007, 14:38
| Ответить | Цитировать | Написать  
Быстрый сложный поиск по большому дереву
    #34661322
Sev_Reo
Скрыть профиль Поместить в игнор-лист Сообщения автора в теме
Sev_Reo
Гость
guest_20040621> Есть XML документы, которые надо хранить в базе и делать по ним различные поиски.

Незачем хранить XML документы - и файлы вообще - в базе данных (за исключением очень специфичных случаев, о которых речь в данном случае не идет).

Растроган. Плачу.
...
Рейтинг: 0 / 0
16.07.2007, 14:43
| Ответить | Цитировать | Написать  
Быстрый сложный поиск по большому дереву
    #34661398
Bely
Скрыть профиль Поместить в игнор-лист Сообщения автора в теме
Bely
Участник
Sev_ReoTo guest_20040621 & Васильев Андрей :
Да с задачей все просто. Есть XML документы, которые надо хранить в базе и делать по ним различные поиски. This is it. Если вы желаете еще подробностей - спрашивайте.Какие данные в этих XML?
Можете показать примеры?
А также примеры поиска - не абстрактные, а более реальные.

Sev_ReoСпецифика приложения такова, что оно должно поддерживать работу с MSSQL2005 и с Ораклом (молюсь, чтоб к этому не добавились всякие DB2, Информиксы и прочие монстры). Естественно, что, чем меньше различий будет в имплементации, тем лучше.при таком раскладе, вам скорее всего не удасться избежать спкцифики БД.
В обработке XML - уж точно.


Sev_Reo guest_20040621> Есть XML документы, которые надо хранить в базе и делать по ним различные поиски.

Незачем хранить XML документы - и файлы вообще - в базе данных (за исключением очень специфичных случаев, о которых речь в данном случае не идет). Растроган. Плачу.Побольшей части гость прав - хранить лучше не файлы, а данные из файлов.
...
Рейтинг: 0 / 0
16.07.2007, 15:02
| Ответить | Цитировать | Написать  
Быстрый сложный поиск по большому дереву
    #34661443
Фотография MasterZiv
Скрыть профиль Поместить в игнор-лист Сообщения автора в теме
MasterZiv
Участник
Sev_Reo пишет:
> Есть непреодолимое желание делать запросы вида "/Найти все ноды с именем
> таким-то *И* со значениями некоторых атрибутов такими-то *И* чтоб у этих
> нодов в родителях были ноды с такими-то именами, атрибутами и пропертями
> *И* чтоб у этих родителей были еще родители уже с другими именами,
> атрибутами и пропертями."/

Хранить еще и результат транзитивного замыкания дерева в отдельной таблице.
Posted via ActualForum NNTP Server 1.4
...
Рейтинг: 0 / 0
16.07.2007, 15:12
| Ответить | Цитировать | Написать  
Быстрый сложный поиск по большому дереву
    #34661468
guest_20040621
Скрыть профиль Поместить в игнор-лист Сообщения автора в теме
guest_20040621
Гость
> Растроган. Плачу.

Обрыдайтесь, - мне никогда не было жаль буратин.
...
Рейтинг: 0 / 0
16.07.2007, 15:18
| Ответить | Цитировать | Написать  
Быстрый сложный поиск по большому дереву
    #34661509
Фотография LR
Скрыть профиль Поместить в игнор-лист Сообщения автора в теме
LR
Участник
Imho, при таких объемах, рано или поздно, так или иначе, задача сведется к построению/настройке "правильных" индексов. Могут ли индексы на xml-типе в mssql2005 быть "правильными" - х.з., для меня этот вопрос остается открытым...
...
Рейтинг: 0 / 0
16.07.2007, 15:25
| Ответить | Цитировать | Написать  
Быстрый сложный поиск по большому дереву
    #34662888
drev
Скрыть профиль Поместить в игнор-лист Сообщения автора в теме
drev
Участник
Sev_ReoTo guest_20040621 & Васильев Андрей :
Да с задачей все просто. Есть XML документы, которые надо хранить в базе и делать по ним различные поиски. This is it. Если вы желаете еще подробностей - спрашивайте.

To drev :
Спасибо за сцылку на хелп - обязательно вникну. Поддержка MSSQL2005 у нас случилась совсем недавно, так что XML data type не был еще достаточно изучен. Кстати, если Вам не составит труда, сориентируйте пожалуйста меня на оракловские аналоги - они тоже пригодятся, а опыта с ним (с ораклом) у меня тоже почти нет.
Специфика приложения такова, что оно должно поддерживать работу с MSSQL2005 и с Ораклом (молюсь, чтоб к этому не добавились всякие DB2, Информиксы и прочие монстры). Естественно, что, чем меньше различий будет в имплементации, тем лучше.
Что касается структуры данных. XML документы содержат ветки глубиной 3-7 уровней. Примерно такой структуры:
Код: plaintext
1.
2.
3.
4.
5.
6.
7.
A
+-B
  +-C
    +-D
      +-E
      +-E
      ...
      +-E
Проблема в том, что узлов Е в документе может быть от 1 до десятков/сотен тысяч. С определенной долей вероятности можно предсказать, что большинство узлов будет приходиться на документы, в которых большое количество листьев на одну ветку. Но количество документов с одним листом на одну ветку тоже может быть весьма значительным - тысячи/десятки тысяч (в день).
Насколько, по Вашему мнению, в этих условиях будет эффективно применение XML data type?


вроде, должно сработать... попробуйте

в случае Оракла - начните отсюда http://www.oracle.com/technology/tech/xml/index.html
...
Рейтинг: 0 / 0
17.07.2007, 09:05
| Ответить | Цитировать | Написать  
Быстрый сложный поиск по большому дереву
    #34663304
Bely
Скрыть профиль Поместить в игнор-лист Сообщения автора в теме
Bely
Участник
drevв случае Оракла - начните отсюда http://www.oracle.com/technology/tech/xml/index.htmlЭто очень далеко копать.
здесь ближе.
Searching XML Data Stored in CLOBs Using Oracle Text .
...
Рейтинг: 0 / 0
17.07.2007, 11:11
| Ответить | Цитировать | Написать  
Быстрый сложный поиск по большому дереву
    #34724948
Sev_Reo
Скрыть профиль Поместить в игнор-лист Сообщения автора в теме
Sev_Reo
Гость
Спасибо всем участникам за идеи.
Увы, native xml оказался слишком тяжелым в плане производительности и объема...
...
Рейтинг: 0 / 0
13.08.2007, 20:28
| Ответить | Цитировать | Написать  
Быстрый сложный поиск по большому дереву
    #34725027
belugin
Скрыть профиль Поместить в игнор-лист Сообщения автора в теме
belugin
Участник
Sev_ReoСпасибо всем участникам за идеи.
Увы, native xml оказался слишком тяжелым в плане производительности и объема...

Может то поможет
Akzhan's Developer Corner - Home (Russian)



статья
нам потребуется оптимизировать обработку иерархии счетов с помощью дополнительной функциональности. Воспользуемся шаблоном "Реализация древовидных структур данных" Анатолия Тенцера.

Нам потребуется в физической модели ввести новую таблицу "Наследование счёта", которая связана идентифицирующими отношениями с сущностями "Счёт" и "Счёт-папка". Для каждого счёта в этой таблице будет перечислены все его владельцы (прямой владелец счёта, владелец владельца и так далее). Немного подумав о получающихся запросах, мы можем придти к выводу, что помимо владельцев данного счёта, мы можем хранить в ней ещё и сам счёт. Тогда, правда, нам придётся несколько изменить определение таблицы, которая теперь будет дважды связана идентифицирующими отношениями с таблицей "Произвольный счёт" (не стоит забывать, что мы не установили ограничение на то, что конечный счёт всегда должен быть подсчётом).
...
Рейтинг: 0 / 0
13.08.2007, 21:47
| Ответить | Цитировать | Написать  
Быстрый сложный поиск по большому дереву
    #34726938
mdrg
Скрыть профиль Поместить в игнор-лист Сообщения автора в теме
mdrg
Гость
А если по мотивам Celco? т.е. добавить к каждому узлу 2 поля min,max так что все id наследников лежат между min и max. все равно записи только добавляются и все равно пакетами.
т.е. имеем лес деревьев, в который добавляем по 1 дереву.
и тогда проверки (забудем пока NodeProperty) будут выглядеть например след образом

Код: plaintext
1.
2.
3.
4.
5.
select
from Node parent
join Node Child1 (on Child1.id between parent.min and parent.max and child1< ПРОВЕРКИ>)
join Node Child2 (on Child2.id between Child1.min and Child1.max and child2< ПРОВЕРКИ>)
where Parent<Проверки>
...
Рейтинг: 0 / 0
14.08.2007, 15:22
| Ответить | Цитировать | Написать  
Быстрый сложный поиск по большому дереву
    #34760742
Фотография Alexandr Nikolaev
Скрыть профиль Поместить в игнор-лист Сообщения автора в теме
Alexandr Nikolaev
Участник
Иерархические структуры данных в реляционных БД
Иерархические справочники с линейным временем доступа
Навигация по иерархиям и сетям в реляционных базах данных
C уважением,
AlexandrN©
...
Рейтинг: 0 / 0
29.08.2007, 11:45
| Ответить | Цитировать | Написать  
14 сообщений из 39, страница 2 из 2
  2  все
Форумы / Проектирование БД [игнор отключен] [закрыт для гостей] / Быстрый сложный поиск по большому дереву
Найденые пользователи ...
Разблокировать пользователей ...
Читали тему (0):
Читали форум (0):
Пользователи онлайн (0):
Польз. соглашение   Полит. конфиден.  
NoSQL.ru       Кролег: Проекты, Новости, Чат       РЕД ФОРУМ       Фотоальбом: Участники, Встречи
Закрыть
start [/forum/topic.php?fid=32&msg=34661443&tid=1544331]:
 0ms
get settings:
 9ms
get forum list:
 24ms
check forum access:
 4ms
check topic access:
 4ms
track hit:
 167ms
get topic data:
 11ms
get forum data:
 3ms
get page messages:
 81ms
get tp. blocked users:
 2ms
others: 210ms
total:  515ms
созд. / загр.: 515ms
x
x
Закрыть


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