Д. Кнут - Искусство программирования том 3 (2-е издание) - 2001 (Часть 2) (1119371), страница 51
Текст из файла (страница 51)
с) Логический запрос, состоящий из зап(юсов предыдущих типов, скомбинированных при помощи логических операций АИО, ОЯ, ИОТ, например "(КУРС = ВТОРОКУРСНИК) АИО (ИЕСТОЖИТЕЯЬСТВО.ШТАТ = ОГАЙО) АИО ИОТ ((СПЕЦИАЛИЗАЦИЯ ИАТЕМАТИКА) Ой (СПЕЦИАЛИЗАЦИЯ СТАТИСТИКА))': Проблема разработки эффективных технологий поиска достаточно сложна уже для этих трех простых типов запросов, а потому более сложныг типы запросов обычно не рассматриваются. Например, железнодорожная компания может иметь файл с информацией о текущем состоянии всех товарных вагонов.
Запрос наподобие 'Найти все пустые вагоны-рефрижераторы в радиусе 500 миль от Сиэтла" при этом в явном виде невозможен, за, исключением случая, когда "расстояние от Сиэтла" является атрибутом, хранящимся в каждой записи, а не сложной функцией вычисления этой величины по значениям других атрибутов. Использование же логических кванторов в дополнение к АИО, Ой, ИОТ приведет к дальнейшему усложнению запросов, ограниченных исключительно воображением запрашивающего. Имея файл со статистикой по бейсболу, например, можно запросить информацию о самой длинной серии удачных ударов в ночных играх.
Такие запросы несмотря на их сложность могут выполняться в течение одного прохода по соответствуюьчим образом упорядоченному файлу. Однако могут быть и существенно более сложные запросы, например "Найти вге пары записей, имеющие одинаковые 'значения в пяти и более атрибутах (без указания атрибутов, которые должны совпадать)': Такие запросы могут рассматриваться как общие задачи программирования, выходящие за рамки нашего обсуждения. хотя зачастую они могут быть разбиты на подзадачи, подобные рассматриваемым здесь.
Прежде чем приступить к изучению различных технологий получения информации по вторичным ключам, стоит рассмотреть экономический аспект вопроса. Хотя огромное количество приложений помещается в жесткие рамки трех типов запросов, описанных выше, далеко не для всех нз них подходят технологии, которые мы будем изучать; в некоторых из них лучше было бы использовать ручную, а не машинную рабюту! Люди взобрались на Эверест просто потому, что он существует.
И многое альпинистское снаряжение было разработано именно по этой причине. Так и в информационных технологиях: увидев перед собой Эверест данных, люди тут же начинают разрабатывать снаряжение для его покорения, позволяющее в оперативном режиме ответить на все вопросы, которые только могут присниться в кошмарном сне. Зачастую они просто не задумываются о вопросах стоимости. Такие вычисления возможны, но они не подходят для любого приложения.
Например, рассмотрим следующий простой подход к выборке по вторичным ключам: после сбора пакегла из нескольких запросов (ба8сЬзпу) выполним последовательный поиск по всеьгу файлу, получая все нужные записи. (Сбор пакета означает, что мы накапливаем некоторое количество запросов перед их выполнением.) Такой метод вполне удовлетворителен при не слишком болыпих файлах и отсутствии требования немедленно обработать поступающие запросы.
Этот подход может использоваться с файлами на лентах и требует работы компьютера над запросом через некоторые интервалы времени, что делает его вполне экономичным в плане стоимости оборудования. Волее того, он способен обрабатывать вычислительные запросы наподобие рассмотренного нами ранее (с использованием понятия "расстояние от Сиэтла" ). Другой простой путь облегчить получение информации по вторичному ключу состоит в делегировании части работы человеку, который снабжен подходящими печатными указателями.
Этот метод зачастую является наиболее разумным и экоиоми гным способом работы (ег и, конечно„старая бумага перерабатывается при издании нового указателя), в особенности потому, что люди обычно отмечают интересные запросы при обеспечении удобного доступа к данным большого объема*. Приложения, для которых не подходят приведеннтне простые схемы, включают в себя очень большие файлы, критичные ко времени ответа иа запрос. Такал ситуация, например, возникает при одновременной выдаче запросов от множества пользователей нли при машинной генерации запросов.
Назначение данного раздела — рассмотреть способы обеспечения выборки информации при различных предположениях о структуре файла. К счастью, методы, которые будут обсуждаться, становятся все более и более пригодными для практического применения, а цена вычислений продолжает резко снижаться. Существует немало хороших способов решения поставленных задач, однако (как читатель должен был понять из всех предварительных примечаний) все эти алгоритмы не так хороши, как алгоритм поиска информации по первичному ключу.
Изза огромного разнообразия файлов н приложений мы не в состоянии сколь-нибудь пблно обсудить все возможности илн проанализировать поведение каждого алгоритма в типичных условиях. В оставшейся части этого раздела представлены основные предлагаемые подходы, н дело читателя — решать, какая комбинация описанных технологий лучше всего подходит для решения той или иной конкретной задачи.
ч Поиылуй, автор несколько недооценивает тенденции развития вычислительной техники и технологий баз данных. Так, например, оператор службы "09", конечно же, держит в гтжове сотни телефонов и на самые часто залаваемые вопросы способен ответить мгновенно. Но кто мешает иснользоватгь например, кзшнрование запросов, которое ие подвержено той же усталости к концу смены? Вычислительная техника и информационные технологии — очень быстро развивающаяся область, и зхь чтп еще вчера казалось недостижимым, сегодня становится обыденным. Общая тенденция такова, что думать и принимать решения — зто работа человека, а ыеханическн искать информацию — удел компъютера. — Приап иерее.
Инвертированные файлы. Первый важный класс технологий поиска по вторичному ключу основан на идее инвергпированнмх файлов. Данный термин не означает, что файл перевернут вверх ногами; это означает изменение ролей атрибутов записей (вместо списка атрибутов записи приводится список записей с данным атрибутом). Ыы часто сталкиваемся с инвертированными файлами (пусть н под другнмн названиями) в нашей повседневной жизни. Например, инверсией англо-русского словаря будет словарь русско-английский; инвертированным файлом, соответствующем какой-нибудь книге, является ее предметный нли авторский указатель. Бухгалтеры традиционно используют в работе "двойную бухгалтерию" (бопЫе-еп1гу ЬооЫсеер1пй), в которой все сделки фиксируются как в кассовых книгах, так и в счетах клиентов, чтобы иметь возможность быстро получить информацию как по кассе, так и по клиентам.
В общем случае инвертированный файл не самодостаточен и должен использоваться совместно с "прямым", неинвертированным файлом. ° В инвертированном файле содержится избыточная информация — цена, которую приходится платить за ускорение поиска по вторичному ключу. Компоненты инвертированного файла называются иивершированиььми списками, т. е. списками всех записей с данным значением некоторого атрибута. Подобно прочим спискам, инвертированные списки могут быть представлены в компьютере самыми разными способами, причем для каждого приложения и данных может быть выбран свой, наиболее подходящий способ представления.
Одни вторичные ключи могут иметь только два значения (например, графа анкеты ПОЛ (хотя, как говорят, находятся уникумы, пишущие в этой графе что-то вроде 'паркетный", а в англоязычной анкете на вопрос БЕЛ отвечающие "тейп)вг"; впрочем, этн замечания больше относятгл к вопросу о проверке корректности вводимых данных. -— Прим, перев.)), и соответствующие списки могут оказаться весьма длинными: другие же, наподобие НОМЕР ТЕЛЕФОНА, как правило, коротки н с малым количеством дубликатов.
Представим, что хранить информацию в телефонной книге нужно так. чтобы все записи хюгли быть получены на основе имени, телефонного номера илн адреса абонента. Одно нз решений — создать три различных файла, ориентированных на поиск по своему типу ключа.
Вторая идея состоит в комбинировании всех трех файлов, например, в три хеш-таблицы, служащие в качестве заголовков списков для метода цепочек. В последней схеме каждая запись файла должна быть элементом трех списков н, таким образом, должна иметь трн поля ссылок. Этот так называемый миогвсписочнмй (гпи1МЫ) метод проиллюстрирован на рис.
13 раздела 2.2.6 и обсуждается ниже. Третья возможность состоит в комбинировании трех файлов в один суперфайл по аналогии с каталогом библиотеки, в котором карточки авторов, названий книг и нх тем располагаются вместе в алфавитном порядке. После рассмотрения формата, использованного в предметном указателе этой книги, возникают новые идеи по представлению инвертированных списков. Для полей вторичного ключа, когда имеется около пяти элементов на одно значение атрибута, можно просто создать короткий последовательный список позиций записей (по аналогии с номерами страниц в указателе книги), гзедующнх за значением ключа. В случае кластеризации записей может оказаться удобным указание диапазонов позиций ~как, например, указание диапазона страниц 559-582).
Если записи в файле часто перемещаются, то лучше вместо позиций записей использовать первичные ключи — прн этом ие требуется обновление при перемещении записей. Например, ссылки в Библии всегда даются на главу и стих; во многих книгах ссылки основываются на номерах параграфов, а не страниц. Ни одна из рассмотренных идей не подходит для атрибута с двумя значениями, например ПОЛ, В таком случае, конечно, достаточно только одного инвертированного списка, так как все не мужчины являются женщинами и наоборот. Если каждое значение соответствует примерно половине элементов файла, инвертированный список может быть ужасно длинным, но существует возможность получить очень изящное решение на бинарном компьютере с помощью представления в виде битовой строки, в которой каждый бит определяет значение конкретной записи.
Так, битовая строка 01001011101... может означать, что первая запись в файле относится к мужчине. вторая — к женщине, следующие две — к мужчинам и т. д. Таких методов достаточно для обработки простых запросов по определенным значениям атрибутов. Немного расширив эти методы, можно работать с запросами диапазонов, но вместо хеширования следует использовать схемы поиска, основанные на сравнениях (см.
раздел 6.2). Для логических запросов наподобие "(СПЕЦИАЛИЗАЦИЯ = ИАТЕИАТИКА) АМО (ИЕСТОЖИТЕЛЪСТЗО.ШТАТ = ОГАЙО)*' необходимо найти пересечение двух инвертированных списков. Это можно сделать несколькими путями; например, если оба списка упорядочены, два прохода 1по каждому из них) дадут все общие элементы.
![](https://s.studizba.com/z.php?f=/templates/si/i/noavatar.png&w=100&h=100&t=1"){kind=avatar}
