Самый эффективный и эффективный способ хранения дерева с совместно проиндексированными узлами в XML - PullRequest
Новая
       28

Самый эффективный и эффективный способ хранения дерева с совместно проиндексированными узлами в XML

0 голосов
/ 04 июня 2018

Я подбираю свой старый проект, в котором эффективность и результативность являются ключевыми.У меня есть 100 ГБ данных XML, которые я анализирую.Для каждого дерева XML (их миллионов) используются некоторые атрибуты XML, из которых вычитаются шаблоны.Для этого вопроса, однако, я сильно упросту вещи - но важно помнить, что существует много данных и что важна быстрая обработка и аккуратное хранение результатов в XML.Кроме того, итоговое дерево XML также необходимо будет просмотреть.Фактически, он будет служить пользовательским механизмом индексации, используемым в BaseX , но я вернусь к этому позже.

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

<node letter="X">
  <node letter="A"/>
  <node letter="B"/>
  <node letter="C"/>
  <node letter="D"/>
</node>

Шаблон создается путем взятия всех атрибутов букв детей, их сортировки и объединения.В этом случае шаблон будет ABCD.

. Для каждого дерева также генерируются все возможные поддеревья (порядок не важен, мин. Комбинация 2), т. Е. Все возможные комбинации дочерних элементов иих образцы генерируются.Я не включаю XML деревьев комбинаций, но возможные шаблоны, в дополнение к ABCD, будут, таким образом: 

AB
ABC
ABD
AC
ACD
AD
BC
BCD
BD
CD

В иерархии они выглядят так (обратите внимание на дублирование вконечные узлы).

tree view of patterns

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

С точки зрения запроса, вы можете argue that I am doing a bottom-up look-up. If I am looking for a generalized pattern, e.g. AB, the more specific patterns should also be found because ABis part of ABCD.Поэтому, если бы я искал шаблон AB с данными выше, я бы хотел найти 

ABCD
ABC
ABD

. Может быть, здесь есть два шага.Сначала обобщите на один уровень вверх: AB -> ABC,ABD, а затем ABC->ABCD (и снова ABD->ABDC, но каждый результат должен быть найден только один раз).Промежуточные шаги ABC и ABD также важны для меня, не только конечный результат ABCD.

Проблема, с которой я столкнулся, заключается в том, как с пользой хранить дерево, такое какодин представлен на изображении, так что 1. легко запрашивать способом, который я обсуждал;2. как можно меньше, не теряя узлов;3. Эффективно строить.Последний пункт менее важен для этого вопроса, так как я сам реализую сценарий сборки - что будет сделано в Python 3.6.

Идея, которая у меня была до сих пор, состоит в том, чтобы иметь довольно плоскую структуру, которая работаетпутем «совместного индексирования» непосредственного родительского узла.Это будет выглядеть так: 

<tree>
  <node pattern="AB" index="1">
    <parentnode coindex="7"/> <!-- ABC -->
    <parentnode coindex="8"/> <!-- ABD -->
  </node>
  <node pattern="AC" index="2">
    <parentnode coindex="7"/> <!-- ABC -->
    <parentnode coindex="9"/> <!-- ACD-->
  </node>
  <node pattern="AD" index="3">
    <parentnode coindex="8"/> <!-- ABD -->
    <parentnode coindex="9"/> <!-- ACD -->
  </node>
  <node pattern="BC" index="4">
    <parentnode coindex="7"/> <!-- ABC -->
    <parentnode coindex="10"/> <!-- BCD -->
  </node>
  <node pattern="BD" index="5">    
      <parentnode coindex="8"/> <!-- ABD -->
      <parentnode coindex="10"/> <!-- BCD -->
  </node>
  <node pattern="CD" index="6">    
      <parentnode coindex="9"/> <!-- ACD -->
      <parentnode coindex="10"/> <!-- BCD -->
  </node>
  <node pattern="ABC" index="7">    
    <parentnode coindex="11"/> <!-- ABCD -->
  </node>
  <node pattern="ABD" index="8">    
    <parentnode coindex="11"/> <!-- ABCD -->    
  </node>
  <node pattern="ACD" index="9">   
    <parentnode coindex="11"/> <!-- ABCD -->    
  </node>
  <node pattern="BCD" index="10">    
    <parentnode coindex="11"/> <!-- ABCD -->    
  </node>
  <node pattern="ABCD" index="11" isMain="true"/>
</tree>

Делая это, я думаю, можно получить все шаблоны, которые связаны друг с другом.Например, если бы я сейчас искал AB, я бы надеялся получить к этим узлам дочерние элементы (parentnode), взять эти индексы и использовать их для поиска ближайших родителей.Затем процесс должен повторяться до тех пор, пока не останется ни одного элемента с совмещенным индексом (например, ABCD в этом случае)

Представьте, что есть тысячи таких элементов XML, и что основные из них обозначены isMain.Обратите внимание, что isMain не обязательно является шаблоном, который не имеет дочерних узлов!Результатом является накопление всех оригинальных деревьев XML.Это означает, что в некоторых случаях шаблон может быть основным, в то время как в других он может быть частью комбинаций.В таких случаях node - это , обозначенное isMain, потому что в исходном XML есть «некое дерево, которое имеет этот шаблон в качестве своего основного шаблона».

Пока это только моя идея, но я не уверен, есть ли лучший способ или, что более важно, легко ли это сделать в BaseX.В основном с заданным входным значением AB я хочу получить все соответствующие pattern s (ABC, ABD, ABCD), используя индексы, а затем отфильтровать эти результаты, получив только те из них, где isMain="true".Я с нетерпением жду, чтобы увидеть лучшие идеи и способы их запроса в BaseX.Если моя идея хорошая, то я хотел бы увидеть хороший способ зафиксировать запрос в одном выражении xquery.

1 Ответ

0 голосов
/ 29 июня 2018

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

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

Таким образом, вы просто используете иерархическую структуру как есть, например: 

<tree>
    <node pattern="ABCD">
      <node pattern="ABC">
        <node pattern="AB"/>
        <node pattern="AC"/>
        <node pattern="BC"/>
      </node>
      <node pattern="ABD">
        <node pattern="AB"/>
        <node pattern="AD"/>
        <node pattern="BD"/>
      </node>
    </node>
</tree>

Так что, я думаю, вы выбрали этот формат по причинам производительности.Но когда вы строите свою базу данных, вы должны создать индекс атрибута, т.е. все ваши значения атрибута будут проиндексированы.Обычно для более обычных запросов его следует переписать, но вы можете напрямую использовать индекс атрибута.Например, у меня есть база данных объемом более 50 ГБ, содержащая дамп английской википедии.Например, я выбираю поиск страницы List of Dragon Ball characters: 

db:attribute("wikipedia", "List of Dragon Ball characters")/parent::*

Это заняло примерно 20 мсек, чтобы выполнить на моем компьютере.

Таким же образом, вы можете просто найти шаблон и перейтивверх по вашему дереву: 

db:attribute("<YOUR_DB>", "AB")/ancestor::node/@pattern => distinct-values()

Учитывая, что вы сначала используете индекс, а затем просто идете к родителям, это должно быть так же быстро, как он получает.

...