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

Максим Гринев

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

Между этими двумя крайностями находится наибольший объем данных. Такие данные и называются полуструктурированными. Примером, полуструктурированных данных может быть форматированный текст, HTML страницы, данные в нетрадиционных форматах (например, в ASN.1), в формате XML и т.д. Кроме того, в последнeе время проводятся большие исследования, связанные с вопросами интеграции распределенных данных. При этом даже при интеграции нескольких источников, данные которых достаточно хорошо структурированы, не удается придумать жесткую схему для полученных обобщенных данных. Таким образом, опять приходится иметь дело с полуструктурированными данными, т.е. схема которых размыта.

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

• Управление данными с «размытой» структурой.
• Интегрировать данные из разных источников.

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

Полуструктурированные данные

К полуструктурированным относят такие данные, в которых можно выделить некоторую структуру (в этом их отличие от аудио или видео данных), но структура этих данных не достаточно строгая для хранения их в традиционных системах (реляционных, объектно-ориентированных [GM1]). Ниже перечислены основные особенности полуструктурированных данных, которые раскрывают их сущность и определяют требования к системам управления такими данными.

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

Многие данные хотя и имеют некоторую достаточно строгую структуру, но эта структура неявная. Например, текстовые документы или HTML страницы на Web-серверах (в этом случае некоторое, но не полное представление о структуре помогут дать теги). Поэтому необходимо разрабатывать методы выявления неявной структуры, таких данных. В этом направлении уже ведется ряд работ [AK97,NAM97].

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

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

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

Модели данных

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

Почему выгодно использовать легковесную модель? К легковесным моделям данных относят простые и очень гибкие модели данных. При использовании таких моделей удается работать с данными, которые имеют сколь угодно сложную или неправильную структуру. Например, используя легковесную модель, удается интегрировать данные из разных источников, каждый из которых использует свою отличную и сложную структуру для хранения данных. Расплатой за гибкость является сложность оптимизации доступа к данным в такой модели. Пример легковесной модели Object Exchange Model (OEM) подробно рассмотрен ниже в этой главе.

Почему выгодно использовать тяжеловесную модель? Часто из общей совокупности полуструктурированных данных удается выделить часть, которая имеет вполне строгую структуру, тогда для работы с этой частью можно использовать приимущества эффективного доступа, которые нам предоставляют традиционные модели данных. Например, отношения с индексами позволяют эффективно и естественно моделировать многие сущности реального мира. Опираясь на такие рассуждения, можно построить модель данных, которая будет представлять из себя интеграцию общеизвестных структурных элементов из различных моделей (объекты, отношения, упорядоченные коллекции и т.д.). Но какой бы богатой получившаяся модель не была существует возможность, что некоторые данные не впишутся в нее. Кроме того, становится невозможным придумать элегантный язык запросов для такой модели. В качестве примера тяжеловесной модели можно привести ADM (ARANEUS Data Model), используемая в системе ARANEUS [AMM97], которая разработана для интеграции информации Web-серверов.

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

OEM модель была разработана специально для полуструктурированных данных [PGMW95]. Эта модель используется системой Lore [HAG97], которая является одной из самых развитых систем управления полуструктурированными данными на сегодняшний день. Среди основных достоинств OEM элегантность и гибкость, что позволяет моделировать структуры данных традиционных систем (реляционных, объектно-ориентированных и т.д.). Данные в этой модели представляются в виде ориентированного графа с именованными ребрами. Вершины графа — это объекты. Каждый объект имеет уникальный идентификатор. Объекты могут быть простыми (атомарными) или сложными. Простые объекты не имеют исходящих ребер, но могут принимать значения одного из базовых атомарных типов, таких как целый, вещественный, строковый, звука, видео и т.п. Сложные объекты имеют исходящие ребра и не имеют значения. Некоторым объектам графа приписываются имена. Такое имя используется как точка входа в граф для описания путей при формировании запросов (вершину с именем также называют корнем).

OEM-база данных не имеет фиксированной схемы. Вся семантическая информация содержится в именах ребер графа. Сам же граф может изменяться динамически. Таким образом, база данных имеет «самоописательный» характер. Понятия целостности или корректности данных в OEM не вводится, за счет чего и достигается большая гибкость представления данных.

Рассмотрим пример OEM-базы данных сотрудников университетской группы, занимающейся вопросами управления данными приведенный на рис. 1.

Рис. 1. База данных OEM

На этом примере видно, что каждый объект имеет свой уникальный идентификатор (на рисунке изображен числом, перед которым стоит символ &), кроме того, одному из объектов с идентификатором &1 присвоено имя DBGroup, таким образом, все пути в графе будут описываться от этой вершины. Обратим особое внимание на то, что одни и те же сущности реального мира представлены в этой базе данных с помощью различных структур или типов данных. Например, о сотруднике группы с именем Clark известно только его имя, в то время как о Smith содержится более полная информация, при этом для ее описания используется два ребра с одним именем, что допустимо в OEM и является типичным примером неправильности данных. Или номер комнаты (&18) представлен в виде строки, тогда как номер другой комнаты (&20) целое число.

17.05.1999г