Первым шагом на пути решения этой задачи является формулировка в терминах XSLT предложения "сгруппировать объекты по своим источникам". Источник каждого объекта определяется его атрибутом

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

Тогда для каждого элемента

в его группу войдут элементы, которые будут выбраны выражением

Попробуем использовать этот факт в следующем шаблоне:

Как и ожидалось, при применении этого правила к элементам

для каждого из них будет создана группа, принадлежащая тому же источнику, — уже хороший результат, но в условии требуется создать по группе не для каждого объекта, а для каждого источника. Чтобы достичь этого, можно создавать группу только для первого объекта, принадлежащего ей. Провести такую проверку опять же несложно: объект будет первым в группе тогда и только тогда, когда ему не предшествуют другие, элементы , принадлежащие тому же источнику. Иначе говоря, создаем группы только для тех элементов, для которых выражение

будет возвращать пустое множество.

С небольшими добавлениями искомое преобразование целиком будет иметь вид.

Бесспорно, решение было несложным, но довольно громоздким. Самым же узким местом в этом преобразовании является обращение к элементам

источника текущего элемента посредством сравнения атрибутов .

Проблема совершенно стандартна для многих преобразований: нужно выбирать узлы по определенным признакам, причем делать это нужно как можно более эффективно. Хорошо, что в нашем документе было всего восемь элементов

, но представьте себе ситуацию, когда элементов действительно много.

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

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

Однако какого именно типа условия мы чаще всего проверяем? Анализируя различные классы задач, можно придти к выводу, что в большинстве случаев предикаты являются равенствами — выражениями, которые обращаются в "истину" тогда и только тогда, когда некоторый параметр узла, не зависящий от текущего контекста, равен определенному значению. В нашем примере смысл предиката на самом деле состоит не в том, чтобы проверить на истинность выражение

, а в том, чтобы проверить на равенство и .

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

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