Аналогично из атрибутов А, В, С и D можно сформировать шесть составных атрибутов:

(A,B,C,D), (B,C,D,A), (B,D,A,C), (C,A,D,B), (C,D,A,B), (D,A,B,C). (8)

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

(D,A,B,C), (D,B,C,A), (D,C,A,B), (9)

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

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

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

Будем определять базовый запрос к файлу бинарных атрибутов как запрос на все записи, в одних столбцах которых содержатся нули, в других - единицы и в остальных столбцах - произвольные величины. Используя символ "*" для обозначения любого значения, базовый запрос можно представить в виде последовательностей символов О, 1 и "*" Например, представим человека, который захотел печенья с кокосом и у которого аллергия на шоколад, который ненавидит анис и у которого дома закончился ванилин. Тогда его запрос может быть сформулирован так:

*0****0**1*******************0. (10)

Из табл. 1 становится понятно, что его желания совпадают с его возможностями в случае ароматных палочек с черносливом.

Таблица 1

ФАЙЛ С БИНАРНЫМИ АТРИБУТАМИ

Миндальные вафли с ромом Печенье с яблочным соусом Бананово-овсяное печенье Шоколадный хворост Миндальное печенье с кокосами Печенье со сливочным сыром Ароматные палочки с черносливом Драже в шоколаде Райские палочки Пирог с начинкой Финский какор

Глазированные имбирные пряники Печенье с орехами Драгоценное печенье Перепутаница Малайский крендель Медовые пряники Меренги

Моравское печенье со специями Овсяные палочки с финиками Старинное сахарное печенье Печенье с арахисовым маслом Юбочки

Печенье с перцем Шотландские овсяные коржики Песочные звездочки Анисовое печенье Воздушное печенье Шведский крендель Швейцарское рассыпчатое печенье Ириски

Ванильно-ореховое мороженое

я « се О.

g, S &

Пт С I

1« S

о. о

« я

§§igPNiiio

й « 3 а

° се

аЗпосвйяЙ

Яблочный соус Бананы

Сливочный сыр Апельсины, чернослив

Экстракт миндаля

Уксус

Абрикос

Смородиновое желе Растительное масло

Засахаренная вишня

Сметана

Арахисовое масло Цукаты, перец, мускат

McCalls Cook Book (New York: Random House, 1963), Chapter 9.

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

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

О о О О 0\yo5v/0 ООО 0\>V/\/0 о OV/O ООО о\у\у\Уо о о о о о о\

-,шшQ:<Q:5Ш2л[-ШIлшQ:Q:ш-Jvшc)л-Jл-trQ:Q:<-J -О!лшошо1-о!"эшош эшиш ]шш-<г1<<< ]<

Oz<og о"" шш со:

О I m

О <

О SWISS-CINNAMON CRISPS

ООООООООООООООООООООООООООООООООООООО

Рис. 46. Карта с перфорацией по краям.

Система, основанная на картах свойств, работает с инвертированным файлом аналогичным образом: имеется по одной карте для каждого атрибута и отверстия в карте пробиваются в позициях, которые соответствуют записям, содержащим этот атрибут. Таким образом, одна стандартная перфокарта шириной 80 позиций может использоваться для хранения информации о том, какие из 12 х 80 = 960 записей имеют данный атрибут. Для обработки включающего запроса отбираются карты свойств для определенных атрибутов и накладываются одна на другую. Луч света, проходя через позиции, в которых на всех картах имеются отверстия, покажет искомый результат. Это напоминает обработку логического запроса путем пересечения инвертированных битовых строк, как объяснялось выше.

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