Интеграция информации
Как утверждалось ранее, WWW содержит все возрастающее число информационных источников, которые могут просматриваться как контейнеры множеств кортежей. Эти "кортежи" могут быть либо встроенными в HTML-страницы, либо быть скрытыми за интерфейсами форм. Благодаря написанию специальных программ, называемых оболочками (wrapper), можно создать иллюзию, что данный Web-сайт обслуживает множества кортежей. Будем называть комбинацию такого Web-сайта и ассоциированной с ним оболочки Web-источником.
Задача системы интеграции информации, поддерживаемой средствами Web, состоит в том, чтобы отвечать на запросы, которые могут потребовать извлечения и комбинирования данных из множества Web-источников. Например, рассмотрим такую предметную область, как кино. Сайт Internet Movie Database содержит исчерпывающие данные о кинофильмах, составе исполнителей ролей, жанрах и руководителях съемки. Во множестве других Web-источников (например, на Web-сайтах большинства газет) могут быть найдены также рецензии на кинофильмы, а некоторые Web-источники предоставляют расписания показа кинофильмов. Комбинируя данные из этих источников мы можем отвечать на запросы типа: выдать мне какой-либо фильм с Фрэнком Синатрой в главной роли, который можно посмотреть сегодня вечером в Париже, время сеанса и рецензии на него.
Для ответов на запросы с использованием множества Web-источников был создан целый ряд систем [GMPQ+97, EW94, WBJ+95, LRO96, FW97, DG97b, AKS96, Coh98, AAB+98, BEM+98]. Многие из проблем, с которыми пришлось столкнуться при их разработке, аналогичны проблемам, связанным с созданием неоднородных систем базы данных [ACPS96, WAC+93, HZ96, TRV98, FRV96, Bla96, HKWY97]. Наряду с этим, системы интеграции данных Web должны иметь дело с: (1) с большим и развивающимся количеством Web-источников, (2) немногими метаданными, характеризующими источники, и (3) большой степенью автономности источников.
Важные различия при построении систем интеграции данных, а, следовательно, и систем интеграции данных Web, возникают в связи с тем, принимается ли подход, основанный на хранилищах данных, или виртуальный подход (см.
для сравнения [HZ96, Hul97]). В случае использования первого подхода данные из множества Web-источников загружаются в хранилище данных, и далее все запросы будут обращены к этому хранилищу данных. В таком случае необходимо, чтобы при изменении данных в источниках обновлялось и хранилище данных. Однако преимущество состоит в том, что может быть гарантирована адекватная эффективность на стадии обработки запроса. При виртуальном подходе данные остаются в Web-источниках, и запросы к системе интеграции данных декомпозируются на стадии исполнения на запросы к отдельным источникам. При таком подходе данные не тиражируются, и тем самым гарантируется их актуальность на стадии обработки запросов. С другой стороны, поскольку Web-источники автономны, для обеспечения адекватной эффективности необходимы более изощренные техника оптимизации запросов и исполнения. Виртуальный подход более уместен при построении таких систем, где число источников велико, данные изменяются часто, и имеется слабый контроль над Web-источниками. По этим причинам большинство исследований недавнего времени было сосредоточено на виртуальном подходе, и поэтому им прежде всего будет посвящено наше дальнейшее обсуждение. Нужно, однако, подчеркнуть, что многие проблемы, которые возникают при виртуальном подходе, возникают также и при использовании хранилищ данных (хотя зачастую и в несколько иной форме). Следовательно, наше обсуждение имеет отношение к обоим указанным случаям. Прежде чем перейти непосредственно к обсуждению, нам хотелось бы обратить внимание читателей на два коммерческих приложения систем интеграции данных Web, в одном из которых был принят подход с хранилищем данных [Jun98], а в другом - виртуальный подход [Jan98].
Архитектура прототипа системы виртуальной интеграции данных показана на рис. 2. Имеется две главных особенности, отличающие такую систему от традиционной системы базы данных:
- Как уже говорилось ранее, система не взаимодействует непосредственно с локальными менеджерами хранения данных.
Вместо этого для получения данных механизмы исполнения запросов взаимодействуют с множеством оболочек (wrapper). Оболочка - это специфическая для каждого Web-сайта программа, задачей которой является трансляция данных Web-сайта в форму, позволяющую осуществлять дальнейшую их обработку средствами системы интеграции данных. Например, оболочка может извлекать множество кортежей из HTML-файла. Необходимо подчеркнуть, что оболочка обеспечивает только интерфейс к данным, обслуживаемым рассматриваемым Web-сайтом. Поэтому, если Web-сайт предоставляет только ограниченный доступ к данным (например, через интерфейс формы, который требует от пользователя некоторого ввода), то и связанная с ним оболочка может поддерживать лишь ограниченные виды доступа к данным. - Второе отличие от традиционных систем заключается в том, что пользователь не формулирует запросы непосредственно в терминах той схемы, в соответствии с которой хранятся данные. Такой подход продиктован тем, что одной из важнейших целей систем интеграции данных является стремление к освобождению пользователя от необходимости знания специфических особенностей источников данных и взаимодействия с каждым из них. Вместо этого пользователь формулирует запросы в терминах промежуточной (mediate) схемы. Промежуточная схема - это множество виртуальных отношений, которое проектируется для каждого конкретного приложения системы интеграции данных. Отношения промежуточной схемы фактически нигде не хранятся. В связи с этим система интеграции данных должна прежде всего переформулировать запрос пользователя в такие запросы, которые обращены непосредственно к схемам в источниках. Для выполнения шага переформулирования запроса системе интеграции данных необходимо множество описаний источников. Описание источника информации специфицирует его содержание (например, указывает, что он содержит фильмы), атрибуты, которые могут быть найдены в источнике (например, жанр, состав актеров), ограничения на содержание источника (например, содержит только американские фильмы), полноту и надежность источника, и, наконец, возможности обработки запросов этого источника (например, может выполнять только выборку данных или может отвечать на произвольные запросы SQL).
Рассмотрим теперь основные проблемы, которые исследуются в работах, связанных с созданием систем интеграции данных Web.
Спецификация промежуточной схемы и переформулирование запросов: Промежуточная схема в системе интеграции данных представляет собой совокупность наборов имен атрибутов, которые используются для формулировки запросов. Для обработки запроса система интеграции данных должна транслировать его формулировку в терминах промежуточной схемы в запросы к источникам данных, которые имеют их собственные локальные схемы. Чтобы сделать это, системе необходимо множество описаний источников. Несколько недавних исследований было посвящено проблемам определения принципов спецификации описаний источников и их использования для переформулирования запросов. Вообще говоря, было предложено два общих подхода: Глобальная схема как представление (Global as View, GAV) [GMPQ+97, PAGM96, ACPS96, HKWY97, FRV96, TRV98] и Локальная схема как представление (Local as View, LAV) [LRO96, KW96, DG97a, DG97b, FW97]. Детальное сопоставление этих подходов можно найти в [Ull97].
При подходе GAV для каждого отношения R в промежуточной схеме, мы записываем запрос над отношениями источников, которые определяют, каким образом можно получить кортежи R из источников. Подход LAV является противоположным. Для каждого источника информации S мы записываем запрос над отношениями в промежуточной схеме, который описывает, какие кортежи находятся в S. Главное преимущество подхода GAV состоит в том, что переформулирование запросов является очень простым, поскольку оно сводится к развертыванию представлений. Напротив, при подходе LAV можно более просто добавлять или удалять источники, так как описания источников не должны принимать во внимание возможные взаимодействия с другими источниками, как в случае подхода GAV. В случае LAV, кроме того, более просто описываются ограничения на содержание источников. Проблема переформулирования запросов становится некоторым вариантом проблемы ответа на запросы с использованием представлений [YL87, TSI96, LMSS95, CKPS95, RSU95, DG97b].
Полнота данных в Web-источниках: Вообще говоря, источники, которые мы находим на WWW, не обязательно являются достаточно полными в той предметной области, к которой они относятся. Например, маловероятно, что некоторый источник библиографии в полной мере представляет область информатики. Однако, в некоторых случаях, мы можем высказывать определенные утверждения о степени полноты источников. Например, база данных DB&LP *3) содержит полную подборку работ, опубликованных в трудах наиболее важных конференций по базам данных. Знания о полноте Web-источника могут помочь системе интеграции данных несколькими способами. Наиболее важно, что отрицательный ответ от полного источника является значимым, поскольку он позволяет исключить бессмысленные обращения системы интеграции данных к другим источникам. Проблема описания полноты Web-источников и использования этой информации для обработки запросов исследуется в работах [Mot89, EGW94, Lev96, Dus97, AD98, FW97]. В работе [FKL97] предлагается вероятностный формализм для описания содержания и перекрытий источников информации, а также приводятся алгоритмы оптимального выбора источников.
Различие возможностей обработки запросов: В аспекте систем интеграции данных Web, Web-источники имеют, как представляется, в значительной степени различные потенциальные возможности обработки запросов. Главные причины таких различий заключаются в том, что: (1) внутренние данные источников могут фактически храниться в структурированных файлах или в унаследованной системе, и в таких случаях интерфейс к этим данным, естественно, ограничен, и (2) даже если данные хранятся в традиционной системе базы данных, Web-сайт может обеспечить лишь ограниченные возможности доступа по причинам безопасности или эффективности.
Для создания эффективной системы интеграции данных эти возможности должны явным образом описываться для системы, строго учитываться и в максимально возможной степени использоваться для повышения эффективности. Будем различать два типа возможностей: отрицательные возможности, которые ограничивают способы доступа к данным, и положительные возможности, когда источник способен выполнять некоторые алгебраические действия в дополнение к простым выборкам данных.
Основная форма отрицательных возможностей - ограничения на способы связывания (binding patterns), которые могут использоваться в запросах, адресованных источнику. Например, обращаясь к сайту Internet Movie Database, невозможно запросить выборку всех фильмов с их актерскими составами. Вместо этого имеется возможность запросить сведения об актерах данного фильма или о множестве фильмов, в которых играет данный конкретный актер. Проблема ответа на запросы при наличии ограничений на способы связывания рассматривается в работах [RSU95, KW96, LRO96, FW97].
Положительные возможности порождают дополнительное требование к системе интеграции данных. Если источник данных обладает способностью выполнять такие операции, как селекция и соединение, мы хотели бы в максимально возможной степени перенести обработку на источник, сокращая тем самым объем локальной обработки и количество данных, передаваемых по сети. Проблема описания вычислительных возможностей источников данных и их использования для создания планов исполнения запросов рассматривается в [PGGMU95, TRV98, LRU96, HKWY97, VP97a].
Оптимизация запросов: Во многих работах по системам интеграции данных Web исследовались проблемы выбора минимального набора Web-источников, к которым необходимо осуществить доступ для обработки заданного запроса, и определения минимального запроса, который должен быть адресован каждому из них. Однако проблема выбора оптимального плана исполнения запроса для доступа к Web-источникам до сих пор не привлекала достаточного внимания. Поэтому она мало отражена в литературе по интеграции данных [HKWY97] и остается активной областью исследований. Дополнительные трудности, связанные с оптимизацией запросов для источников в среде WWW, состоят в том, что мы имеем незначительную статистику по данным в источниках, и, следовательно, мало информации для оценки стоимости планов исполнения запросов. В работе [NGT98] рассматривается проблема калибровки модели стоимости для планов исполнения запросов в этом контексте.
В [YPAGM98] обсуждается проблема оптимизации запросов слияния (fusion query), которые являются специальным классом запросов на интеграцию данных, предусматривающих выборку различных атрибутов данного объекта из множественных источников. Мы полагаем, что обработка запросов в системах интеграции данных - это область, где можно было бы извлечь пользу из таких идей, как перемежающиеся планирование и исполнение, а также вычисление условных планов [GC94, KD98].
Механизмы исполнения запросов: Еще меньше внимания было уделено проблеме разработки механизмов исполнения запросов, предназначенных для интеграции данных Web. Необходимость создания таких механизмов вызвана автономностью источников данных и непредсказуемостью пропускной способности сети. В частности, при доступе к Web-источникам могут иметь место начальные задержки, прежде чем данные начинают передаваться, и даже если это случается, поступление данных может быть очень интенсивным. В работах [AFT98, UFA98] рассматривается проблема адаптации планов исполнения запросов к начальным задержкам в поступлении данных.
Создание оболочек: Напомним, что роль оболочки (wrapper) заключается в обеспечении выборки данных из Web-сайта в форме, которая дает возможность манипулировать ими системе интеграции данных. Например, задача оболочки может состоять в формулировании запроса к Web-источнику c использованием интерфейса в виде формы и выборке множества кортежей ответа из результирующей HTML-страницы. Трудность создания оболочек заключается в том, что HTML-страница обычно разрабатывается для просмотра человеком, а не для выборки данных программами. По этой причине данные часто оказываются встроенными в тексты на естественном языке или скрытыми в примитивах графического представления. Кроме того, форма HTML-страниц часто изменяется, что создает трудности для поддержки оболочек. Несколько работ было посвящено проблеме конструирования инструментальных средств для быстрого создания оболочек. Один из классов таких инструментальных средств (см., например, [HGMN+98, GRVB98]) основан на специализированных грамматиках, позволяющих специфицировать, каким образом данные размещаются на HTML-странице, и, тем самым, как извлекать требуемые данные.
Второй класс средств основан на применении методов индуктивного обучения для автоматического обучения оболочки. Используя алгоритмы, базирующиеся на таких методах, мы сначала задаем системе набор HTML-страниц таких, что содержащиеся в них данные помечены. На основе этих обучающих примеров автоматически строится грамматика, с помощью которой может осуществляться выборка данных из последующих страниц. Конечно, чем большее число примеров мы задаем системе, тем более точной будет порождаемая в результате грамматика, и задача состоит в том, чтобы найти такие языки для оболочек, которые можно обучить с помощью малого числа примеров. Впервые идея конструирования оболочки на основе индуктивного обучения и набор алгоритмов для обучения простых классов оболочек были преложены в [KDW97]. Алгоритм, описанный в [AK97], использует специфические эвристические подходы для общепринятых применений HTML с тем, чтобы добиться быстрого обучения. Следует также отметить, что методы машинного обучения также использовались для изучения отображения между схемами источников и промежуточными схемами [PE95, DEW97]. Работа [CDF+98) представляет собой первый шаг в попытке ликвидировать существующий разрыв между подходами к проблеме создания оболочек, основанными на машинном обучении и на обработке естественного языка. В заключение, нужно отметить, что появление языка XML может обеспечить разработчикам Web-сайтов возможности для экспортирования данных, содержащихся на их сайтах, в машиночитаемой форме, тем самым значительно упрощая создание оболочек.
Соответствие объектов на множестве источников: Одна из наиболее трудных проблем, связанных с получением ответов на запросы над множеством источников, заключается в выявлении ситуации, когда два объекта, упомянутые в двух различных источниках, представляют один и тот же объект в реальном мире. Эта проблема возникает потому, что каждый источник использует свои собственные соглашения об именовании и обозначениях. В большинстве систем эта проблема решается благодаря использованию специфических для предметной области эвристических подходов (как, например, в [FHM94]).В системе WHIRL [Coh98] соответствие объектов на множестве источников поддерживается с помощью методов из области информационного поиска. Кроме того, соответствующие объекты изящно интегрируются в новом алгоритме исполнения запросов.
