XML (расширяемый язык разметки) стал стандартом для представления данных и обмена данными в веб-приложениях. С быстрым развитием Интернета, особенно с широким использованием электронной коммерции, веб-сервисов и других приложений, данные типа XML стали текущими. основная форма данных. Таким образом, технология управления данными XML, особенно технология запросов к данным XML, стала в настоящее время горячей точкой исследований.
По сравнению с реляционными данными XML имеет ряд преимуществ, но его самым большим недостатком является эффективность. Поскольку в файлах реляционных данных имена полей данных должны появляться только один раз, тогда как в файлах данных XML имена элементов будут появляться неоднократно, что, безусловно, повлияет на эффективность запроса. Чтобы максимально повысить эффективность запросов XML, необходимо предоставить функцию индексации для типа XML.
23 января 2007 года Консорциум Всемирной паутины определил XPath 2.0 и XQuery 1.0 в качестве рекомендуемых стандартов, положив конец предыдущей ситуации, когда различные языки запросов конкурировали за доминирование. На основе этого стандарта, помимо традиционных производителей, различные научно-исследовательские учреждения предложили реализации XPath и XQuery (их в литературе упоминается более десятка), с разными моделями хранения, разными алгоритмами запросов и методами оптимизации. В этом контексте компания Dameng Database Company также предложила свою собственную модель механизма запросов XML, основанную на собственной стратегии развития. В настоящее время механизм запросов XML компании Dameng находится в стадии интенсивной разработки, и создание эффективных индексов для данных XML является важным фактором, влияющим на XML. производительность запроса данных. На основе углубленного анализа технологии индексирования существующих продуктов баз данных для механизма запросов Dameng XML разработана более разумная структура индекса, позволяющая механизму достичь оптимальной производительности.
Введение в технологию индексирования XML
В настоящее время исследования XML в основном разделены на два аспекта. Одна из них — это собственная база данных для хранения, запроса и управления полуструктурированными данными, такими как XML. Данные и метаданные полностью выражены в структурах XML и не имеют ничего общего с базовым форматом хранения данных (таким как объектная модель, реляционная модель). , и т. д.). Другой — взаимное преобразование между ним и реляционной базой данных с использованием зрелой технологии реляционной базы данных для обработки данных XML. Поскольку последнее направление имеет большее практическое значение, оно стало центром исследований XML.
Помимо решений для хранения данных, технология индексирования также является одним из наиболее важных факторов при выборе системы базы данных. Если для документов XML не создается структура индекса, то любой запрос данных XML, скорее всего, приведет к обходу всего дерева документа. Поскольку набор данных XML увеличивается, эти накладные расходы становятся недопустимыми. Таким образом, исследование технологии индексирования XML имеет высокую теоретическую и практическую ценность.
Хотя традиционная технология индексирования стала относительно зрелой после длительного накопления, этот тип технологии индексирования в основном фокусируется на функции поиска записей данных на основе значений (а не шаблонов с определенными взаимосвязями) и не уделяет особого внимания логические связи между записями данных. ;Основной особенностью запроса данных XML является извлечение данных, соответствующих шаблону, на основе входных свойств шаблона (структурных связей, описанных в форме регулярных выражений пути). Таким образом, основное содержимое XML. индексом является разработка технологии, подходящей для сопоставления с образцом.
Классификация индекса XML
Индекс XML на основе пути
Индекс на основе пути основан на информации о пути узлов в древовидной структуре XML и использует определенный метод сокращения, так что сокращенная древовидная структура поддерживает только различную информацию о пути и не существует. Два узла с тот же путь. К таким индексам были предложены: индекс DataGuides, индекс Index Fabric, индекс адаптивного пути для XML-данных (APEX).
Индекс Dataguides представляет собой структурную сводку уточненного пути, начиная с корневого узла. Путь строки, образованный объединением меток ребер, описывается в Dataguides только один раз. Dataguides уменьшают количество узлов, необходимых при обходе запросов пути, и эффективны при прохождении XML-документов от корня. Однако запросы пути, содержащие подстановочные знаки, или запросы пути с осью «потомок или сам», определенной в стандарте XPath, требуют нескольких операций подключения, что приводит к низкой эффективности запросов и избыточности данных.
Затем напишите объектный файл Java TestLob.java об этих двух больших полях и определите типы как поля атрибутов CLOB и BLOB как типы String и byte[] соответственно. Поскольку CLOB — это большой текстовый тип, он соответствует типу String в Java. . BLOB предназначен для обработки некоторых больших файлов, которые не определены строго и хранятся в виде двоичных потоков, поэтому позвольте ему использовать тип byte[], а затем определите методы Getter и Setter для этих двух свойств соответственно. код выглядит следующим образом:
Индекс Dataguides взят из корневого узла. Структурное резюме начального пути уточнения. Путь строки, образованный объединением меток ребер, описывается в Dataguides только один раз. Dataguides уменьшают количество узлов, необходимых при обходе запросов пути, и эффективны при прохождении XML-документов от корня. Однако запросы пути, содержащие подстановочные знаки, или запросы пути с осью «потомок или сам», определенной в стандарте XPath, требуют нескольких операций подключения, что приводит к низкой эффективности запросов и избыточности данных.
Index Fabric — это структура индекса, разработанная на основе дерева Патрисии Три. Она кодирует каждый отмеченный путь к каждому узлу элемента с помощью строки, а затем вставляет эти закодированные значения в дерево Патрисии Три, таким образом преобразуя запрос XML-данных в соответствии с путь к запросу строки. При выполнении запроса сначала закодируйте путь запроса в строковую форму, а затем выполните поиск по нему в дереве индексов. Преимущество индекса Index Fabric заключается в том, что он хранит информацию об иерархической структуре данных XML, единообразно обрабатывает извлечение данных XML со схемой и информацией без схемы, а также сокращает время, необходимое для запроса и обновления данных XML, связанных с иерархией, а не с с длиной индексного ключа связано. Недостаток индекса Index Fabric заключается в том, что он теряет структурные связи между узлами элементов, поскольку сохраняет только информацию об узлах элементов с текстовыми значениями. Таким образом, подобно индексам DataGuides, индексы Index Fabric неэффективны при обработке частично совпадающих выражений запроса с осями «потомок» или «сам», определенными в стандарте XPath.
С этой целью APEX [14] представил информацию, основанную на распределении данных XML. запросы: предварительно сохраните узлы меток, соответствующие часто встречающимся операторам запроса XML, в хэш-структуре. Его функция аналогична функции Cache: когда новый запрос требует обработки, он сначала ищет в хэш-таблице, чтобы увидеть, существует ли удовлетворяющий набор узлов. Но он менее эффективен для выражений запроса со значениями элементов или значениями атрибутов.
Узловой индекс
Узловой индекс по существу разлагает данные XML на набор записей блоков данных и в то же время сохраняет информацию о местоположении блока в данных XML в записи. В отличие от индексов на основе путей, индексы на основе узлов нарушают ограничение, согласно которому узлы должны быть найдены по путям меток, и разлагают данные XML на записи узлов в канонической форме. Поскольку он сохраняет информацию о местоположении узлов и может быть хорошо интегрирован в зрелые системы управления реляционными базами данных, в настоящее время он является наиболее широко используемым индексом.
В соответствии с различными методами кодирования информации о местоположении индексы на основе узлов обычно можно разделить на следующие категории:
1. Индексы на
основе префиксов — это в основном индексы, созданные на основе кодировки Дьюи [12] и кодировки ORDPATH. литературы [13] Принят аналогичный метод и дан метод сжатия ORDPATH, который был применен к организации индексов SQL Server 2005.
Основная идея префиксного кодирования состоит в том, чтобы напрямую использовать кодировку родительского узла узла в качестве префикса кодирования узла. Для префиксного кодирования, чтобы определить, является ли узел v потомком другого узла u, вам нужно только определить. является ли кодирование u префиксом кодирования v. Важным свойством индексов префиксного кодирования является их словарный порядок: для любого узла u в поддереве с корнем в узле r его префиксное кодирование c(u) больше (меньше) его левого сестринского поддерева (правого сестринского поддерева). всех узлов в . Таким образом, индексы на основе префиксов могут не только эффективно поддерживать расчет отношений включения, но также эффективно поддерживать расчет отношений позиции документа.
2. Индекс, основанный на интервальном кодировании.
Для индекса интервального кодирования каждому узлу в дереве Т присваивается интервальный код [начало, конец], который удовлетворяет следующим условиям: интервальный код узла включает в себя интервальный код его узлов-потомков. скажем, узел u в дереве T является предком узла v, если и только если
первая схема интервального кодирования start(u) является кодировкой Дитца, каждому узлу в дереве T присваивается порядковый номер обхода предварительного порядка и Post- Кортеж порядковых номеров обхода порядка. Поскольку узел-предок u в дереве T должен появиться до (после) своего узла-потомка v при обходе в предварительном порядке (обходе после порядка), следовательно, узлы u и v являются отношениями «предок/потомок». , тогда и только тогда, когда pre(u)
Другим типичным примером индекса интервального кодирования является индекс XISS, который присваивает пару чисел каждому узлу, где порядок — это расширенное кодирование предварительного порядка, а размер — потомки области узла. Для любого узла X и Y в дереве документов тогда и только тогда, когда
индекс XISS order(x) разлагает исходный оператор запроса на подвыражения. Затем реализуйте запрос для этих подвыражений соответственно и, наконец, объедините эти промежуточные результаты, чтобы получить набор результатов запроса. Это может улучшить поддержку операторов запроса, содержащих подстановочные знаки. Однако окончательный результат запроса он получает после объединения каждого промежуточного результата. Хотя такой метод действительно может решить все проблемы с подстановочными знаками, объединение таких промежуточных результатов, вероятно, займет очень много времени, особенно для простых выражений с длинными путями.
Сравнение двух механизмов индексирования.
Индексирование на основе путей в основном основано на стратегии слияния узлов. С помощью таких методов, как эквивалентность узлов и эквивалентность путей, получается структура индекса, которая намного меньше исходного документа. Ее структура по-прежнему имеет древовидную форму. , поэтому при обработке запроса вам все равно придется пройти все дерево индексов, чтобы получить результат. Индексы на основе пути могут очень хорошо поддерживать простые запросы выражений пути, но для обычных выражений пути это работает не очень хорошо.
Индекс на основе узлов индексирует каждый узел с помощью технологии кодирования. Структурные отношения между узлами могут быть определены за постоянное время с помощью кодирования. Он может хорошо поддерживать обычные выражения пути, но для выражений длинного пути, особенно при генерации запроса. Когда имеется много промежуточных результатов. операция соединения индекса узла является дорогостоящей.
Индексирование на основе путей и индексирование на основе узлов имеют свои преимущества и недостатки, но они могут дополнять друг друга. В настоящее время в практических приложениях индексация на основе узлов более широко используется, и исследования относительно зрелы. Поэтому исследования компании Dameng по структуре индекса XML в основном сосредоточены на индексации на основе узлов и вносят соответствующие улучшения в отношении индексации на основе путей. .