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

Появление языка XML в качестве нового стандарта для представления электронных документов. Применение языка для запросов к БД на основе взаимосвязанных (распределенных по глобальной сети) XML-документов. Синтаксис и семантика конструкций языка XML.

Рубрика Программирование, компьютеры и кибернетика
Вид статья
Язык русский
Дата добавления 17.01.2018
Размер файла 52,5 K

Отправить свою хорошую работу в базу знаний просто. Используйте форму, расположенную ниже

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

Размещено на 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

Фрагмент слабоструктурированной БД изображен на Рис.1.

Часть XML-документа, описывающая ,например, книгу, выглядит как:

<book year=”1995” >

<author><lname>Date</lname></author>

<title>An Introduction to DB Systems</title>

<publisher><name>Addison-Wesley</name></publisher>

</book>

Ниже приведено начало DTD (Document Type Definition)-файла, описывающего схему изображенной выше БД:

<!ELEMENT bib ( book | article )* >

<!ELEMENT book ( author+, title, publisher ) >

<!ATTLIST book year CDATA>

<!ELEMENT author ( fname?, lname ) >

<!ELEMENT publisher ( name , address? ) >

<!ELEMENT name (#PCDATA) >

Вершины графа БД соответствуют элементам XML-документа. Вложенность элементов представляется дугами между соответствующими вершинами, а метка на этой дуге совпадает с именем дескриптора вкладываемого элемента. Если элемент x c дескриптором <D> непосредственно вложен в элемент y, то в XML это обозначается как <D>: x y.

Если элемент x имеет атрибут attr , то адресоваться к его значению можно с помощью выражения x.attr. Если в DTD атрибут для элемента объявлен с ключевым словом ID, то значение этого атрибута рассматривается как уникальное имя (object identifier - OID) данного элемента. Значения атрибутов, объявленных с ключевыми словами IDREF или IDREFS (и называемых атрибутами-ссылками) также рассматриваются как OID'ы. Например, если в DTD атрибут ar объявлен как IDREF, то <D ar = oid1 … > … </D> задает связь (ссылку) с меткой ar от элемента, описываемого данным выражением, к элементу с OID равным oid1. Поэтому в графе отдельного XML-документа могут присутствовать два вида дуг: дуги, определяемые вложенностью элементов, и дуги, задаваемые атрибутами-ссылками. Будем считать, что элемент самого верхнего уровня в XML-документе всегда имеет OID, совпадающий с URL файла, содержащего данный документ.

Синтаксис формул и термов языка XML приводится ниже:

<формула>::= T | F | d1 = d2 | t1 = t2 | d1: t1 t2 | | 1 2 | 1 2 |

d : x t (d, x) | d : x t (d, x) | P ( s1 , … , sn )

Здесь T,F - “истина”, “ложь”, соответственно; d,d1,d2 - либо дескрипторы-константы, либо дескрипторы-переменные; t,t1,t2 - термы; s1,sn - термы-атрибуты; Р - предикат над термами-атрибутами.

<термы>::= <путь> | | { d1 : t1 , , dn : tn } | t | LTC ( t ) | TC ( t )

{ d1 : x | d2 : x t ( d2 , x ) } | { d1 : t' ( x ) | d2 : x t } |

fix q. ( q = q { d1 : x | d2 : x t ( q, d2, x } ) | D ( s, t )

<путь>::= c | x | c.p | x.p | p.r

Здесь с - константа ( OID ), x - переменная, р - путь, r - имя атрибута-ссылки. Более подробно понятие пути объясняется ниже в примерах запросов.

<терм-атрибут> ::= t.a

Здесь t - терм, а - имя атрибута, не являющегося атрибутом-ссылкой.

2. Примеры запросов

Запросы на языке 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


Подобные документы

  • Язык структурированных запросов SQL (Structured Query Language) и его место в сфере доступа к информации в реляционных базах данных. Структура и основные типы данных языка. Синтаксис и семантика главных операторов SQL, последние стандарты языка.

    реферат [98,7 K], добавлен 29.03.2012

  • Работа с хранящейся в базах данных информацией. Язык описания данных и язык манипулирования данными. Распространение стандартизованных языков. Структурированный язык запросов SQL. Язык запросов по образцу QBE. Применение основных операторов языка.

    презентация [76,2 K], добавлен 14.10.2013

  • Обработка распределенных данных и запросов. Многопотоковые и многосерверные архитектуры. Основные типы параллелелизма при обработке запросов. Структура компонентов поддержки удаленного доступа. Доступ к базам данных в двухзвенных моделях клиент-сервер.

    презентация [123,1 K], добавлен 19.08.2013

  • Создание простых и многотабличных запросов с помощью языка запросов SQL. Выполнение запроса с условием отбора. Включение всех столбцов исходной таблицы в результирующую таблицу. Выведение списка платежей с использованием псевдонимов столбцов и таблиц.

    лабораторная работа [183,9 K], добавлен 13.06.2014

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

    доклад [1,9 M], добавлен 12.01.2011

  • Изучение общей структуры языка программирования Delphi: главные и дополнительные составные части среды программирования. Синтаксис и семантика языка программирования Delphi: алфавит языка, элементарные конструкции, переменные, константы и операторы.

    курсовая работа [738,1 K], добавлен 17.05.2010

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

    курсовая работа [1,7 M], добавлен 09.05.2012

  • Объекты модели хранения данных базы данных ORACLE. Взаимосвязь между логическими структурами. Средства манипулирования данными языка SQL, данными языка SQL. Структура выполнения простейших запросов. Формирование критерия отбора. Сортировка данных.

    презентация [120,1 K], добавлен 14.02.2014

  • Изучение особенностей языка структурированных запросов при использовании его в прикладном программировании. Сравнение реализации связи между SQL и языками программирования высокого уровня. Проектирование базы данных и системы управления базами данных.

    курсовая работа [1,5 M], добавлен 25.01.2016

  • Определение понятия гипертекста. Основные части документа SGML. История создания стандартного языка разметки документов HTML. Отличия синтаксиса XHTML от HTML. RSS - семейство XML-форматов для описания лент новостей. Применение языка разметки KML.

    презентация [4,3 M], добавлен 15.02.2014

Работы в архивах красиво оформлены согласно требованиям ВУЗов и содержат рисунки, диаграммы, формулы и т.д.
PPT, PPTX и PDF-файлы представлены только в архивах.
Рекомендуем скачать работу.