Идея метода
Множество вершин типа t изоморфно декартову произведению множеств объектов, которые могут быть её полями. Поясним это на примере. Пусть вершина типа t содержит:
- Список list детей типа p
- Ребёнка child типа s
- Необязательного ребёнка opt_child типа r
- Атрибут attr типа W
Пусть Ml - множество списков вершин типа p, Ms - множество вершин типа s, Mr - множество вершин типа r, Mw - множество объектов типа W. Тогда множество вершин типа t изоморфно декартову произведению множеств Ml, Ms, Mw, Mr U ε (здесь ε - символ отсутствия ребёнка). Действительно, любой кортеж из этого декартова произведения - набор возможных значений полей вершины типа t.
Это наблюдение обеспечивает общий метод генерации вершин типа t. Итак, для построения (конечного) множества вершин типа t необходимо построить конечные множества значений полей такой вершины и выбрать подмножество из декартова произведения этих множеств.
До сих пор мы говорили о ситуации, когда нет никаких связей между атрибутами, а также нет никаких ограничений на значения полей вершины. Если такие связи или ограничения есть, то множества значений полей зависят друг от друга. То есть для того, чтобы определить множество допустимых значений для одного поля, нужно знать значения каких-то других полей. Если в строящемся дереве два атрибута разных вершин зависят друг от друга, то эта зависимость может быть описана через зависимость полей некоторого узла (см. рис. 5).
Процесс генерации теперь будет выглядеть несколько по-другому. Сначала нужно определить зависимости между значениями полей. Граф зависимостей должен быть ациклическим, иначе будет невозможно установить порядок построения полей вершины. Когда порядок построения полей определен, строим множество значений для независимого поля, выбираем из него какое-то значение и устанавливаем его в качестве соответствующего поля вершины. Затем строим множества значений для полей, зависящих от уже установленного поля, выбираем из них значения, устанавливаем выбранные значения в качестве соответствующих полей вершины и т.д.
Таким образом, множества значений полей строятся в соответствии с уже построенным контекстом, поэтому результирующая вершина будет удовлетворять всем наложенным ограничениям. Для построения детей вершины можно использовать такой же метод генерации вершин соответствующего типа (см. рис 6; стрелками указано направление движения данных от одного генератора к другому).
- Первый источник - это семантические требования на данные, такие как требование существования определения используемой переменной в языках программирования или требование уникальности значений какого-то атрибута в XML-документе.
- Второй источник - это удовлетворение требований определённого критерия покрытия. В большинстве практических случаев множество всевозможных деревьев с вершинами определённых типов - это бесконечное множество, и мы, конечно же, не можем построить его целиком. Но это и не нужно, так как обычно такое множество можно разбить на конечное число классов таким образом, что в одном классе будут находиться элементы, "эквивалентные" с точки зрения целевой задачи. Такое разбиение называется критерием покрытия множества деревьев. Для одного и того же множества деревьев можно формулировать разные критерии покрытия; они будут зависеть от целевой задачи.
- Третий источник - это ограниченность ресурсов. Часто даже в пределах одной задачи сформулировать для неё точный критерий покрытия невозможно или же слишком трудоёмко. Поэтому приходится брать более сильный критерий покрытия, разбивающий множество деревьев на более мелкие классы. При этом число классов может весьма сильно возрасти. О том, как можно бороться с этой проблемой, будет сказано немного позже.
- Наконец, четвертый источник - это наличие рекурсии во множестве типов вершин T. Наличие рекурсии влечет необходимость её ограничения, то есть запрещения перебора деревьев с глубиной рекурсии, большей некоторого числа. При отсутствии ограничений на рекурсию множество допустимых деревьев бесконечно, а это значит, что генератор может войти в бесконечный цикл.
