Bely Sev_ReoЕсть непреодолимое желание делать запросы вида " Найти все ноды с именем таким-то И со значениями некоторых атрибутов такими-то И чтоб у этих нодов в родителях были ноды с такими-то именами, атрибутами и пропертями И чтоб у этих родителей были еще родители уже с другими именами, атрибутами и пропертями."
Можно предложить создать таблицу "Родители", в которой перечислить всех родителей этой ноды.
По ходу можно указать и уровень дальности родителя (-1, -2, -3 итп.).
Может понадобиться в условиях запросов, типра "среди всех родителей, которые не дальше 2-го поколения".

В таком случае ваши условия можно формулировать простым JOIN-ом
NODE - PARENTS - NODE.

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

Разумный подход для малых объёмов и/или для относительно плоских деревьев. В худшем случае требует N**2/2 записей в таблице пар предок-потомок, что приводит за месяц к 10**15 записей.

Кстати, Sev_Reo, может быть стоит использовать bigint вместо int? Иначе при указанных темпах через 8-16 месяцев у вас могут появится проблемы.

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

В случае динамических и/или глубоких запросов наверно предстоит генерировать нечто процедурное.

Если диалект позволяет построить индексы для XPATH запросов, следует исследовать производительность, IMHO.

Bely drevРазумный подход для малых объёмов и/или для относительно плоских деревьев. В худшем случае требует N**2/2 записей в таблице пар предок-потомок, что приводит за месяц к 10**15 записей.Если люди не боятся пополнения в млн. строк ежедневно , то бояться таблички в несколько млрд. строк, состоящей из двух чисел глупо .
Здесь надо смотреть на реальную глубину необходимого поиска.

drevВ случае динамических и/или глубоких запросов наверно предстоит генерировать нечто процедурное.процедурный поиск по нескольким млн. строк... и Вы полагаете это сможет работать за адекватное время? :)

1. Нет, не поиска, а дерева .

За год при достачной глубине дерева табличка легко уйдёт в терабайты.

Поэтому глупо не просчитывать это заранее.

2. Безусловнo. При достаточной глубине поиска один селект просто не справится. Поэтому придется организовывать их цепочку с помощью процедуры.

Bely drev1. Нет, не поиска, а дерева .
За год при достачной глубине дерева табличка легко уйдёт в терабайты.
Поэтому глупо не просчитывать это заранее.Считать надо, не спорю.
Но не теоретически, с учетом пролета всех комет, а исходя из реальных предположений о будующих данных.

drev Belyпроцедурный поиск по нескольким млн. строк... и Вы полагаете это сможет работать за адекватное время? :)2. Безусловнo. При достаточной глубине поиска один селект просто не справится. Поэтому придется организовывать их цепочку с помощью процедуры.Ну вот вам примерные исходные данные.
Глубина дерева - от 1 до 50, средняя глубина - 10.

Первое условие (на сам узел) - возвращает примерно 1 млн строк.
Второе условие (на родителя 1) - выдаст результат 10 тыс. строк
Третье условие (на родителя родителя) - выдаст в результате 1000 строк

Можете "коротенько" набросать алгоритм процедурки, которая будет быстрее селекта?

1. будующих - это красиво:)

2. Просчитать это может только спросивший. Данные у него. А Вы, с Вашими "несколькими миллиардами" ввели его в заблуждение.

3. Вы не умеете либо читать, либо считать.

Где Вы видите " При достаточной глубине поиска " ?

В Вашем достаточно безграмотно поставленном примере глубина поиска равна 2. От внука до деда. Глубина дерева абсолютно не релевантна в поставленной Вами задаче.

Bely drev2. Просчитать это может только спросивший. Данные у него. А Вы, с Вашими "несколькими миллиардами" ввели его в заблуждение.Телепатическая экспертная оценка.
Зато вы его со своими теоретическим экспонентным ростом ввели в страх.

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

drev3. Вы не умеете либо читать, либо считать.
Где Вы видите " При достаточной глубине поиска " ?
В Вашем достаточно безграмотно поставленном примере глубина поиска равна 2. От внука до деда. Глубина дерева абсолютно не релевантна в поставленной Вами задаче.Это вы недочитали. Вот изначальное условие от автора:
авторЗабыл добавить, что когда в запросе поминается родитель, то он не обязательно непосредственный.Так что родитель я трактовал в этом ключе.
Или для вас глубина поиска до 50 - невелика?

Ответа насчет алгоритма процедурки - я так и не дождался... а было бы интересно посмотреть.


1. " экспонентным " рассмешили:) У Вас N в квадрате - это экпонента?:) А не полином? :) Вас из какого класса средней школы выгнали?:)

2. Ок, объясняю для второгодников:) Судя по постановке задача очень похожа на сериализацию XML, где атрибуты есть наиболее часто встречающиеся из атрибутов элементов, а пропертиз - остальные. Соответственно, поиск, который он описывал выражается через xpath.

Слово "родитель" занято. Если вы меняете условие задачи (а условие, которое вы написали НЕ содержало никаких определений слова "родитель"), то следовало использовать слово "предок" (ancestor).

Если вы хотите поставить задачу нормально - опишите xpath (можно словами, если у вас получится) и приложите свой вариант селекта. А затем я напишу вам xpath посложнее и вы попробуете его выразить с помощью одного селекта, ок? После того, как у Вас не получится, я покажу, как это сделать с помощью процедуры.

Sev_ReoПроясню ситуацию по данным: если создавать таблицу родителей, то ее размер будет где-то в 3-5 раз больше таблицы нодов. Т.е. порядка 90M - 150M записей через месяц работы... Не самый аппетитный вариант.

BelyЕсли люди не боятся пополнения в млн. строк ежедневно...
Люди боятся, еще как боятся! Но выбирать особо не приходится...


drevКстати, Sev_Reo, может быть стоит использовать bigint вместо int? Иначе при указанных темпах через 8-16 месяцев у вас могут появится проблемы.

Да, именно bigint я и использую, но поскольку для примера это не важно, решил не париться с подробностями.

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

Увы, не являются

В случае динамических и/или глубоких запросов наверно предстоит генерировать нечто процедурное.

Например? Просто обозначьте направление, пожалуйста...

Если диалект позволяет построить индексы для XPATH запросов, следует исследовать производительность, IMHO.

А просветите, пожалуйста, какие диалекты такое позволяют?

............

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

В точку! Респект!

Слово "родитель" занято. Если вы меняете условие задачи (а условие, которое вы написали НЕ содержало никаких определений слова "родитель"), то следовало использовать слово "предок" (ancestor).

OK. Виноват, исправлюсь.



LRдо кучи:
не забыть исследовать возможности покрывающего кластерного индекса (с интенсивностью ~ 1M и 10M записей в день, шансы пережить месяц для такого исследования наверное есть :))

А можно здесь подробнее?


2b&2bСоветовал бы
1) посмотреть на этом форуме сообщения по структуре хранения деревьев (поскольку
только внесение одного допольнительного поля в эту структуру CountNodeChilds позволяет
существенно (в разы) сократить затраты на обработку дерева)
2) Качнуть в вашу структуру "мусора" в количестве не менее 1 000 000 записей и потренироваться

Исключительно полезные советы! Большое человеческое спасибо! До новых встреч!



Извините, что так долго не отвечал.

Отвечу в обратном порядке:

1. Судя по Вашим оценкам количества предком, рискну предположить, что у Вас сохраняются средних размеров XML документы, уровня 1000 элементов, более глубокие, чем широкие.

Я бы на вашем месте, если у Вас SQL Server 2005, попробовал бы сохранять документы целиком в поле XML type. Если я правильно оценил данные у вас останется одна таблица в 1000 строк в день.

Далее по полю XML type я бы попробовал создать от одного до нескольких индексов.

(посмотрите ms-help://MS.SQLCC.v9/MS.SQLSVR.v9.en/udb9/html/f5c9209d-b3f3-4543-b30b-01365a5e7333.htm)

и проверил бы производительность на как минимум месячном объёме данных.


В этой ситуации Вам не придётся имитировать xpath функциональность.

Аналогичные средства есть в Oracle.

2. Если у вас нет подобной функциональности или по каким-то причинам вам она не подходит, Вам придётся эмулировать xpath вручную.

Подъём по дереву придётся делать при помощи joins или CTE.

Для сложных xpath один селект может оказаться слишком сложным.

вам придётся, скорее всего, делать его по частям, скажем вычитывать во временную таблицу и делать join с селектом, имплементирующим следующую часть условий.

Если у Вас есть такая возможность и я правило понял задачу - первый путь лучше.

Sev_ReoTo guest_20040621 & Васильев Андрей :
Да с задачей все просто. Есть XML документы, которые надо хранить в базе и делать по ним различные поиски. This is it. Если вы желаете еще подробностей - спрашивайте.

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


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

в случае Оракла - начните отсюда http://www.oracle.com/technology/tech/xml/index.html