"Дуэли запрещены в субботу, воскресенье и остальные дни недели."

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

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

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

Факты..

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

Работа с такими таблицами фактов чаще всего сводится к различным выборкам из них. Выборка — это фильтрация данных таблицы (множества ее кортежей, записей) на основе значений входного вектора. Входной вектор обращения к таблице фактов может выглядеть примерно так: {Автор: "Иванов"}. Это означает, что нужно выбрать все книги автора Иванова.

Отсутствие какого-либо атрибута таблицы во входном векторе означает, что все значения данного атрибута допустимы в выборке. Так, например, вектор выборки всех книг Иванова можно написать и так: {Автор: "Иванов", Название: ?, ДатаВыпуска: ?, Жанр: ?} — результат выборки от этого не изменится. Здесь ? — обозначение универсума ("все значения"). Очевидно, что в такой записи входной вектор определяет некое множество значений.

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

… и правила

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

В качестве примера значений такой таблицы можно привести окончания слов. В такой таблице значение окончания 'а' — означает множество всех слов оканчивающихся на 'a'. Окончание 'ль' — множество всех слов, оканчивающихся на 'ль' и т.д.

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

Как правило входному вектору соответствует несколько записей (кортежей) таблицы. Назовем такие записи релевантными. Часто из всех релевантных кортежей надо выбрать один, — наиболее релевантный. Это означает, что необходимо уметь оценивать релевантность кортежей таблиц правил.

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

Определение регистра правил

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

• множество $$ называется областью определения функции;
• множество $$ называется областью значений функции;
• $$ — правило, по которому каждому элементу $$ сопоставляется некоторый элемент $$.
  

В отличие от таблиц регистр имеет структуру (а не просто набор) атрибутов. Область определения $$ — это детерминант регистра, область значений $$ — его корень. "Детерминант определяет корень" — это суть регистра. Атрибуты детерминанта называют также измерениями регистра, атрибуты корня — ресурсами.

Особенностью регистров правил является то, что область определения $$ может содержать значения-множества.

Приведем пример простейшего регистра правил. Допустим, необходимо связать дни недели с категорией — рабочий (Р) или выходной (В). Задано, что субботы и воскресенья являются выходными, а все остальные дни рабочими. Здесь областью определения $$ является множество дней недели, областью значений $$ — множество категорий дня. Необходимо построить $$.

Обычная табличная функция может выглядеть как набор пар, связывающих каждый день недели с определенной категорией: {(Пн, Р), (Вт, Р), (Ср, Р), (Чт, Р), (Пт, Р), (Сб, В), (Вс, В)}.
Это вполне себе возможный способ задания функции. По данному множеству пар можно получать категорию дня, если на входе задан день недели.

Но есть и минусы. Существенный недостаток — многословность (затратность). Естественным является желание повысить эффективность нашего описания, уменьшив множество пар. Более краткое выражение нашей функции может содержать всего две записи: {(?, Р), ((Сб, Вс), В)}. Или в виде таблицы:

Правила читаются так: "по умолчанию все дни недели являются рабочими, за исключением субботы и воскресенья, которые являются выходными".

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

В нашей таблице детерминантом является атрибут "День недели", а корнем — атрибут "Категория". Это простая структура. В сложных регистрах детерминант (и корень) могут состоять из нескольких атрибутов.

Извлечение корня

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

Обратимся к примеру выше. Допустим, на входе задан день недели "Вторник". Тогда все просто. Алгоритм извлечения выберет только одно подходящее правило — пару "Универсум — Рабочий", поскольку элемент "Вторник" принадлежит множеству "Универсум", но не принадлежит подмножеству (Сб, Вс). Оценивать релевантность одного правила нет смысла и алгоритм вернет значение соответствующей категории ("Рабочий").
Более сложная ситуация, если на входе задана суббота или воскресенье. В этом случае оба правила регистра являются релевантными. Необходимо сделать между ними выбор.

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

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

Перед тем, как перейти к оценке релевантности кортежей регистров правил, отметим их основные свойства.

Редукция

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

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

Полнота и коллизии

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

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

Расчет релевантности кортежей

Мультипликативная релевантность

Как указано выше,- релевантность правила обратно пропорциональна его абстрактности (общности). Обозначим через $$ мощность множества $$. Для дискретных множеств мощность равна количеству элементов множества. Мощность универсума множества и мощность множества — суть одно и то же. Мощность множества "Дни недели" равна 7, так как в неделе семь дней.

Соответственно мощность дискретных подмножеств $$ также определяется количеством элементов подмножества. Мощность подмножества (Сб, Вс) равна 2.

Относительная мощность подмножества определяется отношением его мощности к мощности его универсума:

Относительная мощность подмножества и есть его абстрактность (размер). При таком определении максимальная абстрактность равна 1. Абстрактность множества (Сб, Вс) = 2/7 = 0.286.

Определение абстрактности совпадает с определением вероятности событий. Чем больше вероятность попадания элемента в подмножество — тем выше абстрактность данного подмножества.

Релевантность — величина, обратная абстрактности. Релевантность — это конкретность, редкость. В соответствии с определением (1) получаем выражение для релевантности:

Подмножества с нулевой мощностью не поддаются оценке (нерелевантны). Другое следствие формулы (2) — релевантность не может быть нулевой для непустых множеств.

Наша таблица правил с заполненной релевантностью имеет вид:

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

Алгоритм извлечения правила из такой таблицы прост: 1) выбираем кортежи по условию принадлежности входного вектора подмножеству детерминанта кортежа, 2) сортируем по убыванию релевантности и 3) возвращаем первый кортеж.

Многомерный (составной) детерминант

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

Регистр правил после добавления атрибута детерминанта и нового правила принимает вид:

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

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

Множество "Пол" состоит из двух элементов — (мужской, женский). Соответственно, его мощность равна 2. Тогда мощность детерминанта нашего регистра (универсума детерминанта) будет равна:

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

где $$ — релевантность 1-го атрибута и т.д. Данная формула явно демонстрирует мультипликативность введенной релевантности.

Для кортежа (Пт, Ж) релевантность равна:

Регистр со значениями релевантностей:

Итоговая релевантность кортежа рассчитывается как произведение релевантностей его атрибутов.

Аддитивная релевантность

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

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

Итак, аддитивная (логарифмическая) релевантность определяется как

Подставляя (2) в (1), получим:

Для универсумов аддитивная релевантность всегда нулевая — это удобно. Важно также, что значение аддитивной релевантности для одного элемента дискретного множества равно энтропии множества.

Таблица правил нашего примера с аддитивной релевантностью:

День недели	Пол		Категория	L(День недели)	L(Пол)	L(Итого)
			Рабочий	0	0	0
(Сб, Вс)			Выходной	$$	0	$$
Пт	Ж		Выходной	$$	1	$$

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

День недели	Пол		Категория	L
			Рабочий	0
(Сб, Вс)			Выходной	$$
Пт	Ж		Выходной	$$

Связь релевантности и энтропии

Введенная нами аддитивная релевантность связана с информационной энтропией. Величина $$ является энтропией подмножества $$. Тогда аддитивная релевантность подмножества — это разность между энтропией всего универсума и данного подмножества. Отсюда ясно, что она всего больше или равна нулю.

Данное определение не зависит от мерности множества. Из формул (3) и (4) получаем развернутое выражение для логарифмической релевантности многомерных множеств:

Подставляем (5) в (3'):

Сгруппировав слагаемые, снова получаем исходное выражение релевантности:

Энтропия универсумов — одна и та же для всех кортежей. Поэтому для сортировки кортежей по релевантности достаточно знания только энтропии самого кортежа — для некоторых типов множеств это полезно.

Релевантность некоторых множеств

Вес (значимость) атрибутов

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

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

Правила читаются таким образом. В целом по организации принято торговать по прайсу А. Но в подразделении П1 торгуют по прайсу Б. В этом же подразделении для контрагента К1 предусмотрен специальный прайс В. А остальные подразделения организации с данным контрагентом работают по прайсу Г. Кроме того, в организации выделен контрагент К2, с которым также работают по прайсу Г.

Коллизия наступает, когда контрагент К2 обращается в подразделение П1. По какому прайсу надо с ним работать? Три правила релевантны — первое, второе и пятое. Для выбора прайса надо рассчитать релевантность всех правил (здесь и далее всегда используется аддитивная релевантность).

Значения атрибутов детерминанта здесь двух типов — универсумы и конкретные. Это наиболее распространенный случай. Как уже выяснили выше — релевантность универсумов всегда нулевая, а релевантность элемента равна энтропии его универсума.

Мощность множества контрагентов и множества подразделений не является фиксированной — их количество может меняться со временем. Для таких динамических множеств нельзя заранее рассчитать значения релевантности.

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

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

Примем, что вес измерения (энтропия) "Подразделение" равен 3, а вес измерения "Контрагент" равен 10 (цифры условны, но обычно контрагентов больше, чем подразделений). Рассчитаем релевантности кортежей таблицы прайсов:

Для входного вектора (К2, П1) релевантные кортежи будут такими:

Видим, что наибольшей релевантностью обладает прайс Г.

Релевантность упорядоченных множеств. Интервалы

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

В простейшем случае одномерного интервала его мощность определяется вычитанием значений границ (если к ним применима такая операция). Например, мощность числового интервала [3, 11[ равна 11-3=8. Используем нормальные границы [С, До[, при которых правая граница интервала не входит в множество (это позволяет складывать интервалы:
[3, 11[ + [11, 15[ = [3, 15[ ).

Мощность интервала дат зависит от типа единиц его измерения. Можно считать в сутках, часах, минутах, секундах и т. д. Например, мощность интервала [30.12.16, 02.01.17[ в сутках будет равна разности дат — 3.

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

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

Описывается так. Все подразделения организации торгуют всегда по прайсу А. Исключение — интервал с 3-го по 10-е. В этом случае используется прайс Б. И еще есть отдельное правило для подразделения П1. Оно работает по прайсу В.
Вопрос. По какому прайсу должно работать подразделение П1 5-го числа?

Для ответа на данный вопрос надо знать энтропию множества подразделений и энтропию множества чисел месяца. В месяце в среднем 30 дней, округлим до 32. Тогда энтропия месяца будет равна $$. Энтропия интервала [3, 11[ равна $$. Энтропию подразделений зададим такой же, как в предыдущем примере — 3. Это соответствует 8-ми подразделениям организации.

Теперь можно рассчитать релевантность значений детерминанта:

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

Открытые интервалы

Часто встречаются ситуации, в которых подмножества интервалов заданы только одной границей. Пусть, например, скидка на цену питания в санатории зависит от возраста гостя. До 4-х лет — 100%-я скидка, от 4-х до 16 лет — 50%-я, свыше 16 лет — скидки нет. Регистр правил будет выглядеть следующим образом:

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

С_возраста		% скидки	L
0		100	0
4		50	$$
16		0	$$

При выборке кортежей используем условие на возраст гостя: "Возраст >= Возраст_С" и возвращаем кортеж с наибольшей релевантностью. Для возраста 5 лет получим два релевантных кортежа, из которых выше релевантность кортежа с 50%-й скидкой.

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

Связанные множества. Слова и строки

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

Предположим, что слово состоит из $$ букв. Допустим, что всего в алфавите 32 буквы. Тогда общее количество всех возможных слов из $$ букв равно $$. Соответственно энтропия данного универсума будет равна $$.

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

Аналогично рассчитывается релевантность правил с двумя буквами:

И т. д. Общее выражение для релевантности правил из $$ букв:

Здесь $$ — энтропия алфавита букв. Интересно, что релевантность не зависит от размера слова и прямо пропорциональна длине подстроки. Данная формула позволяет оценивать релевантность детерминантов, содержащих связанные множества.

Иерархические множества

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

• 1
  
  • 1.1
  • 1.2
• 2
  
  • 2.1
  • 2.2

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

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

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

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

Можно раскрыть данную формулу дальше и выразить мощность элемента через мощности его внуков:

И т.д. Подставим соотношение (7) в формулу релевантности:

Если мощность иерархии достаточно велика, то $$ будет намного меньше кардинальности $$ и ей можно пренебречь. Тогда получаем простое выражение для релевантности элементов 1-го уровня иерархии:

Аналогично из (7') получаем упрощенное выражение для релевантности элементов 2-го уровня:

Ну и далее окончательное выражение релевантности для элементов $$-го уровня:

Здесь $$ — энтропия кардинальности иерархии. Сравнивая (6) и (10), видим, что выражения идентичны. То есть при данных допущениях релевантности элементов иерархии идентичны релевантности подстрок.

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

Конец 1-й части

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

Во 2-й части понятие релевантной выборки будет обобщено. Четкого разделения на таблицы фактов и правил на самом деле не существует. Но существует деление атрибутов отношений на конкретные и универсальные.

Продолжение...