В начало

Лекция 5

Документальные БД. Теоретико-множественная модель индексирования и поиска. Структура процессов в абстрактной АИПС. Примеры структур документоориентированных баз данных

 

5.1. Документальные информационные системы, основанные на концепции БД

Элементом информационного массива АИС является документ. Документом при этом можно считать как всю совокупность записей (обычно текстов), хранящихся в БД, так и отдельные фрагменты текста - заголовки разделов, абзацы и т. д. при этом большую проблему представляет учет контекста употребления слова, зависящий больше не от синтаксических, а от семантических критериев. При поиске может использоваться сходство внутренней структуры отдельных документов, представленной, например, средствами формального языка типа SGML (Standard Generalized Markup Language). Помимо текста, для поиска могут использоваться содержащиеся в статьях уравнения,  таблицы и графики, хотя пока такие средства  поиска  разрабатываются только для узких специализированных применений (поиск  по  структурным  химическим  формулам, элементам  электронных схем и т. д.).  В более широком смысле, объектами текста могут являться заголовки или абзацы, примечания, ссылки, названия таблиц и т. п.  В некоторых системах применяются свернутые (сигнатурные) образы документов.

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

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

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

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

1) сравниваются не сами объекты (они, как отмечалось, не очень удобны для сравнения), а описания - так называемые «поисковые образы»; 

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

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

Таким образом, до начала поиска необходимо выразить информационную потребность, т. е. специфицировать «образец» той информации, которая необходима для решения задачи в сфере ОД, а по окончании – определить степень решения задачи ОД (а не только соответствие слов запроса словам найденных документов) (слайд 3).

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

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

Первая аналогична табличному способу представления данных о свойствах некоторого множества объектов: отдельному i-ому  атрибуту соответствует  i-я колонка, каждая ячейка которой содержит значение этого атрибута, свойственное отдельному объекту. Характерными чертами такого способа являются:  1) атомарность, т. е. отдельный атрибут отдельного объекта имеет строго одно значение;  2) предопределенность набора атрибутов – все существенные атрибуты объектов, информация о которых должна быть внесена в такую форму, должны быть определены на шаге, предшествующем построению таблицы и внесению в неё значений атрибутов.

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

Безусловно, в качестве поискового образа (ПО) может выступать и полное, «аналитическое» описание. Однако такое решение также имеет недостатки:  1) технические возможности для создания полнотекстовых баз данных появились сравнительно недавно, причем содержание, по которому возможен поиск, представлено, в основном, в форме текстов;  2) свободная лексика, авторская точка зрения и стиль изложения, свойственные первичным документам, затрудняют для пользователя нахождение общего с автором лексического пространства.

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

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

 

5.2. Теоретико-множественная модель индексирования и поиска (слайд 4)

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

С теоретико-множественных  позиций  описываем и документы или элементы массива. Каждый документ есть множество  лексических  единиц - слов, дескрипторов (односложных или составных), терминов индексирования, классификационных рубрик (УДК, МПК, ББК и т.д.). Целесообразно ввести понятие  универсального словаря D,  подмножествами которого являются любые документы.

Таким образом:

, для всех k                                                                 

где   какое-либо сообщение.

Далее,  является элементом некоторого массива L:

L

Подобно универсальному словарю, содержащему все термины, (прототипом  которого может являться тезаурус ИС,  рубрикатор УДК или другая  структура),  необходимо ввести универсальный  массив (массив) L₀, содержащий все сообщения:

L₀ 

, для всех k, причем

Прообразом L_o могут являться: поисковый массив АИС, отраслевой справочно-информационный фонд, массив библиотеки и т.д.

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

- множество  терминов  заголовка;

- множество терминов реферата первоисточника;

- множество дескрипторов индексирования документа.

 

5.3. Линейное описание информационных массивов (слайд 5)

Линейное представление теоретико-множественного образа  документа является дополнительным к теоретико-множественному:

 

Универсальный массив  в линейном представлении есть матрица размерности  ( - мощность множества ):

L₀

Подобные матрицы  известны под названием "матрицы термин-документ".

 

Автоматизированная информационно-поисковая система (АИПС) представляет собой объект, реализующий два типа формализованных процедур:

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

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

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

 

5.4. Структурная схема АИПС.

В структурной схеме (Слайд 6) может быть выделен контур документов и контур запросов.

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

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

Тезаурус есть средство, используемое для индексирования, реализующее отображение D®D , причем в общем случае тезаурус, применяемый для документов, не совпадает с тезаурусом запросов.

 

5.5. Критерий смыслового соответствия (КСС)

КСС есть пара (слайд 7):

КСС = <b^*, k^c>

где b^* есть мера формальной релевантности, или мера близости (способ исчисления близости) поисковых образов документа и запроса,

k^c - пороговое значение меры близости, при превышении которого документ признается формально релевантным соответствующему запросу.

В задачах информационного поиска различают формальную и истинную релевантность.

Формальная релевантность – соответствие документа запросу с точки зрения АИПС.

Истинная релевантность – соответствие документа запросу с точки зрения пользователя.

Данное определение КСС, хотя и не отвечает полностью применяемым в АИПС критериям, тем не менее, позволяет описать такие возможности, как сужение или расширение поискового запроса. Это достигается, соответственно, увеличением или уменьшением порога релевантности k^c.

Известны, например, следующие меры формальной релевантности (слайд 8):

- скалярное произведение векторов ПОЗ и ПОД:

                                                                   

- мера Танимото (нормированное скалярное произведение):

                                            

- мера косинуса угла векторов ПОЗ и ПОД:

                                                                

 

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

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

 

5.6. Логическая структура документальной АИПС.

База данных документальной ИПС IRBIS - это именованная совокупность массива документов и структурированных справочников, обеспечивающих эффективность поиска. Логическая структура БД документальной ИПС IRBIS представлена на слайде 9.

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

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

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

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

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

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

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

- представление материала при вводе и выводе (формат и длина поля, размещение и оформление материала при отображении и т. д.);

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

Таким образом, можно сказать, что документальная БД имеет постреляционную модель данных.

 

5.7. Документо-ориентированная база данных Lotus Domino/Notes

Основой единицей хранения информации в базе данных Lotus Domino/Notes является отдельный документ.

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

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

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

Типы документов. Документы БД Notes могут иметь отношения друг к другу, как «родительский» и «дочерний» документ (слайд 11). Например, если создано приложение для отслеживания внешних контактов, то родительским документом может быть описание организации, дочерними к нему – карточки сотрудников, следующим уровнем дочерних документов – отчеты о встречах с сотрудниками или письма и т. д. (до 32 уровней иерархии)

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

Управление версиями. Lotus Notes содержит функцию управления версиями документа, которая отслеживает многочисленные изменения, вносимые в документ различными пользователями. Автоматическое управление версиями реализовано таким образом, что при каждом сеансе редактирования документ помечается либо как основной, либо как производный от оригинала (ответ). При этом изменения, внесенные в документ Notes одним пользователем, не затираются, когда другой пользователь сохраняет свои изменения в документе. Характер изменений иллюстрируется схемами, представленными на слайдах 12  и 13..

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

Ссылки на документы. Notes имеет средства поддержки гипертекста, т. е. каждый документ может содержать «ссылки» на другие документы в любой базе данных Notes или на документы в WWW.

 

5.8. Модель полнотекстовых документов

Как и в случае уровневых моделей фактографических баз данных, внешние схемы должны определять семантику информационных объектов – свойства, атрибуты и характер последующего использования, а внутренние – типы данных и способы их идент ификации. Реально базы данных полнотекстовых документов не могут быть не гетерогенными, причем, в отличие от фактографических, полнотекстовым базам свойственна еще и разнородность физических представлений: документы, в силу разных причин, скорее всего, будут храниться в том формате, в каком они были получены. То есть «разнородность» надо рассматривать в следующих аспектах:

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

2.    Разнородность может быть свойственна всем документам БД или отдельным. То есть «типизация» может быть определена либо для некоторого идентифицируемого подмножества документов, либо своя структура должна быть определена для каждого документа (например, с хранением схемы вместе с содержанием документа).

3.    Для реализации разнородных БД может использоваться декларативный или процедурный способ определения структуры документа.

Для полнотекстовых БД, имеющих разнородность как на уровне семантики, так и на физическом уровне, согласованность процессов «декомпозиции-синтеза» данных[1] основа на трехуровневой системе следующих базовых информационных компонент:

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

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

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

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

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

В случае, когда для хранения полнотекстовой информации используются БД, структура документов может быть определена двумя путями[2]:

1)      так же, как и для фактографических БД, заданием схемы – последовательности именованных типизированных полей данных;

2)      контекстным определением – использованием специализированных языков разметки (например, HTML или XML), задающим индивидуальные особенности представления материала каждого документа.

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