Рейтинг@Mail.ru
[Войти] [Зарегистрироваться]

Наши друзья и партнеры

UnixForum
купить дешевый 
компьютер родом из Dhgate.com



  • Консультация юриста
  • Запись на консультацию. Комментарии и консультации юристов. Рейтинг юристов
  • reshenie-rf.ru

Lines Club

Ищем достойных соперников.

Библиотека сайта или "Мой Linux Documentation Project"

База с "археологическим" принципом хранения данных

Оригинал: An Archaeology-Inspired Database
Автор: Yoav Rubin
Дата публикации: 20 October 2015
Перевод: Н.Ромоданов
Дата перевода: июль 2016 г.

Объединяем все вместе в виде библиотек

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

Обход по графу

Когда типом атрибута сущности является :db/ref, что означает, что атрибутом является идентификатор другой сущности, то между сущностями создаются связи в виде ссылок. Когда сущность с такой ссылкой добавляется в базу данных, то это ссылка индексируется в индексе VAET.

Информация, содержащаяся в индексе VAET может быть использована для получения всех входящих ссылок, указывающих на сущности. Это делается при помощи функции incoming-refs, которая собирает все листья, доступные из сущности в этом индексе:

(defn incoming-refs [db ts ent-id & ref-names]
   (let [vaet (indx-at db :VAET ts)
         all-attr-map (vaet ent-id)
         filtered-map (if ref-names 
                          (select-keys ref-names all-attr-map) 
                          all-attr-map)]
      (reduce into #{} (vals filtered-map))))

Мы также можем пройтись по всем атрибутам заданной сущности, собрать все значения атрибутов типа :db/ref и, тем самым, извлечь все исходящие ссылки этой сущности. Это делается с помощью функции outgoing-refs.

(defn outgoing-refs [db ts ent-id & ref-names]
   (let [val-filter-fn (if ref-names #(vals (select-keys ref-names %)) vals)]
   (if-not ent-id []
     (->> (entity-at db ts ent-id)
          (:attrs) (val-filter-fn) (filter ref?) (mapcat :value)))))

Эти две функции выступают в качестве основных строительных блоков для любой операции обхода графа, поскольку они являются функциями, которые позволяют перейти от сущностей и атрибутов на более высокий уровень абстракции, представляющий собой узлы и связи в графе. После того, как у нас появилась возможность посмотреть на нашу базу данных в виде графа, мы можем предоставлять различные переходы по базе и выполнение запросов API в виде графа. Как это сделать, мы оставляем это читателю в качестве упражнения; одно из решений можно найти в исходном коде, прилагаемом к настоящей главе (см. graph.clj).

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

Наша модель данных базируется на парадигме накопления фактов (т. е. датомов) в течение продолжительного периода времени. Согласно такой модели, естественный способ найти необходимый язык запросов — это использовать логическое программирование. Обычно используемым языком запросов, в основе которого лежит логическое программирование, является язык Datalog, который, в дополнение к тому, что он хорошо подходит для нашей модели данных, можно очень элегантно адаптировать к синтаксису языка Clojure. В нашем движке запросов будет реализовано подмножество языка Datalog из базы данных Datomic.

Язык запросов

Давайте рассмотрим пример в предлагаемой языке запросов. В этом запросе спрашивается: "Какие имена и дни рождения субъектов (сущностей), которые любят пиццу, говорят по-английски и дни рождения у которых в этом месяце?"

{  :find [?nm ?bd ]
   :where [
      [?e  :likes "pizza"]
      [?e  :name  ?nm] 
      [?e  :speak "English"]
      [?e  :birthday (birthday-this-month? ?bd)]]}

Синтаксис

Мы для записи базового синтаксиса наших запросов используем непосредственно синтаксис литералов данных языка Clojure. Это позволили нам не писать специализированный анализатор, обеспечив при этом тот вид записи, который знаком и хорошо понятен программистам, знакомым с языком Clojure.

Запрос состоит из двух частей:

  • Часть, в которой в качестве ключа используется :where и rule в качестве значения. Правило rule это вектор предложений clause, а предложение является вектором, составленным из трех предикатов predicate, каждый из которых работает с отдельным компонентом датума. В приведенном выше примере [?e :likes "pizza"] является предложением. Элемент :where определяет правило, которое действует как фильтр для датумов в нашей базе данных (точно также, как предложение 'WHERE' в запросе SQL).
  • Часть, в которой в качестве ключа используется :find и вектор в качестве значения. Вектор определяет, какие компоненты, выбранные датумом, должны быть показаны в результатах (точно также, как предложение 'SELECT' в запросе SQL).

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

Мы выполняем оба эти требования с помощью переменных, которые предваряются ведущим символом ?. Единственным исключением из этого определения является переменная "don't care" ("всегда истина"), которая обозначается символом _ (подчеркивание).

Оговорка в запросе состоит из трех предикатов; Таблица 3.2 определяет, что может выступать в качестве предиката в нашем языка запросов.

Таблица 2: Предикаты

НазваниеСмыслПример

Константа

Равно ли значение элемента в датоме константе?

:likes

Переменная

Привязывает значение элемента в датоме к переменной и возвращает значение "истина".

?e

Всегда истина

Всегда возвращает значение "истина".

_

Унарный оператор

Унарная операция, которая в качестве операнда использует переменную. Привязывает значение элемента датума к переменной (если это не '_'). Заменяет переменную значением элемента датума. Возвращает результат применения операции.

(birthday-this-month? _)

Бинарный оператор

Бинарная операция, которая должна в качестве одного из операндов использовать переменную. Привязывает значение элемента датума к переменной (если это не '_'). Заменяет переменную значением элемента датума. Возвращает результат применения операции.

(> ?age 20)

Ограничения нашего языка запросов

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

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

  • Пользователи не могут определять логические операции между предложениями; для них всегда выполняется операция "AND" ("логическое И"). (Это можно обойти, используя унарные или бинарные предикаты).
  • Если в запросе есть более чем одно предложение, то должна быть одна переменная, которая находится во всех предложениях этого запроса. Эта переменная действует как объединяющая переменная. Это ограничение упрощает оптимизатор запросов.
  • Запрос выполняется только для одной базе данных.

Хотя такие проектные решения повлияли на язык запросов, который стал менее богатым, чем язык Datalog, мы все еще можем выполнять большое количество простых, но полезных запросов.

Продолжение статьи смотрите здесь


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

Комментарии отсутствуют