Статьи

Связанные списки в Datomic

Январь 18, 2019

Поскольку мой последний контакт с Прологом был более десяти лет назад, я думаю, что пришло время повеселиться с Datomic и Datalog . Чтобы научиться лучше знать Datomic, я попытаюсь реализовать связанные списки как структуру данных Datomic.

Во-первых, мне нужна «схема» базы данных, что в Datomic означает, что мне нужно определить несколько атрибутов. Я определю одно: content / name (в виде строки) для именования элементов моего списка, а также атрибуты самой структуры данных списка, а именно: connectedList / head и: connectedList / tail (оба являются ссылками):

[{:db/id #db/id[:db.part/db], 
  :db/ident :content/name, 
  :db/valueType :db.type/string, 
  :db/cardinality :db.cardinality/one, 
  :db/doc "Simple demo list content.", 
  :db.install/_attribute :db.part/db}
  
 {:db/id #db/id[:db.part/db], 
  :db/ident :linkedList/head, 
  :db/valueType :db.type/ref, 
  :db/cardinality :db.cardinality/one, 
  :db/doc "The head of a linked list.", 
  :db.install/_attribute :db.part/db}
  
 {:db/id #db/id[:db.part/db], 
  :db/ident :linkedList/tail, 
  :db/valueType :db.type/ref, 
  :db/cardinality :db.cardinality/one, 
  :db/doc "The tail of a linked list. Should point to a linked list.", 
  :db.install/_attribute :db.part/db}]

Далее я создам несколько примеров данных. Я определю простой список (A, B, C, D):

[{:db/id #db/id[:db.part/user -1], :content/name "A"}
 {:db/id #db/id[:db.part/user -2], :content/name "B"}
 {:db/id #db/id[:db.part/user -3], :content/name "C"}
 {:db/id #db/id[:db.part/user -4], :content/name "D"}

 {:db/id #db/id[:db.part/user -5], 
  :linkedList/head #db/id[:db.part/user -1], 
  :linkedList/tail #db/id[:db.part/user -6]}
  
 {:db/id #db/id[:db.part/user -6], 
  :linkedList/head #db/id[:db.part/user -2], 
  :linkedList/tail #db/id[:db.part/user -7]}
  
 {:db/id #db/id[:db.part/user -7], 
  :linkedList/head #db/id[:db.part/user -3], 
  :linkedList/tail #db/id[:db.part/user -8]}
  
 {:db/id #db/id[:db.part/user -8], 
  :linkedList/head #db/id[:db.part/user -4]}]

Теперь по некоторым запросам. Давайте сначала немного согреемся.

Поиск всего содержимого (не по списку):

[:find ?n :where [_ :content/name ?n]]

Нахождение главы нашего списка (зная, что начинается с A):

[:find ?h :where [?h :linkedList/head ?c] [?c :content/name \"A\"]]

Далее нам нужно правило, которое определяет, когда два элемента списка связаны между собой. Первое, что приходит на ум, это то, что два предмета связаны, когда один — голова, а другой — (голова) хвоста. Так:

[[[linked ?h ?t] [?h :linkedList/tail ?t]]]

Теперь я могу запросить элемент списка, связанный с A, используя это правило:

[:find ?n :in $ % :where 
  [?c :content/name ?n] 
  [?e :linkedList/head ?c] 
  [linked ?f ?e] 
  [?f :linkedList/head ?a] 
  [?a :content/name \"A\"]]

Это вернет только B, конечно. Чтобы получить весь список, мне понадобится рекурсивное правило. Теперь, как это работает? — Давайте посмотрим:

[[[linked ?h ?t]
    [?h :linkedList/tail ?t]]
 [[linked ?h ?t] 
    [linked ?h ?x]
    [?x :linkedList/tail ?t]]]

Итак, я говорю, что два элемента списка связаны, когда они связаны напрямую или когда существует промежуточный элемент списка, который рекурсивно связан с одним и напрямую связан с другим элементом ввода.

Что происходит, когда я запускаю запрос с новым правилом? — Хм, я получаю B, C и D, но все еще скучаю по самой A.

Как включить A, чтобы получить полный список содержимого? — Мне придется снова продлить правила. Два элемента списка также должны рассматриваться как связанные, если они одинаковы:

[[[linked ?h ?t]
    [?h :linkedList/head]
    [?t :linkedList/head]
    [(= ?h ?t)]]
 [[linked ?h ?t] 
    [linked ?h ?x]
    [?x :linkedList/tail ?t]]]

Эти правила рассматривают два элемента как связанные, когда они оба являются элементами списка (если они имеют атрибут: connectedList / head), и они равны. Или, как указано выше, когда два элемента связаны через промежуточный элемент.

Наконец, я получаю A, B, C и D в результате. Конечно, если я сделаю такой запрос, я не получу заказ. Если мне нужно, чтобы они были заказаны, мне придется просто запрашивать один за другим, самим перебирать список…

Итак, это все для сегодняшних упражнений с пальцами …

По моему скромному мнению, Datomic — лучшая база данных NoSQL, с которой я когда-либо сталкивался . Это дальновидно: я бы очень хотел покончить с изменчивостью (как это делает Datomic) во всех моих текущих проектах с бэкэндами баз данных…

Я также начал небольшой проект по созданию простого в использовании Scala API для Datomic. Однако я еще не уверен, в каком направлении это пойдет. Смотрите здесь .

 

 

 

 

 

 

32
Share: