МОДЕЛЬ ИНВЕРТИРОВАННЫХ ФАЙЛОВ И ИНФОРМАЦИОННО-ПОИСКОВЫЕ СИСТЕМЫ

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

Множество основных файлов базы данных обозначим через {Fl,F2,...,Fn}.

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

Естественно, что выделенный атрибут (обозначим его А) может принимать в Fi несколько различных значений {а( 1),а(2),.,.,а(к)}.

Поставим в соответствие каждому значению a(j) множество номеров записей файла Fi, в которых это значение связано с именем атрибута А.

ja(l),njt),n(P),...i ja(2),n(g),n(h),...)

jaO),n(x),n(y),...i

Через п с соответствующим индексом обозначены номера записей из Fi.

Определенная таким образом последовательность значений атрибута А и номеров записей основного файла Fi является инвертированным файлом, который далее будем обозначать через A(Fi).

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

Рассмотрим два файла Fi и Fm, в структуре которых имеется общий атрибут А.

Пример

База данных содержит основные файлы Сотрудники и Зарплата, показанные на рис. 2.7. Естественно, что списки связи установлены по атрибуту Фамилия, а инвертированных списков в нашем примере максимально может быть пять (по числу атрибутов в основных файлах).

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

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

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

Ключевые слова А, В, С. D, Е

А

140 220

С 140 240

Основной файл

D 22 0

100 140 240

И н вертированный Рис. 2Я. Связь основного и инвертированного файла

В 100 220

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

Так, при обработке запроса - найти все записи, содержащие ключи В или С, кроме А, которому в терминах теории множеств соответствует запись (В UC)\ А, производится последовательное вычисление

( { 100, 140, 240} и ( 140, 240} ) \ { 140, 220} = { 100, 240}.

Результат означает, что запросу удовлетворяют записи с номерами 100 и 240.

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

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

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

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

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

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

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

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

В каждой информационно-поисковой системе должна присутствовать административная подсистема и поисковая подсистема.

9*

131

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

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

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

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

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

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

Рассмотрим основные возможности реализации поиска, характерные для большинства информационно-поисковых систем, иа простых примерах.

Пример 1

Поиск записей, содержащих слово подшипник.

Текст команды и ответ информационно-поисковой системы приводятся ниже.

>Найти подшипник

1 27 Найти подшипник, где 1 - порядковый номер запроса,

27 - количество найденных записей.

Найти подшипник - текст команды запроса, который система воспроизводит заново после о кончай ия поиска.

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

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

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

Пример 2

Поиск записей, содержащих в атрибуте Название экспоната слово подшипник.

>Найти подшипник/Название 2

19 Найтн подшипник/Название

Для просмотра предоставляются 19 записей, в которых слово подшипник встречается в значениях атрибута Название экспоната.

В большинстве поисковых систем реализованы три логические операции: И (конъюнкция), ИЛИ (дизъюнкция), НЕ (конъюнкция плюс отрицание).

Пример 3

> Найти подшипник НЕ роликовый 3

10 Найти подшипник НЕ роликовый

Каждая из 10 записей, выбранных по этому запросу, содержит термин подшипник, но не содержит термин роликовый.

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

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

Пример 4

Использование скобок. Команда

>НаЙти подшипник ИЛИ ротор И электродвигатель

аналогична команде

>Найти (подшипник ИЛИ ротор) И электродвигателе Измененный порядок скобок приведет к другой команде поиска с другим результатом.

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

Для указания произвольного символа в поисковом термине используется восклицательный знак "!". Этот знак ие может замешать первый символ термина.

>Найти т!л

проводится поиск терминов типа тол, тыл и так далее.

> Найти маши?

проводится поиск терминов типа машина, машинный, машиностроение и так далее.

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

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

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

Пример

Рассмотрим структуру ВУЗа. Из всех видов деятельности ВУЗа рассматривается только научно-исследовательская работа (рис. 2.9).

На первом уровне иерархической структуры должны располагаться: •

главная запись (сведения о руководстве ВУЗа);

« отношение Person с данными о преподавателях. Сведения о преподавателях нумеруются - Person(l), Person(2), Person(3) и т. д. Сведения о факультетах являются самостоятельными иерархическими базами данных. Их количество равно числу факультетов.

На первом уровне базы данных о факультете располагаются две главные записи: •

сведения о руководстве факультета; •

список преподавателей факультета.

Затем представлены иерархические базы данных о каждой кафедре факультета.

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

Ссылки на другие разделы базы данных реализуются через номера строк в отношении Person.

Например, содержимое главной записи о ВУЗе:

<Н2>Руководство

< DT>< В>Ректор

Person( 1)

<ОТ><В>Проректор по учебной pa6oTe

Person(2)

Проректор по научной pa6oTe

Person(3) <ОТ><В>Проректор по социально-экономическим вопросам < DD>Person(4)

<ОТ><В>Проректор по административно-хозяйственной ра- 6oTe

Person(5)

<ОТ><В>Ученый секретарь CoBera

Person(6)

Список преподавателей факультета 01.

Person(l)

Person(4)

Person(20l 1)

Person(lOOl)

Person(1002)

Person(1043) Запись Research(3):

Ыагае(Региональные проблемы рыночной экономики)

Chief(1001)

BEGIN

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

Ссылка Chief( 1001) означает, что научным руководителем темы является преподаватель, информация о котором хранится как Person(lOOl). Этот преподаватель работает на факультете 01.

Структура базы данных разрешает фиксировать сведения о преподавателях, не работающих ни иа одном факультете или работающих иа нескольких факультетах.

ВОПРОСЫ И ЗАДАНИЯ

1. Сведения об учебном процессе зафиксированы в четырех отношениях:

Студ(Гр.Зач.ФИО) Оценка(Гр,Зач,ДисЦнДата,Пр,Оц) Расп(Дата, ГрДисц, Пр) Преп(Дисц,Пр,Каф)

В задании используются следующие обозначения:

Студ - студент

Гр - номер группы

Зач - номер зачетной книжки

ФИО - фамилия студента

Дисц - дисциплина

Пр - фамилия преподавателя

Оц - оценка

Расп - расписание

Л реп - преподаватель

Каф - название кафедры

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

Найдите фамилии преподавателей, ведущих занятия в группах 305 и 307 одновременно. 2)

Какие оценки получил студент Федоров? 3)

У каких студентов преподает Иванов? 4)

Какие студенты сдали те же экзамены, что и Федоров? 5)

Какие преподаватели работают 10.10.98? 6)

Какие преподаватели ведут занятия в тех же группах, что и Иванов? 7)

По каким предметам сдается зачет, а не экзамен? 8)

Какие студенты изучают дисциплину ВМ 10.10.98? 9)

Какие дисциплины преподаются на кафедре ВМ? 10)

Какие преподаватели преподают дисциплину ВМ? 11)

Какие преподаватели поставили удовлетворительные оценки в группе 305? 12)

Какие экзамены сданы у всех студентов группы 30S? 13)

Какие кафедры ведут занятия в группе 305? 14)

Какие преподаватели работают в те же дни, что и Иванов? 15)

Какие преподаватели поставили отличные оценки студенту Федорову? 16)

По каким дисциплинам студент Федоров получил отличные оценки? 17)

Какие студенты учатся в той же группе, что и Федоров? 2.

Разработайте программы реализации операций вычитания и деления отношений для СУБД семейства dBASE. Требуемые имена файлов и атрибутов передавайте как параметры. 3.

В п. 2.2.1 приведен метод поиска вероятного ключа отношения (если он единственный). Из полного списка атрибутов отноше* ния вычеркните те, которые встречаются в правых частях функциональных зависимостей. Оставшиеся атрибуты образуют вероятный ключ .Докажите корректность этого метода. Какое множество функциональных зависимостей необходимо использовать? 4.

Какой нормальной форме соответствует база данных, приведенная в задании 1? 5.

Определите отношения в ЗНФ для известного списка атрибутов БД и функциональных зависимостей.

Табельный номер (таб. N) Участок -* Цех Фамилия рабочего (ФИО) Таб. N -* Цех Цех Таб. N -» Участок

Участок Таб. N, Дата -* Сумма

Дата Таб: N ФИО

Сумма зарплаты (сумма) Таб. N -* ФИО, Участок 6.

Определите отношения в ЗНФ для известного списка атрибутов БД и функциональных зависимостей.

ФИО служащего (ФИО) ФИО, Дата -* Должность

Должность ФИО -* Должность

Дата ФИО, Дата -* Зарплата

Зарплата ФЙО, Имя_ребеика —? Возраст

Имя_ребенка Возраст ребенка 7. Разработайте структуру двухуровневой сетевой базы данных для заданного множества атрибутов и отношений.

ФИО студента W^HO, Группа)

Группа 5(Преподаватель, Кафедра)

Дисциплина г(ФИО, Дисциплина,

Преподаватель, Оценка)

Преподаватель У(Группа, Преподаватель,

Дисциплина, День занятий)

Кафедра

Оценка экзамена Р(Дисциплина, Кафедра)

День занятий

Студенты и преподаватели-однофамильцы отсутствуют. 8.

Найдите все вероятные ключи в отношении ТЗ из п. 2.2. і. 9.

Для приведенной ниже иерархической структуры базы данных укажите минимально возможный набор атрибутов в отношениях;

Атрибуты: Музей, Город, Экспонат, Год, Выставка, ФИО реставратора.

Отношения: \У(Музей, Город), С(Экспонат, Год поступления), Т(Экспонат, Год реставрации, ФИО), 5(Выставка, Экспонат, Год выставки).

Веерные отношения: (W,C), (С, S), (С, Т).

Названия музеев и выставок не повторяются. 10.

Для баз данных в ЗНФ из заданий 5 и б проверьте их ацикличность. 11.

Из каких атрибутов состоит первичный ключ отношения, в котором нет справедливых функциональных зависимостей?