XML - язык запросов к базам данных на основе XML-документов

Размещено на http://www.allbest.ru/

XML - язык запросов к базам данных на основе xml-документов

Юрий Сердюк

Переславль-Залесский, ИПС РАН

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

Введение

Появление языка XML в качестве нового стандарта для представления электронных документов усилило внимание к изучению новой модели баз данных (БД) - слабоструктурированным данным. Еще большую актуальность этой модели придает то, что язык XML продвигается крупнейшими производителями компьютерных систем и программ (Microsoft, IBM, Oracle, Sun и др.) в качестве единого языка электронной коммерции (e-commerce). В частности, подавляющее большинство разработок в области слабоструктурированных БД сразу же мигрировало в сторону XML ( см., например, [Goldman et al.,1999; Deutsch et al., 1999; Abiteboul et al., 1999] ).

Язык XML вызвал большой поток теоретических и практических работ, связанных с исследованиями различных его аспектов. Достаточно только отметить таких теоретиков с мировым именем как J. Ullman, S.Abiteboul, V. Vianu и др. Центром их исследований стали языки запросов к XML-данным. Среди них можно назвать такие языки как Lorel [Goldman et al.,1999], XML-QL [Deutsch et al., 1999], XQL [Robie et al., 1998] и др. В основу всех этих языков заложена идея использования «регулярных путей» для навигации по БД со сложной структурой, представляемой обычно в виде графа. В работах [Sazonov,1993; Sazonov,1995] была показана возможность кодирования множеств в виде графов и развита соответствующая теория вычислимости. В частности, был предложен язык в качестве языка запросов к сложноустроенным (например, по типу Web) БД. Важная отличительная черта этого языка состоит в том, что все определимые в нем запросы являются эффективно (а именно, полиномиально) вычислимыми. Некоторые теоретические вопросы, связанные с применением языка для запросов к WWW, а также соответствующая экспериментальная реализация, представлены в [Serdyuk, 1999; Сазонов и др., 1999].

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

синтаксис семантика язык запрос

1. Язык запросов XML

Запросы на языке XML имеют общий вид

d : t

где d - дескриптор-константа, t - терм. Результатом выполнения запроса является новый XML-документ с заглавным дескриптором d и содержанием, определяемым значением терма t.

Конструкция { d1 : t1 , , dn : tn }языка XML создает новый элемент, подэлементами которого являются значения термов t1, tn c соответствующими дескрипторами d1, , dn.

Конструкция { d1 : x | d2 : x t ( d2, x ) } ( тождественно истинная может опускаться ) выбирает из элемента, определяемого термом t, те (непосредственно) вложенные в него подэлементы с дескриптором d2, которые удовлетворяют условию ( d2, x ). У выбранных подэлементов дескриптором становится d1.

Приводимые ниже запросы относятся к библиографической БД (Рис.1), которая считается хранящейся в файле bib.xml.

Запрос 1. Переструктурировать исходную базу данных, сгруппировав книги и статьи в отдельные объекты базы данных.

<newbib>: {<books> : { <book>: x | <book>: x “bib.xml” } ,

<articles> : { <article> : x | <article> : x “bib.xml” } }

Запрос 2. Найти все книги, выпущенные в издательстве Addison-Wesley.

<AW-books> : { <book> : x | <book> : x “bib.xml” &

( <publisher> : y x <name> : “Addison-Wesley” y )}

Пусть результат этого запроса сохранен в файле AW-books.xml .

Конструкция t формально есть теоретико-множественная операция объединения, “достающая” элементы элементов множества (документа) t .

Запрос 3. Перечислить авторов всех книг, выпущенных в издательстве Addison-Wesley после 1995 года:

<authors> : { <author> : x | <author> : x

{ <book> : y | <book> : y “AW-books.xml” & y.year > 1995 } }

Конструкция LTC ( t ) дает множество всех элементов , принадлежащих (на любом уровне вложенности) документу t.

Запрос 4. Перечислить фамилии авторов публикаций, хранящихся в БД.

<author's-lnames> : { <lname> : x | <lname> : x LTC ( “bib.xml” ) }

В запросах, приводимых далее, показано использование атрибутов-ссылок. Иллюстративные фрагменты схемы БД и самой БД personnel.xml с атрибутами-ссылками показаны ниже :

<!ELEMENT personnel (person)+ >

<!ELEMENT person (name, email*) >

<!ATTLIST person id ID #REQUIRED

manager IDREF #IMPLIED

subordinates IDREFS #IMPLIED >

<!ELEMENT name ( family, given ) >

<!ELEMENT family (#PCDATA) >

<!ELEMENT given (#PCDATA)>

…

<personnel>

<person id =“H.MARUYAMA” subordinates =“N.URAMOTO K.TAMURA” >

<name> <family>MARUYAMA</family>

<given>Hiroshi</given>

</name>

<email>maruyama@jp.ibm.com</email>

</person>

<person id =“N.URAMOTO” manager = “H.MARUYAMA” >

…

<email>uramoto@jp.ibm.com</email>

</person>

…

<personnel>

Запрос 5. Найти всех служащих, у которых менеджером является H.MARUYAMA.

<H.MARUYAMA_subordinates> :

{ <person> : x | <person> : x “personnel.xml” & x.manager=“H.MARUYAMA”}

Запрос 6. Перечислить электронные адреса всех менеджеров.

<manager's-emails> : { <email> : x | <email> : x

{ <person> : x | <person> : x “personnel.xml” &

( <person> : y “personnel.xml” y.manager = x ) } }

Запрос 7. ( Проверка ограничения целостности ).

Найти всех таких служащих, у которых есть менеджеры, среди подчиненных которых данный служащий не числится.

<incorr-subordination> : { <person> : x | <person> : x “personnel.xml” &

( <person> : y “personnel.xml” ( x.manager = y & ( x y.subordinates ) ) ) }

Рекурсия в языке XML реализуется через оператор расширяющей неподвижной точки fix q. ( q = q { d1 : x | d2 : x t & ( q, d2, x ) } ), задающий решение уравнения q=q{d1: x|} путем стабилизации рекурсивной последовательности множеств q0,q1,q2, , где q0 = , и qi+1=qi{ d1 : x | d2 : x t & ( qi, d2, x ) }.

Запрос 8. Найти всех таких служащих, которые непосредственно или косвенно подчиняются H.MARUYAMA.

<all-whose-H.MARUYAMA-subordinates> :

fix q. ( q = q { <person> : x | <person> : x “personnel.xml” &

( ( x “H.MARUYAMA”.subordinates )

( <person> : y q x y.subordinates ) ) } )

В языке XML возможны запросы сразу к нескольким XML-документам, взаимосвязанным друг с другом через простые ссылки, записанные на языке XLink [XLink,1999]. Т.е., например, если основная библиографическая БД связана со вспомогательной БД простой ссылкой, то в DTD основной БД должна быть запись

<!ATTLIST bib xlink:type CDATA #FIXED “simple”

xlink:href CDATA #REQUIRED

xlink:title CDATA #IMPLIED >,

которой соответствует такая, например, запись в XML-файле:

<bib xml:link = “simple” xml:href = “bib2.xml” xml:title = “bib2”>

В свою очередь, БД bib2.xml может аналогичным образом ссылаться на bib3.xml ( или снова на bib.xml ) и т.д. Тогда пути “bib.xml”.“bib2”.“bib3” и “bib2.xml”.“bib3” указывают на БД bib3.xml из баз данных bib.xml и bib2.xml , соответственно. В общем случае, цепочка глобальных ссылок выглядит как

<OID>.<title1>. … <title n>

Запрос 9. Отыскать во вспомогательной БД bib2 (т.е., мы предполагаем, что мы знаем имя БД, но не знаем ее физического расположения) книги, автор которых Abiteboul.

<Abiteboul's-books> : { <book> : x | <book> : x “bib.xml”.“bib2” &

( <author> : a x <lname> : “Abiteboul” a ) }

Конструкция TC ( t ) дает множество всех элементов, которые принадлежат либо документу t, либо некоторому достижимому из него по глобальным ссылкам документу.

Запрос 10. Отыскать книги издательства Addison-Wesley во всех файлах распределенной базы данных.

<all-AW-books> : { <book> : b | <book>: b TC ( “bib.xml” ) &

( <publisher> : p b <name> : “Addison-Wesley” p ) }

Конструкция { d1 : t' ( x ) | d2 : x t } позволяет строить образы элементов x, входящих в t с дескриптором d2 , согласно конструкции t' ( x ), снабжая их дескриптором d1.

Запрос 11. Для каждой статьи, хранящейся в БД, отыскать ее название и год издания.

<title_year_pairs> : {<article>: {<Fst> : { <title> : y | <title> : y x }

<Snd> : { <year> : z | <year> : z x } } |<article>: x “bib.xml”}

Конструкция D ( s, t ) есть оператор декорации из нефундированной теории множеств. Он по “горизонтальному” представлению множества (а именно, в виде совокупности пар <d> : (x,y), соответствующих принадлежности <d> : x y ) и выделенному элементу одной из этих пар, строит обычное (вложенное) представление множества. Например, D({<d1>:(x,y),<d2>:(y,z)},z)= { <d2> : { <d1> : x } }. Мы не приводим здесь пример запроса, в котором используется этот оператор, а заметим только, что если “горизонтально” представленное множество действительно является нефундированным, то его вложенное представление (уже как XML- документ) будет иметь атрибуты.

Литература

Abiteboul et al.,1999 S. Abiteboul et al. XML Repository and Active Views Demonstration. - Proceedings of the VLDB Conference, Edinburg, September, 1999.

Deutsch et al.,1999 A. Deutsch, M. Fernandez, D. Floresku, A. Levy, D. Suciu. XML-QL : A query language for XML. - Proceedings of the WWW8 Conference, 1999.

Goldman et al.,1999 R. Goldman, J. McHugh, J. Widom. From semistructured data to XML: migrating the Lore data model and query language - Proceedings of the 2nd International Workshop on the Web and Databases ( WebDB'99), Philadelphia, June 1999.

Robie et al., 1998 J. Robie, J. Lapp, D. Schach. XML query language (XQL) . - The W3C Query Languages Workshop , Boston, December 3-4, 1998.

Sazonov, 1993 Sazonov V. Yu. Hereditarily-finite sets, data bases and polynomial-time computability. - Theoretical Computer Science, 1993, v. 119, pp. 187 - 214.

Sazonov, 1995 Sazonov V. Yu. A bounded set theory with anti-foundation axiom and inductive definability. - Lecture Notes in Computer Science, 1995, v. 933, pp. 527 - 541.

XLink, 1999 XML Linking Language (XLink). W3C Working Draft, July 1999.

Сазонов и др.,1999 Сазонов В.Ю., Сердюк Ю.П. Экспериментальная реализация теоретико- множественного языка запросов Дельта к базам данных типа Web. - Программные системы: Теоретические основы и приложения. М., Наука, Физматлит, 1999, стр. 185 - 192.

Размещено на Allbest.ur