Регистры правил. Развитие парадигмы

Материал из КинтВики
Версия от 09:09, 4 октября 2007; WikiSysop (обсуждение | вклад) (Новая: Категория:Регистры правил Категория:Базы данных <center>Дмитрий Малюгин, 2004</center> <center>ЗАО "Корпорати...)
(разн.) ← Предыдущая | Текущая версия (разн.) | Следующая → (разн.)
Перейти к: навигация, поиск


Дмитрий Малюгин, 2004
ЗАО "Корпоративные информационные технологии"

С позиций сегодняшнего дня (2007) данная статья имеет прежде всего исторический интерес (слегка отредактирована в части терминологии).

Введение

Регистры правил являются удобным инструментом для выборки непротиворечивой информации при сложных и/или разнообразных входных условиях. За время, прошедшее с момента выхода первой статьи о регистрах правил Регистры правил. Общие принципы, в которой изложены основы концепции, был накоплен некоторый опыт их практического использования. Данный опыт послужил основой для дальнейшего развития и уточнения основных положений концепции.

Корпоративные приложения чаще всего имеют дело с изощренными данными большого объема и бизнес-правилами, логика которых иногда просто противоречит здравому смыслу. Мартин Фаулер[2]

Одной из главных проблем корпоративных приложений (в первую очередь тиражных) является большое разнообразие входных ситуаций, явных и неявных условностей, ограничений, правил. Со всем этим разнообразием разработчикам необходимо как-то управляться. Усилия многих направлены на поиск методов, повышающих устойчивость и долговечность сложных информационных систем. Существует убеждение, что решение следует искать в применении объектно-ориентированных методов разработки. "Основное преимущество объектной парадигмы состоит в облегчении понимания запутанной логики" [2]. На наш взгляд, несмотря на безусловную практическую полезность объектной парадигмы, ее одной недостаточно для борьбы со сложностью систем. Нужен комплекс мер. Современные подходы к разработке - это использование декларативного подхода, введение семантических ограничений, пред- и постусловий прецедентов, наборов правил, инвариантов и пр. [3].

Одним из перспективных методов разработки является использование концепции Регистров правил (РП). В основе концепции - применение декларативного подхода к описанию продукционных правил типа "Если, То".

Общие положения

Кратко изложим основы концепции РП. Регистры правил представляют собой структуру для хранения и извлечения информации. Основу структуры РП составляют детерминант и корень регистра. Детерминант задает контекст поиска информации, т. е. корня. И детерминант, и корень также имеют структуру. Атрибутами детерминанта являются измерения, а атрибутами корня - ресурсы. Детерминант может быть ключевым (уникальным), в этом случае одному значению детерминанта соответствует одно значение корня. В общем случае детерминант может определять множество значений корня.

Не стоит путать регистры правил и наборы правил (rules set). Регистры правил - это таблицы, а наборы правил - это код [3]. Также регистры правил коренным образом отличаются от таблиц решений, как принципами организации, так и алгоритмом выборки информации.

Отличительной чертой регистра правил является использование квантора "Для любых" в значениях измерений детерминанта. Это позволяет вводить обобщающие правила, значения корня "по умолчанию". Другой ключевой особенностью РП является упорядоченность измерений детерминанта. Порядок измерений определяет приоритет выбора корня, - чем левее измерение, тем выше его значимость при прочих равных условиях. Выборка правила из регистра осуществляется на основании значений переменных входного контекста (вектора входного контекста).

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

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

  • противоречивые требования к функциональности со стороны пользователей;
  • управление расстановкой приоритетов;
  • интеллектуализация установки значений "по умолчанию";
  • "понимание" программой текущей ситуации;
  • большое количество операторов "Если, То" в одной процедуре.

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

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

Понятие степени и функции соответствия

Стремление увеличить сферу применимости использования РП (демонстрационные примеры представлены ниже) послужило причиной пересмотра (уточнения) алгоритма выборки правила (извлечения корня). Вместо того, чтобы фильтровать таблицу правил по значениям переменных входного контекста, необходимо "умножить" таблицу на вектор входного контекста (по аналогии с умножением матрицы на вектор). Результатом такого умножения будет новая таблица (таблица соответствий), в которой значения измерений детерминанта заменены числами. Эти числа отражают степень соответствия значения переменной входного контекста соответствующему значению измерения. Функция, сравнивающая значения измерений с переменной контекста и возвращающая результат такого сравнения, называется функцией соответствия (ФС). Для каждого типа измерений могут существовать свои функции соответствия. Независимо от вида функции принимается, что квантору "Для любых значений" всегда соответствует нулевая степень соответствия. При несовпадении элементов измерения и входного вектора контекста степень соответствия равна "-1". При точном совпадении - максимальное число, константа для заданного типа измерения (например, "1000"). В зависимости от типа измерения допускаются также промежуточные значения степеней соответствия (между нулем и максимальной степенью).

После заполнения таблицы соответствий она сортируется по убыванию значений измерений (степеней соответствия) по всем измерениям детерминанта в порядке от левых к правым. Верхняя строка полученной таблицы является правилом (корнем) с наивысшей степенью соответствия вектору входной ситуации.

Ниже приводятся примеры, в которых демонстрируется использование функций и степеней соответствия.

Строковые переменные. Окончания слов

В примере склонения фамилий [1] мы ввели два измерения для хранения окончаний слов - "Последняя буква" и "Две последних буквы". В общем же случае для задания правил склонения любых слов требуются окончания в три буквы, четыре и пять. Очевидно, было бы намного удобнее хранить все типы окончаний в одном измерении - "Окончание слова". Однако при этом возникают коллизии подмножеств окончаний, таких, например, как "я" и "ая", - если слово оканчивается на "я", то неясно, какое из двух значений измерений имеет больший приоритет.

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

Поясним сказанное примером. Пусть имеем измерение "Окончание слова" с перечнем окончаний от "ь" до "тель". Тогда при умножении этой таблицы на входной вектор (слово) "учитель" мы получим следующие степени соответствия:

Окончание Окончание
(степень соотв.)
тель 4
ель 3
ль 2
ь 1
  0


На языке платформы "1С: Предприятие" функция соответствия для окончаний строк может выглядеть следующим образом:

Степень соответствия = ?(Окончание = Прав(Слово, СтрДлина(Окончание)), СтрДлина(Окончание), -1);

Диапазоны значений. Типы "Пол" и "Потолок"

Вывод, который был сделан в [1] относительно невозможности поддержки диапазонов в явном виде, требует пересмотра. Напомним, что диапазоны могут задаваться переменными типа "Число", "Дата", а также любыми другими типами, поддерживающими операторы сравнения.

Любое из измерений регистра, имеющее один из названных выше типов, может быть определено как диапазон. При определении измерения как диапазона необходимо указать тип диапазона: пол или потолок [4]. Значения диапазона типа "Пол" определяют нижнюю границу для входных значений- "От". Значения диапазона типа "Потолок" определяют верхнюю границу - "До". Разницу между типами легко понять из примера. Пусть в измерении регистра правил заданы числовые значения диапазона {1000, 2000, 3000}. Если тип диапазона - "Пол", то при поступлении на вход числа 1500, условию фильтрации будет удовлетворять значение измерения 1000. Если тип диапазона - "Потолок", то ответом будет 2000.

С точки зрения рассматриваемой модели типы диапазонов различаются функциями соответствия. Например, для диапазона типа "Пол" функция соответствия может иметь следующий вид:

Степень соответствия = ?(Пол>Вход, -1, Пол-НижняяГраница+1);


Здесь

  • Пол - значение измерения РП "Пол";
  • Вход - число (дата), значение переменной вектора входного контекста;
  • НижняяГраница - наименьшее число диапазона.

Пример определения степени соответствия диапазона "Пол" входному значению 300:

Пол Пол
(степень соотв.)
0 1
200 201
400 -1
600 -1
  0


Для диапазона "Потолок" функция соответствия симметрична ФС "Пол":

Степень соответствия = ?(Вход>Потолок, -1, ВерхняяГраница-Потолок+1);


Потолок Потолок
(степень соотв.)
0 -1
200 -1
400 201
600 1
  0


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

С учетом вышесказанного пример из работы [1] на склонение фамилии нуждается в корректировке. Тип измерения детерминанта "Длина фамилии" следует преобразовать в диапазон. Замена булева типа (> 3) на диапазон позволит при уточнении правил для данного регистра легко расщеплять диапазон (добавлять строки/правила) без необходимости вводить новые измерения.

Отметим также, что диапазон типа "Пол" по функциональности полностью совпадает с датой исторического регистра, а также объекта "регистр сведений" платформы "1С: Предприятие 8.0". Таким образом, измерение "Дата", поддерживающее историю данных регистра, является частным случаем диапазона типа "Пол".

Иерархия элементов, группы элементов

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

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

Для решения проблемы уникальности правил мы можем на уровне исполнения разворачивать группы по правилам декартова произведения. Однако это вряд ли оправдано при наличии групп в разных измерениях детерминанта одного правила. Например, если некое правило определено для группы товаров, содержащей порядка 1000 наименований и группы контрагентов такой же численности (мощности), то при развороте групп в регистр правил надо будет добавить порядка миллиона записей.

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

Степень соответствия = ?(Вход.ПринадлежитГруппе(ЗначениеИзмерения), ЗначениеИзмерения.Уровень(), -1);


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

Структура регистра правил

Итак, наиболее гибким способом выборки правил является использование функций и степеней соответствия. Очевидно, что способ выборки правил определяет структуру регистра и его интерфейс. Реализация принципов организации структуры и интерфейсов регистра правил может быть различной в зависимости от уровня гибкости регистра, его предопределенности. Можно выделить три уровня "жесткости" (или наоборот, гибкости) регистра.

На нижнем уровне находятся системные регистры правил. Для таких регистров разработчиками определяются как структура регистра, так и его значения. Такие регистры чаще всего соответствуют жестким правилам, менять которые пользователям нет необходимости. Примером такого регистра может служить РП склонения слов. Предполагается, что у пользователей не должно возникать необходимости настраивать системные РП под собственные нужды. Тем не менее, системные РП могут допускать механизмы доопределения или переопределения их значений.

На промежуточном уровне жесткости находятся служебные регистры правил. К данному типу мы относим правила, структура которых определяется разработчиком, однако значения вводятся и редактируются пользователем. Кроме того, пользователь может переопределить приоритеты измерений, а также отключить неиспользуемые. Предопределенность служебных регистров позволяет разработчикам "привязывать" вызов их правил к неким системным событиям с последующим соответствующим использованием возвращаемых значений корня. В качестве примера служебного регистра можно привести РП "Управление скидками для клиентов". Корнем является процент скидки, а одним из предопределенных измерений - "Клиент". При изменении клиента в диалоговой форме документа принудительно вызывается РП и, в зависимости от значения контекста, устанавливается соответствующая скидка.

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

Для любого типа РП существуют следующие уровни операций:
  • определение основной структуры регистра (структурный уровень);
  • ввод, задание правил (уровень определения);
  • выборка правил (уровень исполнения).

Структурный уровень

С точки зрения ООП парадигмы РП является абстрактным классом с неким набором методов и свойств. Конкретная структура детерминанта и корня регистра задается наследниками данного класса. Такое определение структуры регистра мы относим к структурному уровню.

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

В общем случае выборка правила из регистра осуществляется в три этапа:

  1. Предварительная обработка входного контекста для вычисления дополнительных значений переменных и, в конечном счете, значения вектора входного контекста (предобработка).
  2. Выполнение запроса к регистру и получение значения(й) ресурсов корня.
  3. Преобразование значений ресурсов в выходное значение корня регистра (постобработка).


Интерфейс ввода-вывода проще всего организовать в виде блока переменных регистра. Для каждой переменной регистра задается ее идентификатор и способ получения значения. Способ получения значения заключается в выполнении каких-либо действий над переменными входного контекста, либо над другими переменными регистра. Вычисленные переменные дополняют переменные входного контекста. Часть переменных образует входной вектор запроса. Измерения (координаты) входного вектора и измерения детерминанта РП совпадают по идентификатору и типу. Функции соответствия также должны задаваться (если это необходимо) на структурном уровне (в принципе, можно переопределять функции соответствия на этапе выполнения запроса к регистру, но примеры, в которых необходимо такое переопределение, нам неизвестны).

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

Небольшой пример, поясняющий вышесказанное (склонение слова).

Входной контекст: {Слово; Род}.

Итак, на входе имеем слово в именительном падеже какого-то рода. В принципе, род тоже поддается определению на основании слова (другой регистра правил), но здесь считаем, что он уже определен.

Структура детерминанта основного регистра: {ПоследняяБуква; ТипПоследнейБуквы; Род}

Мы назвали регистр основным, чтобы подчеркнуть его отличие от подчиненных регистров (которые могут подключаться на этапе выборки правила [1]). Видно, что для определения значения входного вектора переменных входного контекста недостаточно. Необходимо задать переменные регистра (используется язык платформы "1С:Предприятие"):

Предобработка (инициализация переменных регистра):

{ПоследняяБуква=Прав(Слово, 1);

ТипПоследнейБуквы=ТипБуквы(ПоследняяБуква);

СловоБезПоследнейБуквы=Лев(Слово, СтрДлина(Слово)-1);

СловоБезДвухПоследнихБукв=Лев(Слово, СтрДлина(Слово)-2);

…}

Здесь также заданы переменные (СловоБезПоследнейБуквы, СловоБезДвухПоследнихБукв), которые для определения входного вектора не требуются, но используются при формировании результата регистра правил.

Ресурсы РП могут хранить непосредственное значение, а могут и выражаться через ссылку на переменную контекста выполнения запроса. В последнем случае при определении такого ресурса мы должны указать, что его типом является переменная контекста.

Структура корня регистра:

{НачалоСлова: ПеременнаяКонтекста;

ОкончаниеСлова: Строка}

Таким образом, ресурс "НачалоСлова" может принимать значения переменных контекста выполнения запроса. (На самом деле только три значения имеют смысл: "Слово", "СловоБезПоследнейБуквы", "СловоБезДвухПоследнихБукв"). Типом ресурса может быть также набор программных строк (выполняемых после получения правила), ссылка на функцию/процедуру, ссылка на другой регистр правил.

Наконец, предопределенная функция корня просто конкатенирует два ресурса:

Постобработка: Корень=НачалоСлова+ОкончаниеСлова.

Уровень определения

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

Поясним сказанное примером. Пусть мы имеем следующие значения детерминанта для одного и того же значения корня:

Уровень исполнения
Изм. 1 Изм. 2
A
A 2
A 3
B 1
B  2
B  3


Тогда мы можем определить данное множество значений через следующую свертку:

Уровень определения
Изм. 1 Изм. 2
{A, B} {1, 2, 3}


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

Алгоритм свертки измерений в множества

Наряду с алгоритмом разворота множества значений измерений в нормализованный вид (атомарные значения измерений) существует и обратный алгоритм свертки значений измерений в произведение множеств. Такой алгоритм представляется полезным при построении регистра правил на основе фактов. Регистр фактов (сведений) может содержать большое количество неструктурированной информации. Преобразование таких фактов в произведение множеств позволяет выделить основные закономерности и упорядочить информацию.

Для описания алгоритма введем операцию объединения нескольких элементов в множество - U(a, b, c) = {a, b, c}. Данная операция может быть применена к колонкам таблицы при ее свертке. Пример такой свертки приведен ниже, исходная таблица (слева) сворачивается по измерению 1 с одновременным объединением элементов измерения 2 в множества:

Изм. 1 Изм. 2
A
A 2
A 3
B 1
B  2


Изм. 1 Изм. 2
A {1, 2, 3}
B {1, 2}


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

Приведем пример этапов такой свертки для таблицы, состоящей из трех измерений типа булево (0, 1). Для упрощения значения корня принимаем одним и тем же для всех значений детерминанта. Ниже приведены три (по количеству измерений) последовательных этапа свертки детерминанта (слева направо):


A B C Сворачиваем по колонкам B, C, объединяя A
A B C Сворачиваем по колонкам A, C, объединяя B
A B C Сворачиваем по колонкам A, B, объединяя C
A B C
0 0 0 {0,1} 0 0 {0,1} {0,1} 0 {0,1} {0,1} {0,1}
0 0 1 {0,1} 0 1 {0,1} {0,1} 1      
0 1 0 {0, 1} 1 0            
0 1 1 {0,1} 1 1            
1 0 0                  
1 0 1                  
1 1 0                  
1 1 1                  


Полученная итоговая таблица намного компактнее исходной.

Уровень исполнения

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

Для получения правила (значения корня РП) пользователь задает требуемые значения переменных входного контекста (только внешние переменные!) и выполняет запрос к регистру. В работе [1] подразумевалось, что структура запроса к регистру совпадает со структурой самого регистра. На данный момент мы считаем, что необходимости в накладывании такого ограничения нет. Структура РП прежде всего определяет структуру хранения правил, поддержку непротиворечивости. Однако на этапе выборки правила мы можем переопределить структуру правил. То есть переопределить состав измерений детерминанта и ресурсов корня регистра на период запроса. Независимость структуры хранения от структуры выборки РП значительно расширяет его возможности.

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


Заключение

Регистры правил позволяют минимизировать код, повысить прозрачность логики информационных систем, реализовывать сложные задачи красиво и элегантно. Концепция регистров правил не привязана к конкретной платформе или технологии, - она является универсальной. Регистры правил и лежащий в их основе табличный стиль программирования побуждают к пересмотру привычных приемов и методов программирования. Много интересных применений концепции, ее уточнений, обобщений и прочее осталось за рамками данной статьи, но автор надеется возвращаться к теме регистров правил и в дальнейшем.

Литература

  1. "Регистры правил", Д. Малюгин, 2003, http://itland.ru/lib/index.php?id=48.
  2. "Архитектура корпоративных программных приложений", М. Фаулер и др., 2004.
  3. "Объектно-ориентированные методы. Принципы и практика. 3-е издание", И. Грэхем, 2004.
  4. "Конкретная математика (основание информатики)", Р.Грэхем, Д.Кнут, О.Паташник, 1998.