Моделирование Web и запросы
Если Web рассматривается как большая, графового типа база данных, естественно формулировать запросы, которые выходят за рамки основной парадигмы информационного поиска, поддерживаемой современными механизмами поиска, и принимают во внимание структуру. Имеется в виду не только внутренняя структура страниц Web, но и внешняя структура связей, которые их соединяют. В часто цитируемой статье об ограничениях гипертекстовых систем [Hal88] Халаш говорит:
"Поиск по содержанию игнорирует структуру гипермедийной сети. Напротив, при структурном поиске в гипермедийной структуре осуществляется поиск таких подсетей, которые соответствуют заданному шаблону" и приводит примеры, где такие запросы оказываются полезными.
3.1. Структурный информационный поиск
Первыми инструментальными средствами для обработки запросов в Web, были известные поисковые машины, которые теперь широко развернуты и активно используются. Они основаны на поисковых индексах слов и фраз, встречающихся в документах, обнаруженных "роботами" (crawler) Web. Совсем недавно были предприняты усилия, направленные на преодоление ограничений этой парадигмы за счет использования в запросах структуры связей. Например, в [Kle98], [BH98] и [CDRR98] предлагается использовать структуру Web для анализа многочисленных сайтов, выдаваемых поисковой машиной в качестве релевантных запросу, с тем, чтобы выделить из них те, которые, вероятно, являются авторитетными источниками по интересующему вопросу. Для того, чтобы поддержать анализ связности (connectivity) для этого и других приложений (например, для эффективных реализаций языков запросов, описанных ниже), быстрый доступ к структурной информации обеспечивается сервером связности [BBH+98]. Прототип поисковой машины Web следующего поколения Google [BP98] интенсивно использует структуру Web для повышения производительности функционирования "робота" и индексирования. Другие методы, опирающиеся на использование структуры связей, предлагаются в [PPR96, CK98].
В этих работах структурная информация обычно используется "за сценой" для повышения качества ответов на запросы, которые в чистом виде ориентированы на содержание. Спертус [Spe97] указывает много полезных приложений, связанных с обработкой запросов, которые в явном виде принимают во внимание структуру связей.
3.2. Родственные парадигмы запросов
В этом подразделе мы кратко опишем несколько семейств языков запросов, которые не разрабатывались специально для использования в среде Web. Однако поскольку концепции, на которых они основаны, по своему духу подобны концепциям языков запросов Web, которые мы здесь обсуждаем, эти языки могут быть также полезными для приложений Web.
Гипертекстовые/документальные языки запросов: Ряд моделей и языков запросов для структурированных документов и гипертекстов был предложен еще в период, предшествующий появлению Web. Так, Абитебул и др. [ACM93] и Кристофидес и др. [CACS94] отображают документы в объекты объектно-ориентированной базы данных посредством семантических действий, присоединенных к грамматике. Далее можно делать запросы относительно такого представления базы данных с использованием языка запросов базы данных. Новый аспект этого подхода заключается в возможности производить запросы относительно структуры с помощью переменных-путей. Гутинг и др. [GZC89] моделируют документы, использующие вложенные упорядоченные отношения и используют некоторое обобщение алгебры вложенных отношений как язык запросов. Бири и Корнацкий [BK90] предлагают логику, формулы которой специфицируют шаблоны на графе гипертекста.
Графовые языки запросов: Исследования, связанные с использованием графов для моделирования баз данных, которые были стимулированы такими приложениями, как разработка программного обеспечения и управление компьютерными сетями, привели к созданию языков целого ряда языков, например, G, G+ и GraphLog [CMW87, CMW88, CM90], основанных на графах. В частности, G и G+ основаны на помеченных графах. Они поддерживают использование в запросах правильных выражений путей и графовых конструкций.
Язык GraphLog, семантика которого основана на Datalog, был применен в [CM89] для гипертекстовых запросов. Переденс и др. [PdBA+92] разработали графовый язык запросов для объектно-ориентированных баз данных.
Языки запросов для слабоструктурированных данных: Такие языки запросов для слабоструктурированных данных, как Lorel [AQM+97], UnQL [BDHS96] и STRUDQL [FFLS97], также используют помеченные графы как гибкую модель данных. В отличие от графовых языков запросов, они делают акцент на возможности запрашивать схему и приспосабливаться к нерегулярностям в данных, таких, например, как опущенные или повторяющиеся поля, неоднородные записи. В аналогичной работе из области объектно-ориентированных систем [Har94] предложены модели и запросы с "недостаточной схемой" (schema-shy) для управления информацией относительно артефактов разработки программного обеспечения.
Как уже говорилось, эти языки не были разработаны специально для Web, и в них не делается различия, например, между дугами графа, которые представляют соединения между документом и одной из его частей, и дугами, представляющими гиперссылки из одного документа Web на другой. Их модели данных, хотя они и элегантны, не слишком богаты, поскольку в них испытывается недостаток таких важных средств, как записи и упорядоченные коллекции.
3.3. Языки запросов первого поколения для Web
Авторы языков запросов первого поколения для Web стремились сочетать в них возможности запросов, основанных на содержании, присущие поисковым машинам Web, с возможностями запросов, основанных на структуре, подобными тем, которые характерны для систем баз данных. Такие языки, к числу которых относятся W3QL [KS95], WebSQL [MMM97, AMM97a] и WebLog [LSS96], сочетают в себе условия, налагаемые на образцы текста, появляющиеся в документах, с графовыми шаблонами, описывающими структуру связей. Далее мы будем использовать WebSQL для демонстрации примеров запросов, возможных в языках такого рода.
Язык WebSQL: В языке WebSQL предлагается моделировать Web как реляционную базу данных, состоящую из двух (виртуальных) отношений: Документ и Якорь.
Отношение Документ содержит по одному кортежу для каждого документа из Web, а отношение Якорь - по одному кортежу для каждого якоря в каждом документе из Web. Такая реляционная абстракция Web позволяет нам использовать для формулировки запросов язык, подобный SQL.
Если бы Документ и Якорь были фактическими отношениями, мы могли бы просто использовать SQL, чтобы записывать на нем запросы. Но поскольку эти отношения являются полностью виртуальными и не имеется какого-либо способа производить над ними вычисления, мы не можем оперировать ими непосредственно. Семантика WebSQL зависит от материализации частей этих отношений путем спецификации представляющих интерес документов во фразе FROM запроса. Основным способом материализации части Web является навигация из известных URL. Для описания такой навигации используются правильные выражения путей. Атом такого правильного выражения может иметь форму d1 = > d2, означающую, что документ d1 указывает на d2, и d2 хранится на ином сервере, чем d1. Он может иметь также форму d1 - > d2, которая, в свою очередь, означает, что d1 указывает на d2, и d2 хранится на том же самом сервере, что и d1.
Предположим, например, что мы хотим найти список триплетов вида (d1, d2, метка), где d1 - документ, хранимый на нашем локальном сайте, d2 - документ, хранимый где-либо еще, и d1 указывает на d2 с помощью связи, помеченной меткой. Допустим также, что все наши локальные документы достижимы из www.mysite.start. Тогда указанную задачу можно решить с помощью запроса:
SELECT d.url, e.url, a.label FROM Document d SUCH THAT <www.mysite.start> -> d, Document e SUCH THAT d => e, Anchor a SUCH THAT a.base = d.url WHERE a.href = e.url
Предложение FROM порождает экземпляры двух переменных, определенных на отношении Документ, - d и e, и одной переменной a - на отношении Якорь. Области определения переменной d принадлежит каждый локальный документ, достижимый из начального документа, а e принимает значения на множестве всех не локальных документов, достижимых непосредственно из d.
В свою очередь, значением переменной a может являться каждая связь, которая исходит из документа d. Дополнительное условие, предписывающее, чтобы целевым документом связи a был документ e, задается предложением WHERE. Другим способом материализации части отношений Документ и Якорь является использование условий, налагаемых на содержание (content condition). Например, если для нас представляли интерес только документы, которые содержат строку "база данных", мы могли бы добавить в предложение FROM условие: d MENTIONS "база данных". В этом случае в реализации использовались бы поисковые машины для генерации возможных документов, удовлетворяющих условию NENTION.
Другие языки: Язык W3QL [KS95] подобен, по существу, WebSQL, с некоторыми значительными различиями: он использует внешние программы (аналогично определяемым пользователем функциям в объектно-реляционных языках) для спецификации условий, налагаемых на содержание файлов, а не формирование условий в синтаксисе языка, и это обеспечивает механизмы для обработки форм, встречающихся в процессе навигации. В работе [KS98] Конопницкий и Шмуэли описывают планируемые расширения, позволяющие превратить W3QL в то, что мы называем теперь языками второго поколения. Эти расширения предусматривают моделирование внутренней структуры документов, иерархическое моделирование Web, в котором явно фигурирует понятие Web-сайта, а также отказ от использования метода внешних программ для спецификации в пользу обобщенного расширяемого метода, основанного на стандарте MIME.
WebLog [LSS96] отличается от рассмотренных выше языков использованием дедуктивных правил вместо SQL-подобного синтаксиса (см. описание FLORID ниже).
WQL, язык запросов проекта WebDB [LSCH98], подобен WebSQL, но он в большей мере поддерживает функциональные возможности SQL, допуская, например, агрегацию и группирование, и, кроме того, обеспечивает ограниченную поддержку запросов внутридокументной структуры. Это обстоятельство позволяет отнести его к классу языков, обсуждаемых в следующем подразделе.
3.4. Второе поколение: Языки манипулирования данными Web
Рассмотренные выше языки интерпретируют страницы Web как атомарные объекты с двумя свойствами: они могут содержать или не содержать некоторые текстовые образцы и они могут указывать на другие объекты. Опыт использования таких языков показывает, что имеется две основные области приложений, для которых они могут быть полезны. Одна из них, рассматриваемая в разделе 4, - создание оболочек (wrapping) для данных, трансформация и реструктуризация данных. Вторая из этих областей - создание и реструктуризация Web-сайтов - обсуждается в разделе 5. В обеих этих областях приложений часто оказывается существенной возможность иметь доступ к внутренней структуре страниц Web из языка запросов, если мы хотим, чтобы декларативные запросы могли оперировать большой частью задачи. Например, задача извлечения множества кортежей из HTML-страниц сайта Internet Movie Database требует синтаксического анализа HTML-страниц и избирательного доступа к некоторым поддеревьям в дереве синтаксического анализа.
В этом подразделе мы опишем языки запросов второго поколения для Web, которые мы называем "языками манипулирования данными Web". Эти языки превосходят языки первого поколения в двух важных аспектах. Прежде всего, они обеспечивают доступ к структуре объектов Web, которыми они манипулируют. В отличие от языков первого поколения, они моделируют внутреннюю структуру документов Web, а также внешние связи, которые их соединяют. Они поддерживают связи для моделирования гиперссылок, а некоторые из них поддерживают также упорядоченные совокупности записей для более естественного представления данных. Во-вторых, эти языки обеспечивают возможности создания новых сложных структур в результате запроса. Поскольку данные в Web обычно являются слабоструктурированными, в этих языках придается особое значение поддержке возможностей для работы со слабоструктурированными данными. Далее кратко описываются три языка этого класса: WebOQL [AM98], STRUQL [FFLS97] и FLORID [HLLS97].
