Программные продукты и системы

Основная идея группировки по соседям заключается в построении графа, обобщающего исходное XML-дерево. В литературе такой подход часто называется обобщением путей (path synopsis).

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

 1) имеют одинаковое имя;

 2) их родительские узлы относятся к одной группе;

 3) обладают одинаковым набором различных имен узлов-детей.

 Вершины родительских узлов соединены дугами с вершинами детей, а дуги получают вес, равный  количеству узлов в последних. Такие дуги соответствуют отношениям parent–child. При этом для отношений following–sibling и preceding–sib­ling добавляются дополнительные дуги. Вес этих дуг равен количеству узлов одной группы, находящихся в соответствующем отношении с узлами той группы, из которой эта дуга выходит.

 Обобщение строится путем обхода XML-иерархии сверху вниз, начиная с корневого узла.

 Подробное описание дается в статье «Оценка селективности XPath-запросов в XML-СУБД», автор Лукичёв М.С. (Санкт-Петербургский государственный университет).