Консалтинг и автоматизация в области управления
эффективностью банковского бизнеса

Журнал ВРМ World

Языки запросов XML: опыт использования и примеры

За прошедшие годы специалисты в области баз данных пришли к более или менее единому мнению о механизме обработки запросов. За это время эта мы были свидетеляим эволюции от реляционных баз данных через объектно-ориентированные базы данных к полуструктурированным базам, однако многие принципы остались теми же. Из рассматриваемых в этом обзоре четырех языков три были разработаны специалистами по полуструктурированным базам: XML-QL [15], YATL [11], [12] и Lorel [2], [18]. Эти языки были созданы независимо друг от друга группами разработчиков, расположенными на расстоянии тысяч миль друг от друга, однако они демонстрируют поразительное подходов. За эти годы специалисты по обработке документов также собрали определенный объем информации об организации поиска в документах и форматирования. Эта группа специалистов разработала модели структурированного текста и методов поиска (таких, как алгебра областей(region algebras [10]). По мнению этих специалистов, для обработки XML-данных подходит язык XQL [26], [25].

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

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

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

По мнению авторов, перечисленные выше языки запросов имеют ряд особенно важных черт:

  • Запросы, состоящие из трех частей: оператор шаблона, оператор фильтра и оператор конструктора. Информация, проходящая между этими операторами, может быть смоделирована как отношение, имеющее плоскую и неупорядоченную структуру.
  • Конструкции для выражения вложенности и упорядоченности. Этот процесс может сохранять структуру исходного документа или позволять его полную реструктуризацию - и это является ключевым преимуществом такого подхода. Эти конструкции содержат вложенные запросы, группировки соответствующих данных с помощью Skolem functions, либо представляют собой явные операторы группировки, индексации и сортировки.
  • Использование оператора объединения для соединения данных из различных документов, соответствующих операциям объединения в отношениях.
  • Использование тэговых переменных или спецификации пути для поддержки запросов в отсутствие точной информации о структуре документа и доступа к вложенным данным.

Они имеют и другие полезные свойства:

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

Эти возможности можно проиллюстрировать набором примеров: рассмотрим типичные запросы к базе данных, содержащей информацию о книгах, и покажем, как это выглядит на XML-QL, YATL, Lorel и XQL. Первые три языка почти всегда используют для определенного запроса одинаковые структуры, тогда как XQL часто применяет другую структуру. В ряде случаев может быть невозможно выразить запрос на языке XQL. (Разумеется, поскольку XQL исходит из требований специалистов по обработке документов, существует и достаточно большое число запросов, которые могут быть выражены на XQL, но не могут - на XML-QL, YATL или Lorel.)

Эта статья была написана для XML Query Working Group с целью поделиться опытом специалистов, изучающих базы данных, в области проектирования и реализации языков запросов XML. Авторы не предлагают принять XML-QL, YATL или Lorel в качестве исходного языка этой рабочей группы. Однако в свете такого поразительного сходства нельзя игнорировать информацию, собранную сообществом исследователей баз данных. Таким образом, авторы действительно предлагают рассматривать общие идеи и свойства этих языков в качестве отправного пункта для этой рабочей группы и критерия сравнения для языка, рекомендованного рабочей группой.

В данной статье авторы не описывают ряд важных, но несоответствующих выбранному направлению вопросов - таких, как, например, среда, в которой должен работать язык запросов XML. Вместо этого, авторы отсылают читателя к объемному списку предпочтительных свойств языка, и связанных с ними проблем [21]. Кроме того, авторы предлагают ознакомиться с фундаментальным содержанием исследования, включая и мотив разработки и типичные приложения полуструктурированных данных, [1], [4], [27], модели полуструктурированных данных, [24], проектирование языка запросов [2], [6], [16], обработка и оптимизация запросов [22], языки схем [3], [5], [19] и выделение схем [23].

Следующий раздел описывает десять важнейших, по мнению авторов статьи, запросов. Раздел 3 представляет другие полезные, но менее важный свойства.

2. Десять важнейших запросов

Здесь авторы представляют примеры запросов, иллюстрирующие десять важнейших, по их мнению, свойств языка запросов XML. Эти примеры в свою очередь проиллюстрированы с помощью XML-QL, YATL, Lorel и XQL. Везде, где это возможно, первым приводится пример на языке, предоставляющем наиболее естественную или простую формулировку.

Авторы используют следующий рабочий пример. Исходный XML находится в документе www.bn.com/bib.xml, содержащем библиографические записи, описанные в следующем DTD.

<!ELEMENT bib  (book* )>
 <!ELEMENT book  (title,  (author+ | editor+ ),
                  publisher, price )>
 <!ATTLIST book  year CDATA  #REQUIRED >
 <!ELEMENT author  (last, first )>
 <!ELEMENT editor  (last, first, affiliation )>
 <!ELEMENT title  (#PCDATA )>
 <!ELEMENT last  (#PCDATA )>
 <!ELEMENT first  (#PCDATA )>
 <!ELEMENT affiliation  (#PCDATA )>
 <!ELEMENT publisher  (#PCDATA )>
 <!ELEMENT price  (#PCDATA )>

Этот DTD определяет, что элемент book (книга) содержит один элемент title (заголовок), один или более элементов author (автор) или один или более элементов editor (редактор), один элемент publisher (издатель) и один элемент price (цена), а также имеет атрибут year (год). Элемент author содержит фамилию и имя (last name и first name). Элемент editor также содержит принадлежность. Элементы title, last name, first name, publisher или price являются текстовыми.


2.1. Выборка и извлечение

Первый пример выбирает все заголовки книг, выпущенные издательством Addison-Wesley после 1991. Чтобы придать вычислительному блоку запроса максимум гибкости, порядка вывода не задано. В разделе 2.8 будет показано, как сортировать заголовки в порядке документов или в алфавитном порядке.

В XML-QL, YATL и Lorel запрос состоит из трех частей: оператора шаблона, сопоставляющего вложенные элементы во введенном документе и связывает переменные; оператора фильтра, проверяющего связанное переменные; и оператора конструктора, определяющего результат в терминах связанных переменных. В конструкторе могут быть вложениые запросы. XQL поддерживает шаблоны и фильтры, но не поддержимвает конструкторы. XQL может применять фильтры к элементам и атрибутам, а также к инструкциям обработки (processing instructions), комментариям и к внешним ссылкам(entity references). Замечено, что XML-QL, YATL и Lorel все обеспечивают синтаксические варианты для наиболее часто употребляемых в запросах идиом, но для большей понятности авторы представляют запросы в их наиболее общей форме.

Авторы полагают, что запросы определяют фиксированный источник данных (через один или более URL) и возвращают правильно сформированный XML. Разумеется, запросы могут обрабатывать другие представления XML - такие, как DOM. Например, XML-QL имеет графовый интерфейс и некоторые реализации XQL имеют интерфейс к DOM.


XML-QL

CONSTRUCT <bib> {
  WHERE 
    <bib>
      <book year=$y>
        <title>$t</title>
        <publisher><name>Addison-Wesley</name></publisher>
      </book> 
    </bib> IN  www.bn.com/bib.xml , 
    $y > 1991
  CONSTRUCT <book year=$y><title>$t</title>
} </bib>

В запросе XML-QL шаблоны и фильтры появляются в операторе WHERE, а конструктор - в операторе CONSTRUCT. Результатом внутреннего оператора WHERE является отношение, задающее соответствие переменных кортежам значений, удовлетворяющих отношению. В этом случае результат содержит все пары значений года и заголовка, привязанные к ($y, $t), которые удовлетворяют условию. Результатом полного запроса является один элемент , сконструированный внешним оператором CONSTRUCT. Он содержит один элемент для каждой книги, удовлетворяющей условию оператора WHERE внутреннего запроса, т.е. один для каждой пары ($y, $t).


YATL

make 
  bib [ *book [ @year [ $y ],
                title [ $t ] ] ]
match  www.bn.com/bib.xml  with 
  bib [ *book [ @year [ $y ],
                title [ $t ] ],
                publisher [ name [ $n ] ] ] 
where 
  $n =  Addison-Wesley  and $y > 1991

В запросе YATL конструктор появляется в операторе make, шаблон - в операторе match, а фильтры - в операторе where. Символ * предшествует любому повторяющемуся элементу. Таким образом, шаблон определяет, что элемент bib может иметь множество элементов book, однако каждый элемент book имеет один атрибут year, один элемент publisher и один элемент title. Здесь не требуется никаких вложенных запросов, так как конструкция указывает на наличие одного элемента bib со множеством элементов book, т.е. по одному для каждой пары ($y, $t) в результате. Как и в XML-QL, значение операторов match и where представляет собой отношение, задающее преобразование переменных в кортежи значений, удовлетворяющих условиям.


Lorel

select xml(bib:{
  (select xml(book:{@year:y, title:t})
   from bib.book b, b.title t, b.year y
   where b.publisher =  Addison-Wesley  and y > 1991)})

В запросе Lorel конструктор появляется в операторе select, шаблоны - в операторе from, и одновременно и шаблоны и фильтры появляются в операторе where. В этом запросе bib используется в качестве точки входа для данных XML-документа. Оператор from связывает переменные с идентификаторами элементов, обозначенными представленным шаблоном, а оператор where выбирает элементы, удовлетворяющие фильтрам. Как и в XML-QL и в YATL, значение операторов from и where представляет собой отношение, преобразующее переменные в кортежи значений, удовлетворяющие условиям. Оператор select конструирует новый XML-элемент book с атрибутом year и элементом title.


XQL

document( http://www.bn.com )/bib { 
  book[publisher/name= Addison-Wesley  and @year>1991] {
        @year | title
  }
}

В этом XQL-запросе шаблон document( http://www.bn.com )/bib выбирает из введенного документа все элементы bib верхнего уровня, и оценивает вложенное выражение для каждого такого элемента. Вложенный шаблон book выбирает элементы, являющиеся дочерними для элемента bib и это удовлетворяет условию фильтрации, указанному в скобках. XQL не имеет операторов конструирования. Вместо них результат запроса определяется выражениями шаблона. В этом случае результатом является один элемент bib, содержащий выбранные элементы book; самое внутреннее выражение отражает только атрибут year и элемент title.


2.2. Выравнивание

Следующий запрос не содержит фильтра по издательству и году издания, возвращая набор всех пар title-author. Запрос выравнивает вложенную структуру, и каждая книга порождает одну пару для каждого автора. Следует напомнить, что в XML-QL, YATL и Lorel значением шаблонов и фильтров было отношение, представлявшее собой декартово произведение всех привязок переменных, удовлетворяющих шаблонам и фильтрам. Это оказывает выравнивающее воздействие, которое, как мы увидим ниже, обеспечивает основу для дальнейшей реструктуризации документа.


XML-QL

CONSTRUCT <results> {
  WHERE 
    <bib>
      <book>
        <title>$t</title>
        <author>$a</author>
      </book> 
    </bib> IN  www.bn.com/bib.xml 
  CONSTRUCT
    <result> 
      <title>$t</title>
      <author>$a</author>
    </result>
} </results>

Оператор WHERE создает один кортеж для каждой привязки $t и $a, удовлетворяющей условию шаблона и фильтра. Каждая книга имеет один заголовок и возможно множество авторов, таким образом, существует один кортеж для каждого автора каждой книги. Оператор CONSTRUCT дает один элемент result для каждой пары значений, привязанных к ($a, $t), т.е. свободным переменным конструкции.


YATL

make 
  results [ *result [ title  [ $t ],
                      author [ $a ] ] ]
match  www.bn.com/bib.xml  with 
  bib [ *book [ title [ $t ],
                *author [ $a ] ] ]

Когда все пары заголовков и авторов уникальны, YATL выдает те же элементы result, что и запрос XML-QL. Если в разных книгах встречается один и тот же заголовок и автор, YATL сохраняет такие дубликаты, тогда как XML-QL их игнорирует. Это происходит потому, что YATL имеет семантику bag, которая разрешает дубликаты в промежуточном отношении, а XML-QL имеет семантику set, исключающую дубликаты.


Lorel

select xml(results:
  (select xml(result:{title: t,
                      author: a})
    from bib.book b, b.title t, b.author a))

В этом запросе на языке Lorel оператор from привязывает переменную b к каждой книге во введенном документе. Все пары заголовок-автор для каждой книги привязаны к переменным t и a. В примере новый элемент для каждой пары с тэгом result создан с помощью конструкции xml. Этот результирующий элемент имеет два подэлемента, один для заголовка и один для автора.


XQL

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


2.3. Сохранение структуры

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


XQL

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

document( http://www.bn.com )/bib->results {
    book->result {
        title | author
  }
}

Для каждого элемента book вышеприведенный запрос создает с помощью оператора переименования -> элемент result. Дочерними элементами этого элемента result являются все элементы title и author, содержащиеся в элементе book, с сохранением порядка, предусмотренного документом.


YATL

В языке YATL этот запрос выгляди так:

make 
  results [ *result [ title  [ $t ],
                      $as ] ]
match  www.bn.com/bib.xml  with 
  bib [ *book [ title [ $t ],
                *($as) author ] ]

Этот запрос использует для извлечения заголовка и авторов две переменные, $t и $as$. Благодаря конструкции автора вида *($as), $as привязана скорее к списку всех элементов author в книге, чем к каждому автору.


Lorel

Этот запрос может быть выражен на языке Lorel так:

select xml(results:
  select xml(result:{b.title, b.author})
  from bib.book b)

Выражение шаблона b.author указывает на набор значений для элемента author; аналогично, b.title указывает на набор элементов titles, если их больше одного. Каждая привязка для b создает новый элемент book с набором, в качестве его подэлементов, заголовков и авторов данной книги.


XML-QL

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

CONSTRUCT <results> {
  WHERE
    <bib>
      <book>
        <title>$t</title>
      </book> CONTENT_AS $b
    </bib> IN  www.bn.com/bib.xml 
  CONSTRUCT 
    <result> 
      <title>$t</title>
      {  WHERE <author>$a</author> IN $b
         CONSTRUCT <author>$a</>
      }
    </result>
} </results>

Здесь, CONTENT_AS привязывает переменную b к содержимому элемента book, представляющему собой набор элементов. Внутренний оператор WHERE выбирает элементы author из $b. В XML-QL можно сохранять структуру и без вложенных запросов - с помощью явного задания группировки (см. Раздел 2.5).


2.4. Изменение структуры путем вложения

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


XML-QL

CONSTRUCT <results> {
  WHERE
    <bib>
      <book>
        <author><last>$l</last><first>$f</first></author>
      </book> 
    </bib> IN  www.bn.com/bib.xml 
  CONSTRUCT 
    <result> 
      <author><last>$l</last><first>$f</first></author>
      {
        WHERE 
         <bib>
           <book>
             <title>$t</title>  // join on $l and $f
             <author><last>$l</last><first>$f</first></author>
           </book>
         </bib> IN  www.bn.com/bib.xml 
        CONSTRUCT <title>$t</title>
      }
    </result>
} </results>

В этом запросе XML-QL встречающиеся во внешнем операторе WHERE $l и $f вызывает их привязку, тогда как их появление во внутреннем операторе WHERE проверяет их тождественность. Для каждой фамилии и пары имя-фамилия формируется один элемент результата, содержащий один элемент author и один или более элементов title, создающихся вложенным запросом.


YATL

make 
  results [
    *result [
      author [ last [ $l ], first [ $f ] ],
      ( make
          *title [ $t ]
        match  www.bn.com/bib.xml  with 
          bib [ *book [ *author [ last [ $l ], first [ $f ] ],
                        title [ $t ] ] ] ) ] ]
match  www.bn.com/bib.xml  with 
  bib [ *book [ *author [ last [ $l ], first [ $f ] ] ] ]

Как и XML-QL, YATL использует вложенный запрос для соединения элементов author на основании их фамилий и имен.


Lorel

select xml(results:
  (select xml(result:{author: a, 
                      (select xml(title: t)
                       from bib.book b, b.title t
                       where b.author.first = a.first and 
                             b.author.last = a.last)})
   from bib.book.author a))

Как XML-QL иYATL, Lorel использует вложенный запрос для соединения элементов author на основании их фамилий и имен.


XQL

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

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


2.5. Изменение структуры с помощью явного группирования


Помимо группировки путем вложения, XML-QL, YATL и Lorel обеспечивают другие, в ряде случаев более легкие в использовании, конструкции поддержки группирования. YATL имеет оператор группирования, а XML-QL и Lorel предлагают для это цели функции Skolem. Ниже будет показано, как переписать запрос из предыдущего раздела с использованием эти операторов. Как и ранее, запросы, группирующие каждого автора с заголовками написанных им книг.


YATL

make 
  results [ *($l,$f) result [ author [ last [ $l ],
                                       first [ $f ] ],
                              *title [ $t ] ] ]
match  www.bn.com/bib.xml  with 
  bib [ *book [ title [ $t ],
                *author [ last [ $l ],
                          first [ $f ] ] ] ]

Как и ранее, оператор match дает один кортеж для каждой привязки $t, $l и $f, удовлетворяющей шаблону. Но ранее это приводило к эффекту выравнивания, здесь же результаты снова вложены благодаря группировке по имени и фамилии, как это указано в ($l,$f) между * и result в операторе make. Эта более компактная запись дает тот же результат, что и предыдущий вложенный запрос.


XML-QL

CONSTRUCT <results> {
  WHERE
    <bib>
      <book>
        <title>$t</title>
        <author><last>$l</last><first>$f</first></author>
      </book> 
    </bib> IN  www.bn.com/bib.xml 
  CONSTRUCT 
    <result ID=author($l,$f)> 
      <title>$t</title>
      <author><last>$l</last><first>$f</first></author>
    </result>
} </results>

В XML атрибуты с типом ID уникальным образом идентифицируют содержащие их элементы: только один элемент в документе может иметь атрибут ID с данным значением. В XML-QL идентифицирующий атрибут ID имеет тип ID и используется для контроля группирования. Здесь значением атрибута является author($l,$f), означающее некоторую уникальную функцию фамилии и имени автора, называемую функция Skolem. Все это дает группировку вместе всех отдельных элементов result с одними и теми же фамилиями и именами, и результат представляет собой один отдельный элемент с одним автором и множеством заголовков книг.


Lorel

select Root()->result->Author(l,f),
       Author(l,f)->author->a,
       Author(l,f)->title->t
from bib.book b, b.author a, a.first f, a.last l, b.title t

Синтаксис для функций Skolem в Lorel отражает лежащую в его основе модель данных и представляет собой нечто отличное от представленного в предыдущих запросах. Этот запрос для создания необходимой структуры использует две функции Skolem. Корневая Skolem-функция Root, не имеющая параметров, создает отдельный элемент со множеством подэлементов result. Один подэлемент результат создается Skolem-функцией Author для каждой отдельно идентифицируемой пары привязок l и f. Элементы, созданные Author, имеют подэлементы для авторов и заголовков своих книг.


XQL

XQL не поддерживает оператор явного группирования.


2.6 Объединение источников данных

Теперь видно, как объединить информацию, собранную из различных документов, что необходимо для соединения информации из множества документов. Для следующего запроса допустим, что имеется второй источник данных на www.amazon.com/reviews.xml, содержащий обзоры книг и цены, со следующим DTD:

 <!ELEMENT reviews (entry*)>
 <!ELEMENT entry   (title, price, review)>
 <!ELEMENT title   (#PCDATA)>
 <!ELEMENT price   (#PCDATA)>
 <!ELEMENT review  (#PCDATA)>

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


XML-QL

CONSTRUCT <books-with-prices> {
  WHERE
    <bib>
      <book>
        <title>$t</title>
        <price>$pb</price>
      </book> 
    </bib> IN  www.bn.com/bib.xml ,
    <reviews>
      <entry>
        <title>$t</title>
        <price>$pa</price>
      </entry>
    </reviews> IN  www.amazon.com/reviews.xml 
  CONSTRUCT
    <book-with-prices>
      <title>$t</title>
      <price-amazon>$pa</price-amazon>
      <price-bn>$pb</price-bn>
    </book-with-prices>
} </books-with-prices>

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

Даже если этот оператор объединения может показаться достаточно дорогостоящим, для эффективного выполнения объединений разработано множество различных методов [20].


YATL

make 
  books-with-prices
     *book-with-prices [ title [ $t ],
                         price-amazon [ $pa ],
                         price-bn [ $pb ] ]
match  www.bn.com/bib.xml  with
  bib [ *book [ title [ $t ],
                price [ $pb ] ] ],
       www.amazon.com/reviews.xml  with
  reviews [ *entry [ title [ $t ],
                     price [ $pa ] ] ]

И снова этот запрос почти идентичен такому же в XML-QL.


Lorel

Для соответствующего запроса в Lorel для доступа к данным второго XML-документа будет использоваться точка входа reviews.

select xml(books-with-prices:
  (select xml(book-with-prices: { title: t,
                                  price-amazon: pa,
                                  price-bn: pb }
   from bib.book b, b.title tb, b.price pb,
      reviews.entry e, e.title ta, e.price pa
   where tb = ta)))

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


XQL

XQL-запрос выглядит так:

document( www.bn.com/bib.xml )/bib -> books-with-prices {
  book->book-with-prices[$t:=title] {
    title | price -> price-bn |
    document( www.amazon.com/reviews.xml )/reviews
                                          /entry[title=$t] {
       price -> price-amazon
    }
  }
}

В XQL объединение выполняется с помощью присвоения и использования переменных. Для начала присвоение переменной $t:=title привязывает переменную $t к заголовкам книг, а затем предикат title=$t выбирает соответствующие заголовки в обзорах. Это явное присвоение, сопровождаемое выбором, определяет стратегию выполнения.

Действительно, более симметричный синтаксис других языков сохраняет традицию хорошо известных языков запросов - таких, как SQL и OQL [7], разделяющих семантику запроса и механизм его выполнения.


2.7. Индексация

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


XQL

document( www.bn.com/bib.xml )/bib/book {
        title | author[1 to 2] | author[3]->et-al { }
}

XQL использует для отражения индексов подскрипты. Подскрипт может содержать отдельные номера, области или любую их комбинацию. Например, выражение author[1 to 2] выбирает первых двух авторов. Третий элемент author переименовывается в пустой элемент et-al.


Lorel

select xml(bib:
  (select xml(book:{ title: t, 
                     (select b.author[1-2]), 
                     (select xml(et-al {})
                     where exists b.author[3]) })
   from bib.book b, b.title t))

Lorel использует для формирования результата два вложенных запроса. Первый выбирает авторов с индексами один или два. Второй создает элемент , если существует автор с индексом три.


XML-QL

CONSTRUCT <bib> {
  WHERE 
    <bib>
      <book>
        <title>$t</title>
        <author[$i]>$a</author>
      </book> 
    </bib> IN  www.bn.com/bib.xml , 
  CONSTRUCT
    <book ID=title($t)>
      <title>$t</title> 
      { WHERE $i <= 2 CONSTRUCT <author>$a</author> }
      { WHERE $i = 3 CONSTRUCT <et-al/> }
    </book>
} </bib>

Для этого запроса XML-QL использует индексные переменные. Шаблон связывает три переменные: заголовок $t и автор $a так же, как прежде, а индекс $i привязывается к положению элемента author в списке всех элементов того же уровня . Индексация начинается с нуля и всегда перед элементами author стоит элемент title, при этом первый автор получает индекс один, второй - два, и так далее. Конструкция содержит два вложенных запроса. Первый выбирает авторов с индексом один или два. Второй формирует элемент , если и только если существует автор с индексом три.


YATL

make 
  bib *book [ title [ $t ],
              ( make *author [ $a ]
                match $as with *($$i) author [ $a ]
                where $$i <= 2 ),
              ( make [ et-al ]
                match $as with *($$i) author
                where $$i = 3 ) ]
match  www.bn.com/bib.xml  with
  bib [ *book [ title [ $t ],
                *($as) author ] ]

В YATL индексная переменная обозначается с помощью $$. Сначала выполняется извлечение заголовка и списка авторов в переменные $t и $as соответственно. Оператор make содержит два вложенных запроса: первый возвращает двух авторов, выбирая тех, чей индекс в $$i меньше двух, второй создает элемент et-al,в случае, если существует третий автор.


2.8. Сортировка

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


XML-QL

CONSTRUCT <bib> {
  WHERE 
    <bib>
      <book year=$y>
        <title>$t</title>
        <publisher><name>Addison-Wesley</name></publisher>
      </book> 
    </bib> IN  www.bn.com/bib.xml , 
    $y > 1991
  ORDER-BY $t
  CONSTRUCT
    <book year=$y>
      <title>$t</title> 
    </book>
} </bib>

Этот запрос идентичен запросу из Раздела 2.1, за исключением нового оператора ORDER-BY, определяющего требование сортировки результирующих элементов по заголовкам (в противоположность, скажем, их годам издания).


YATL

make 
  bib [ *o($t) book [ @year [ $y ],
                      title [ $t ] ] ]
match  www.bn.com/bib.xml  with 
  bib [ *book [ @year [ $y ],
                title [ $t ] ],
                publisher [ name [ $n ] ] ]
where 
  $n =  Addison-Wesley  and $y > 1991

Это идентично YATL-запросу из Раздела 2.1, за исключением нового выражения o($t), определяющего требование сортировки результирующих элементов по заголовкам.


Lorel

select xml(bib:
  (select xml(book:{@year:y, title:t})
   from bib.book b, b.title t, b.year y
   where b.publisher =  Addison-Wesley  and y > 1991
   order by t))

Оператор order by сортирует элементы, удовлетворяющие операторам from и where, по заголовкам книг до создания выходного документа оператором select.


XQL

На сегодня XQL не имеет сортирующей конструкции. Однако ряд предложений находится на рассмотрении.

Объединение сортировки и индексации, описанной в предыдущем разделе, может использоваться для формирования списка заголовков в том же порядке, в котором они представлены во введенном документе. В отличие от XQL, всегда сохраняющего порядок элементов документа, упорядочивание в XML-QL, YATL и Lorel носит явный характер. Это сделано специально для сокращения достаточно больших затрат на сортировку.


2.9. Теговые переменные

Так как XML-документ не всегда сопровождается DTD, необходимы какие-либо средства создания запросов к документам в отсутствие предварительных знаний об их структуре или тегах их элементов.

Следующий запрос выбирает книги, в которых некий тэг элемента соответствует регулярному выражению '*or' (например, author, editor, author) и чье значение равно  Suciu . Результат запроса сохраняет исходный тэг.


XML-QL

CONSTRUCT <bib> {
  WHERE 
    <bib>
      <book>
        <title>$t</title>
        <$a>Suciu</>
      </book>
    </bib> IN  www.bn.com/bib.xml ,
    $a LIKE '*or'
  CONSTRUCT 
    <book>
      <title>$t</title>
      <$a>Suciu</>
    </book>
} </bib>

В XML-QL тэговые переменные используются для запроса к структуре документа. Здесь переменная $a привязана к тэгу каждого подэлемента book. Тэг должен соответствовать регулярному выражению '*or'. Конструкция формирует элементы с аналогичными именами тэгов. Заметьте, что выражения элементов, начинающихся с тэговых переменных, закрываются с помощью , поскольку открывающий тэг неизвестен.


YATL

  make
    bib [ * book [ title [ $t ].
                   $$a [  Suciu  ] ] ]
  match  www.bn.com/bib.xml  with
    bib [ * book [ title [ $t ],
                   *$$a [ $l ] ] ]
  where $l =  Suciu  and
        $$a like  *or 

В YATL тэговые переменные обозначаются символом $$.


Lorel

select xml(bib:
  (select xml(book: {title: t, xml(LabelOf(a)): l})
   from bib.book b, b.%or@a l , b.title t
   where l =  Suciu ))

Этот запрос использует переменную пути (path variable) a, привязанную к путям от b до l, соответствующую регулярному выражению %or. Функция LabelOf возвращает строковое представление пути. Переменные пути носят более общий характер, чем тэговые, и могут быть привязаны к произвольному пути в документе.

Тэговые переменные позволяют манипулировать тэгами как значениями. Например, допустим, что оба источника данных содержать информацию о различных типах продукта, например, книгах, дисках и пр. В www.bn.com/bib.xml тип продукта моделируется элементом, а в www.amazon.com/reviews.xml он моделируется значением элемента типа. Использование тэговых переменных позволяет обобщить объединенный запрос из Раздела 2.6 по всем типам элементов, объединяя тэги и значения элементов. В приведенной ниже версии на языке XML-QL $e привязана к тэгу элементов продукта в одном источнике и к значению элемента типа в другом источнике. Формулировки Lorel и YATL совпадают.

CONSTRUCT <items-with-prices> {
  WHERE
    <bib>
      <$e>
        <title>$t</title>
        <price>$pb</price>
      </>
    </bib> IN  www.bn.com/bib.xml ,
    <reviews>
      <entry>
        <title>$t</title>
        <type>$e</type>
        <price>$pa</price>
      </entry>
    </reviews> IN  www.amazon.com/reviews.xml 
  CONSTRUCT
    <$e>
      <title>$t</title>
      <price-amazon>$pa</price-amazon>
      <price-bn>$pb</price-bn>
    </>
} </items-with-prices>

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


XQL

XQL не поддерживает тэговые переменные и поэтому не может формировать запросы такого рода.


2.10. Выражения регулярного пути

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

<!ELEMENT chapter (title, section*)>
 <!ELEMENT section (title, section*)>
 <!ELEMENT title (#PCDATA)>

Элемент section (раздел) может содержать другие вложенные элементы section на произвольной глубине. Выражения регулярного пути используются для сопоставления путей к произвольному уровню глубины. Следующий запрос извлекает все заголовки section или chapter (глава), содержащие слово  XML , вне зависимости от уровня его вложения.


XML-QL

CONSTRUCT <results> { 
  WHERE
    <chapter.(section)*> 
      <title>$t</title>
    </> IN  books.xml ,
  $t LIKE '*XML*'
  CONSTRUCT
    <title>$t</title>
} </results>

Здесь chapter.(section)* представляет собой выражение регулярного пути и соответствует элементу chapter, содержащемому ноль или более элементов section. Выражения регулярного пути формируются с помощью операторов дизъюнкции (|), конкатенации (.) и звездочки Клини (*).


Lorel

select xml(results:
  (select xml(title:t)
   from chapter(.section)* s, s.title t
   where t like  *XML* ))

Компонента выражения пути chapter(.section)* s привязывает переменную s ко всем достижимым элементам с помощью следующих за ней chapter и последовательности элементов section.


XQL

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

document( books.xml )->results {
  chapter[title contains  XML  ] { title } | 
  .//section[title contains  XML  ] { title }
}

YATL

На сегодняшний день YATL не может формировать выражения регулярного пути.

С помощью выражений регулярного пути возможно написать запросы, потенциально дорогостоящие в плане выполнения, например, возвращающие целиком весь документ. Однако существуют методы эффективного выполнения некоторых классов выражений регулярного пути [9], [17].

3. Дополнительные свойства

Авторы полагают, что все примеры, представленные в предыдущих разделах, иллюстрируют важнейшие свойства языка запросов для XML. Далее представлены некоторые другие полезные, но менее критичные особенности.


3.1 Внешние функции и агрегация


Различные прикладные области часто нуждаются в специфических операциях. Например, приложения для поддержки принятия решений требуют функций агрегации, а интегрирующие приложения нуждаются в приближенных сравнениях строковых величин [14].

Например, следующий XML-QL-запрос обращается к прайс-листу, собранному из множества библиографий, и возвращает минимальную цену каждой книги.


XML-QL

CONSTRUCT <results> {
  WHERE <book>
          <title>$t</title>
          <price>$p</price>
        </book> IN  books.yahoo.com/prices.xml 
  CONSTRUCT <minprice ID=title($t)>MIN($p)</minprice>
} </results>

Этот запрос извлекает все пары заголовков и цен, затем группирует цены для одной и той же книги вместе с помощью функции Skolem. И наконец, агрегирующая функция MIN возвращает соответствующую минимальную цену.


YATL

Следующий YATL-запрос вычисляет среднее количество авторов для всех книг.

PRE> make avg([ *count($as) ]) match  www.bn.com/bib.xml  with bib [ * book [ *($as) author ] ]

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


3.2. Обработка альтернатив


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

На YATL это может быть представлено так:


YATL

make
    bib * ( match $b with
               | *($as) author
               make
                   book [ title [ $t ],
                          $as ]
               | * editor [ affiliation [ $af ] ]
               make
                   reference [ title [ $t ],
                               org [ $af ] ] )
  match  www.bn.com/bib.xml  with
    bib [ * book($b) ]

Вложенный запрос соотносит каждую книгу из библиографии с двумя различными шаблонами, разделенными альтернативной конструкцией |. Это аналогично соответствию шаблона в функциональных языках программирования или операторам выбора (case statements) в императивных языках. Если книга соответствует шаблону *($as) author, применяется первый оператор make, хранящий заголовок книги и список ее авторов. Если же она соответствует шаблону * editor [ affiliation [ $af ] ], создается ссылка, содержащая заголовок и организацию.

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


XML-QL

WHERE <bib>
        <book>
          <title>$t</title>
        </book> CONTENT_AS $b
       </bib> in  www.bn.com/bib.xml 
CONSTRUCT <bib> {
  { WHERE     <author>$a</author> in $b
    CONSTRUCT <book ID=Book($t)><title>$t</title>
                                <author>$a</author></book>
  }
  { WHERE     <editor><affiliation>$af</affiliation>
              </editor> in $b
    CONSTRUCT <reference><title>$t</title>
                         <org>$af</org></reference>
  }
} </bib>

3.3. Универсальная квантификация


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

В Lorel это можно реализовать следующим образом:


Lorel

PRE>select xml(original: x, copy: y) from bib.book x, bib.book y where for all z in x.author: exists w in y.author: z = w and for all t in y.author: exists s in x.author: t = s;

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

В YATL можно с той же целью использовать непосредственно установленное тождество:


YATL

make
  * [ original [ $b1 ],
      copy [ $b2 ] ]
match URL with
  *book($b1) { *($a1) author },
      URL with
  *book($b2) { *($a2) author },
where $a1 = $a2

Переменные $a1 и $a2 содержат набор авторов для каждой книги $b1 и $b2. Фильтр $a1 = $a2 проверяет совпадение наборов.

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


3.4. Модели данных и навигация


Теперь представьте небольшое изменение в рассматриваемой базе данных. Для каждого автора будет проставлено не только имя, но и место работы, и адрес электронной почты. Чтобы эта информация не дублировалась, присвоим каждому автору уникальные идентификаторы ID и изменим элементы book таким образом, чтобы они ссылались на авторов по их идентификаторам. Ниже приведен исправленный DTD. (В нем опущены элементы title, editor, publisher, price, first, last, affiliation и e-mail, просто содержащие текст).

 <!ELEMENT bib (book*, person*)>
 <!ELEMENT book (title, publisher, price)>
 <!ATTLIST book year CDATA>
 <!ATTLIST book author IDREFS>
 <!ATTLIST book editor IDREFS>
 <!ELEMENT person (last, first, affiliation?, e-mail?)>
 <!ATTLIST person ID ID>

Теперь author является атрибутом типа IDREFS, относящимся к соответствующим элементам person. Этот пример иллюстрирует возможность представления в XML одних и тех же данных разнообразными способами. Сложное значение может быть представлено непосредственно подэлементом или косвенно, в виде ссылки. Атомарное значение может быть представлено подэелементом или атрибутом. Обычно языки запросов созданы с учетом модели данных, а не их физического представления. Модель данных может использоваться для унификации этих различных представлений. XQL поддерживает документарную модель (document-based model), различающую представления. XML-QL и YATL поддерживают графическую модель данных, унифицирующую встроенные компоненты и ссылки. Lorel поддерживает обе модели и может унифицировать атрибуты и подэлементы. Преимущество унификации моделей данных заключается в возможности составления запросов независимо от лежащего в их основе представления.


Lorel

Например, с помощью графической модели следующий запрос из Раздела 2.2 может использоваться в неизменном виде:

select xml(results:
  (select xml(result:{title: t,
                      author: a}) 
    from bib.book b, b.title t, b.author a))

При этом в случае использования документарной модели запросы должны быть полностью изменены. Модифицированный запрос требует явного объединения для доступа к элементам по ссылкам (access the referenced elements):

select xml(results:
  (select xml(result:{title: t, author: p}) 
    from bib.book b, b.title t, b.author a, bib.person p
    where p.ID = a))

Оператор from привязывает a к атрибуту author, а p - к содержимому элементов person. Оператор where отбирает те person, чей атрибут идентификатора ID равен a, т.е. это есть объединение по bib.book.author и bib.person.ID. Выводимый документ формирует элемент author, содержание которого представляет собой содержимое соответствующего элемента person.


XML-QL

Поскольку XML-QL использует графовую модель, запрос из Раздела 2.2 также применим к заново организованным данным:

CONSTRUCT <results> {
  WHERE 
    <bib>
      <book>
        <title>$t</title>
        <author>$a</author>
      </book> 
    </bib> IN  www.bn.com/bib.xml 
  CONSTRUCT
    <result> 
      <title>$t</title>
      <author>$a</author>
    </result>
} </results>

YATL

make 
  results [ *result [ title  [ $t ] 
                      author [ $a ] ] ]
match  www.bn.com/bib.xml  with 
  bib [ *book [ title [ $t ],
                @author [ *$a ] ] ]

YATL-запрос требует небольшой модификации для доступа к атрибуту author. Переменная $a привязана к элементу по ссылке.


XQL

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

PRE>document( http://www.bn.com )/bib->results { book->result { title | author } }

Несмотря на то, что XQL использует документарную модель, он поддерживает явное связывание - функцию id(), принимающую строку и возвращающую элемент, id которого соответствует данному параметру:

document( www.bn.com/bib.xml )/bib/book {
        title | author/id(@IDREF)
}

4. Вывод

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

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

Несмотря на то, что эта статья акцентирует внимание на выразительной силе и описательных возможностях этих языков, авторы уверены, что эти свойства могут быть эффективно реализованы. Для большинства из наиболее труднореализуемых приведенных здесь свойств опсиано множество хорошо известных методов оптимизации, например, объединения (joins) [20], вложенные запросы (nested queries) [13], выражения пути (path expressions) [9], [17] и функции агрегации (aggregation functions) [8].

Ссылки

[1] S. Abiteboul. Querying semi-structured data. In Proceedings of the International Conference on Database Theory, pages 1--18, Deplhi, Greece, 1997. Springer-Verlag.
http://cosmos.inria.fr:8080/cgi-bin/publisverso?what=abstract&query=103

[2] S. Abiteboul, D. Quass, J. McHugh, J. Widom, and J. Wiener. The Lorel query language for semistructured data. International Journal on Digital Libraries, 1(1):68--88, April 1997.
ftp://db.stanford.edu/pub/papers/lorel96.ps

[3] C. Beeri and T. Milo Schemas for Integration and Translation of Structured and Semi-Structured Data. In Proceedings of the International Conference on Database Theory, Jerusalem, Israel, 1999. Springer Verlag.
ftp://ftp.math.tau.ac.il/pub/milo/icdt99-2.ps.Z

[4] P. Buneman. Tutorial: Semistructured data. In Proceedings of ACM Symposium on Principles of Database Systems, pages 117--121, 1997.
http://www.acm.org/pubs/citations/proceedings/pods/263661/p117-buneman/

[5] P. Buneman, S. Davidson, M. Fernandez, and D. Suciu. Adding structure to unstructured data. In Proceedings of the International Conference on Database Theory, pages 336--350, Deplhi, Greece, 1997. Springer Verlag.
http://www.research.att.com/~mff/files/icdt97.ps.gz

[6] P. Buneman, S. Davidson, G. Hillebrand, and D. Suciu. A query language and optimization techniques for unstructured data. In Proceedings of ACM-SIGMOD International Conference on Management of Data, pages 505--516, 1996.

[7] R. G. Cattell The Object Database Standard: ODMG 2.0. Morgan Kaufmann, 1997.

[8] S. Chaudhuri and K. Shim An Overview of Cost-based Optimization of Queries with Aggregates. In Data Engineering Bulletin 18(3), 1995.
http://www-db-in.research.bell-labs.com/~shim/bulletine95.ps.gz

[9] V. Christophides, S. Cluet and G. Moerkotte Evaluating Queries with Generalized Path Expressions. In Proceedings of ACM-SIGMOD International Conference on Management of Data, 1996.
http://cosmos.inria.fr:8080/cgi-bin/publisverso?what=abstract&query=080

[10] C. L. A. Clarke, G. V. Cormack and F. J. Burkowski An algebra for structured text search and a framework for its implementation. In The Computer Journal, 38(1), 1995.

[11] S. Cluet, C. Delobel, J. Simйon and K. Smaga Your Mediators Need Data Conversion! In Proceedings of ACM-SIGMOD International Conference on Management of Data, 177-188, 1998.
http://cosmos.inria.fr:8080/cgi-bin/publisverso?what=abstract&query=138

[12] S. Cluet, S. Jacqmin and J. Simйon The New YATL: Design and Specifications. Working draft.

[13] S. Cluet and G. Moerkotte Nested Queries in Object Bases In Proceedings of International Workshop on Database Programming Languages, 1993.
http://cosmos.inria.fr:8080/cgi-bin/publisverso?what=abstract&query=064

[14] W. W. Cohen: Integration of Heterogeneous Databases Without Common Domains Using Queries Based on Textual Similarity. In Proceedings of ACM-SIGMOD International Conference on Management of Data, 1998.

[15] A. Deutsch, M. Fernandez, D. Florescu, A. Levy, and D. Suciu. A query language for XML. In International World Wide Web Conference, 1999.
http://www.research.att.com/~mff/files/final.html

[16] M. Fernandez, D. Florescu, J. Kang, A. Levy, and D. Suciu. Catching the boat with Strudel: experience with a web-site management system. In Proceedings of ACM-SIGMOD International Conference on Management of Data, 1998.
http://www.research.att.com/~mff/files/sigmod98.ps.gz

[17] M. Fernandez and D. Suciu Optimizing Regular Path Expressions Using Graph Schemas. In Proceedings of International Conference on Data Engineering, 1998.
http://www.research.att.com/~mff/files/icde98.ps.gz

[18] R. Goldman, J. McHugh, and J. Widom. From semistructured data to XML: Migrating the Lore data model and query language. In Proceedings of the 2nd International Workshop on the Web and Databases (WebDB '99), Philadelphia, Pennsylvania, June 1999.

[19] R. Goldman and J. Widom. DataGuides: enabling query formulation and optimization in semistructured databases. In Proceedings of Very Large Data Bases, pages 436--445, September 1997.

[20] G. Graefe Query Evaluation Techniques for Large Databases. In Computing Surveys 25(2), 1993.

[21] D. Maier. Database Desiderata for an XML Query Language. In W3C Workshop on Query Languages for XML.
http://www.w3.org/TandS/QL/QL98/pp/maier.html

[22] J. McHugh and J. Widom. Query Optimization for XML. In Proceedings of VLDB, Edinburgh, UK, September 1999.
http://www-db.stanford.edu/~mchughj/publications/qo_short.ps