Yoav Rubin是微软的高级软件工程师，在此之前是IBM研究院的研究员和首席发明家。他目前从事云数据安全领域的工作，过去他的工作重点是开发基于云或Web的开发环境。Yoav拥有神经科学领域的医学研究硕士学位和信息系统工程学士学位。他在Twitter上使用@yoavrubin，偶尔会在http://yoavrubin.blogspot.com上发表博客。
软件开发通常被视为一个严格的过程，其中输入是需求，输出是可工作的产品。然而，软件开发人员是人，他们有自己的视角和偏见，这些都会影响其工作成果。
在本章中，我们将探讨常见视角的变化如何影响一个经过充分研究的软件类型——数据库的设计和实现。
数据库系统旨在存储和查询数据。这是所有信息工作者都在做的事情；然而，系统本身是由计算机科学家设计的。因此，现代数据库系统受到计算机科学家对数据是什么以及可以用它做什么的定义的极大影响。
例如，大多数现代数据库通过就地覆盖旧数据来实现更新，而不是追加新数据并保留旧数据。这种机制被Rich Hickey称为“面向位置编程”，它节省了存储空间，但无法检索特定记录的完整历史记录。这种设计决策反映了计算机科学家的观点，即“历史”不如其存储成本重要。
如果你问一个考古学家旧数据在哪里可以找到，答案可能是“希望它就埋在下面”。
（免责声明：我对典型考古学家观点的理解基于参观了一些博物馆，阅读了几篇维基百科文章，以及观看了整个《夺宝奇兵》系列。）
如果我们请我们友好的考古学家设计一个数据库，我们可能会期望需求反映在挖掘现场发现的东西。
例如，一堵墙在一层上可能刻有罗马符号，而在更低的一层上可能刻有希腊符号。这两项观察结果都记录为墙的状态的一部分。
这个类比在图10.1中进行了可视化。
图10.1 - 挖掘现场
如果我们将考古学家的语言翻译成数据库设计人员使用的术语
这可能与您习惯使用的数据库类型看起来非常不同。这种设计有时被称为“函数式数据库”，因为它使用了函数式编程领域的想法。本章的其余部分描述了如何实现这样的数据库。
由于我们正在构建一个函数式数据库，因此我们将使用一种名为Clojure的函数式编程语言。
Clojure具有几个使其成为函数式数据库良好实现语言的特性，例如开箱即用的不可变性、高阶函数和元编程功能。但最终，选择Clojure的原因是它强调简洁、严格的设计，而很少有编程语言具备这种特性。
让我们从声明构成我们数据库的核心结构开始。
(defrecord Database [layers top-id curr-time])一个数据库包含
(defrecord Layer [storage VAET AVET VEAT EAVT])每一层包含
在我们的设计中，单个概念上的“数据库”可能包含许多Database实例，每个实例代表数据库在curr-time时的快照。如果实体的状态在它们所代表的时间之间没有发生变化，则一个Layer可以与另一个Layer共享完全相同的实体。
我们的数据库如果没有要存储的实体将毫无用处，因此我们接下来定义它们。如前所述，实体具有ID和属性列表；我们使用make-entity函数创建它们。
(defrecord Entity [id attrs])
(defn make-entity
([] (make-entity :db/no-id-yet))
([id] (Entity. id {})))请注意，如果没有给出ID，则实体的ID将设置为:db/no-id-yet，这意味着其他东西负责为其提供ID。我们稍后将了解它是如何工作的。
每个属性都包含其名称、值以及其最近更新的日期戳以及之前的日期戳。每个属性还有两个字段描述其type和cardinality。
如果某个属性用于表示与另一个实体的关系，则其type将为:db/ref，其值将为相关实体的ID。这个简单的类型系统也充当扩展点。用户可以自由定义自己的类型并利用它们为其数据提供额外的语义。
属性的cardinality指定属性表示单个值还是一组值。我们使用此字段来确定允许对该属性执行的操作集。
使用make-attr函数创建属性。
(defrecord Attr [name value ts prev-ts])
(defn make-attr
([name value type ; these ones are required
& {:keys [cardinality] :or {cardinality :db/single}} ]
{:pre [(contains? #{:db/single :db/multiple} cardinality)]}
(with-meta (Attr. name value -1 -1) {:type type :cardinality cardinality})))此构造函数中使用了一些有趣的模式
:db/single的默认值。with-meta（用于设置）和meta（用于读取）完成的。属性只有作为实体的一部分才有意义。我们使用add-attr函数建立这种连接，该函数将给定属性添加到实体的属性映射（称为:attrs）中。
请注意，我们首先将其转换为关键字以遵守Clojure对映射的惯用用法，而不是直接使用属性的名称。
(defn add-attr [ent attr]
(let [attr-id (keyword (:name attr))]
(assoc-in ent [:attrs attr-id] attr)))到目前为止，我们已经讨论了很多关于我们要存储什么，而没有考虑我们要存储在哪里。在本章中，我们采用最简单的存储机制：将数据存储在内存中。这当然不可靠，但它简化了开发和调试，并使我们能够专注于程序更有趣的部分。
我们将通过一个简单的协议访问存储，这将使数据库所有者能够定义其他存储提供程序以供选择。
(defprotocol Storage
(get-entity [storage e-id] )
(write-entity [storage entity])
(drop-entity [storage entity]))这是我们对协议的内存实现，它使用映射作为存储
(defrecord InMemory [] Storage
(get-entity [storage e-id] (e-id storage))
(write-entity [storage entity] (assoc storage (:id entity) entity))
(drop-entity [storage entity] (dissoc storage (:id entity))))现在我们已经定义了数据库的基本元素，我们可以开始考虑如何查询它了。根据我们数据结构的方式，任何查询必然至少对实体的ID以及其某些属性的名称和值感兴趣。(entity-id, attribute-name, attribute-value)这三个要素对我们的查询过程非常重要，因此我们为它赋予了一个明确的名称：datom。
Datom很重要，因为它们表示事实，而我们的数据库积累事实。
如果您以前使用过数据库系统，您可能已经熟悉索引的概念，索引是一种支持性数据结构，它消耗额外的空间以减少平均查询时间。在我们的数据库中，索引是一个三级结构，它以特定顺序存储datom的组件。每个索引的名称都源自它存储datom组件的顺序。
例如，让我们看一下图10.2中概述的索引。
此索引命名为EAVT，因为顶层映射保存实体ID，第二层保存属性名称，叶子保存值。“T”来自数据库中的每一层都有自己的索引，因此索引本身与特定的时间相关。
图10.2 - EAVT
图10.3显示了一个将被称为AVET的索引，因为
图10.3 - AVET
我们的索引实现为映射的映射，其中根映射的键充当第一层，每个此类键都指向一个映射，其键充当索引的第二层，值是索引的第三层。第三层中的每个元素都是一个集合，保存索引的叶子。
每个索引都将datom的组件存储为其规范“EAV”排序（entity_id、attribute-name、attribute-value）的某种排列。但是，当我们在索引外部使用datom时，我们希望它们采用规范格式。因此，我们为每个索引提供了函数from-eav和to-eav，用于在这些排序之间进行转换。
在大多数数据库系统中，索引是一个可选组件；例如，在PostgreSQL或MySQL等RDBMS（关系数据库管理系统）中，您将选择仅向表中的某些列添加索引。我们为每个索引提供了一个usage-pred函数，该函数确定是否应将属性包含在此索引中。
(defn make-index [from-eav to-eav usage-pred]
(with-meta {} {:from-eav from-eav :to-eav to-eav :usage-pred usage-pred}))
(defn from-eav [index] (:from-eav (meta index)))
(defn to-eav [index] (:to-eav (meta index)))
(defn usage-pred [index] (:usage-pred (meta index)))我们的数据库中有四个索引：EAVT（参见图 10.2）、AVET（参见图 10.3）、VEAT 和 VAET。我们可以通过indexes函数返回的值向量来访问这些索引。
(defn indexes[] [:VAET :AVET :VEAT :EAVT])为了演示这一切是如何组合在一起的，表 10.1 可视化了对以下五个实体进行索引的结果。
| EAVT 索引 | AVET 索引 |
|
|
| VEAT 索引 | VAET 索引 |
|
|
: **表 10.1** - 索引
现在我们拥有了构建数据库所需的所有组件。初始化我们的数据库意味着
top-id和curr-time设置为 0(defn ref? [attr] (= :db/ref (:type (meta attr))))
(defn always[& more] true)
(defn make-db []
(atom
(Database. [(Layer.
(fdb.storage.InMemory.) ; storage
(make-index #(vector %3 %2 %1) #(vector %3 %2 %1) #(ref? %));VAET
(make-index #(vector %2 %3 %1) #(vector %3 %1 %2) always);AVET
(make-index #(vector %3 %1 %2) #(vector %2 %3 %1) always);VEAT
(make-index #(vector %1 %2 %3) #(vector %1 %2 %3) always);EAVT
)] 0 0)))不过，这里有一个问题：Clojure 中的所有集合都是不可变的。由于写操作在数据库中非常关键，因此我们将我们的结构定义为一个Atom，这是一种提供原子写功能的 Clojure 引用类型。
您可能想知道为什么我们对 AVET、VEAT 和 EAVT 索引使用always函数，而对 VAET 索引使用ref?谓词。这是因为这些索引用于不同的场景，我们将在稍后深入探讨查询时看到这一点。
在我们为数据库构建复杂的查询功能之前，我们需要提供一个较低级别的 API，系统中的不同部分可以使用它来根据其关联的标识符从任何时间点检索我们构建的组件。数据库的使用者也可以使用此 API；但是，他们更有可能使用构建在其之上的功能更完善的组件。
此较低级别的 API 由以下四个访问器函数组成
(defn entity-at
([db ent-id] (entity-at db (:curr-time db) ent-id))
([db ts ent-id] (get-entity (get-in db [:layers ts :storage]) ent-id)))
(defn attr-at
([db ent-id attr-name] (attr-at db ent-id attr-name (:curr-time db)))
([db ent-id attr-name ts] (get-in (entity-at db ts ent-id) [:attrs attr-name])))
(defn value-of-at
([db ent-id attr-name] (:value (attr-at db ent-id attr-name)))
([db ent-id attr-name ts] (:value (attr-at db ent-id attr-name ts))))
(defn indx-at
([db kind] (indx-at db kind (:curr-time db)))
([db kind ts] (kind ((:layers db) ts))))由于我们将数据库视为任何其他值，因此这些函数中的每一个都将数据库作为参数。每个元素都由其关联的标识符检索，并可选地检索感兴趣的时间戳。此时间戳用于查找应将我们的查找应用到的相应层。
基本访问器的第一个用法是提供“读取过去”的 API。这是可能的，因为在我们的数据库中，更新操作是通过追加新层（而不是覆盖）来完成的。因此，我们可以使用prev-ts属性查看该层上的属性，并继续深入历史记录以观察属性的值如何随着时间的推移而演变。
函数evolution-of正是这样做的。它返回一系列对，每一对都包含属性更新的时间戳和值。
(defn evolution-of [db ent-id attr-name]
(loop [res [] ts (:curr-time db)]
(if (= -1 ts) (reverse res)
(let [attr (attr-at db ent-id attr-name ts)]
(recur (conj res {(:ts attr) (:value attr)}) (:prev-ts attr))))))到目前为止，我们的讨论重点关注数据的结构：核心组件是什么以及它们是如何聚合在一起的。现在是时候探索我们系统的动态：数据如何通过添加-更新-删除数据生命周期随着时间的推移而发生变化。
正如我们已经讨论过的，在考古学家的世界里，数据实际上永远不会改变。一旦创建，它就会永远存在，并且只能通过较新层中的数据来隐藏在世界之外。“隐藏”一词在这里至关重要。旧数据不会“消失”——它被掩埋了，可以通过暴露旧层再次揭示出来。相反，更新数据意味着通过在其顶部添加一个包含其他内容的新层来隐藏旧数据。因此，我们可以通过在数据顶部添加“空”层来“删除”数据。
这意味着当我们谈论数据生命周期时，我们实际上是在谈论随着时间的推移向数据添加层。
数据生命周期包括三个基本操作
add-entity函数添加实体remove-entity函数删除实体update-entity函数更新实体请记住，即使这些函数提供了可变性的错觉，但在每种情况下我们真正做的只是向数据添加另一层。此外，由于我们使用的是 Clojure 的持久数据结构，因此从调用者的角度来看，我们为这些操作支付的价格与“就地”更改相同（即可忽略不计的性能开销），同时为数据结构的所有其他用户保持不变性。
添加实体需要我们做三件事
这些步骤在add-entity函数中执行。
(defn add-entity [db ent]
(let [[fixed-ent next-top-id] (fix-new-entity db ent)
layer-with-updated-storage (update-in
(last (:layers db)) [:storage] write-entity fixed-ent)
add-fn (partial add-entity-to-index fixed-ent)
new-layer (reduce add-fn layer-with-updated-storage (indexes))]
(assoc db :layers (conj (:layers db) new-layer) :top-id next-top-id)))准备实体是通过调用fix-new-entity函数及其辅助函数next-id、next-ts和update-creation-ts来完成的。后两个辅助函数负责查找数据库的下一个时间戳（由next-ts完成）以及更新给定实体的创建时间戳（由update-creation-ts完成）。更新实体的创建时间戳意味着遍历实体的属性并更新其:ts字段。
(defn- next-ts [db] (inc (:curr-time db)))
(defn- update-creation-ts [ent ts-val]
(reduce #(assoc-in %1 [:attrs %2 :ts ] ts-val) ent (keys (:attrs ent))))
(defn- next-id [db ent]
(let [top-id (:top-id db)
ent-id (:id ent)
increased-id (inc top-id)]
(if (= ent-id :db/no-id-yet)
[(keyword (str increased-id)) increased-id]
[ent-id top-id])))
(defn- fix-new-entity [db ent]
(let [[ent-id next-top-id] (next-id db ent)
new-ts (next-ts db)]
[(update-creation-ts (assoc ent :id ent-id) new-ts) next-top-id]))要将实体添加到存储中，我们找到数据库中最新的层，并使用新层更新该层中的存储，其结果存储在layer-with-updated-storage中。
最后，我们必须更新索引。这意味着，对于每个索引（由reduce与add-entity函数中partial化的add-entity-to-index的组合完成）
filter与在add-entity-to-index中对属性进行操作的索引的usage-pred的组合）update-attr-in-index函数中partial化的update-entry-in-index与from-eav的组合）update-entry-in-index函数）(defn- add-entity-to-index [ent layer ind-name]
(let [ent-id (:id ent)
index (ind-name layer)
all-attrs (vals (:attrs ent))
relevant-attrs (filter #((usage-pred index) %) all-attrs)
add-in-index-fn (fn [ind attr]
(update-attr-in-index ind ent-id (:name attr)
(:value attr)
:db/add))]
(assoc layer ind-name (reduce add-in-index-fn index relevant-attrs))))
(defn- update-attr-in-index [index ent-id attr-name target-val operation]
(let [colled-target-val (collify target-val)
update-entry-fn (fn [ind vl]
(update-entry-in-index
ind
((from-eav index) ent-id attr-name vl)
operation))]
(reduce update-entry-fn index colled-target-val)))
(defn- update-entry-in-index [index path operation]
(let [update-path (butlast path)
update-value (last path)
to-be-updated-set (get-in index update-path #{})]
(assoc-in index update-path (conj to-be-updated-set update-value))))所有这些组件都作为新层添加到给定数据库中。剩下的就是更新数据库的时间戳和top-id字段。最后一步发生在add-entity的最后一行，它也返回更新后的数据库。
我们还提供了一个add-entities便利函数，该函数通过迭代应用add-entity来将多个实体添加到数据库中。
(defn add-entities [db ents-seq] (reduce add-entity db ents-seq))从我们的数据库中删除实体意味着添加一个实体不存在的层。为此，我们需要
此“构造-不包含”过程由remove-entity函数执行，该函数看起来非常类似于add-entity
(defn remove-entity [db ent-id]
(let [ent (entity-at db ent-id)
layer (remove-back-refs db ent-id (last (:layers db)))
no-ref-layer (update-in layer [:VAET] dissoc ent-id)
no-ent-layer (assoc no-ref-layer :storage
(drop-entity
(:storage no-ref-layer) ent))
new-layer (reduce (partial remove-entity-from-index ent)
no-ent-layer (indexes))]
(assoc db :layers (conj (:layers db) new-layer))))引用删除由remove-back-refs函数完成
(defn- remove-back-refs [db e-id layer]
(let [reffing-datoms (reffing-to e-id layer)
remove-fn (fn[d [e a]] (update-entity db e a e-id :db/remove))
clean-db (reduce remove-fn db reffing-datoms)]
(last (:layers clean-db))))我们首先使用reffing-datoms-to查找在给定层中引用我们的所有实体；它返回一系列三元组，其中包含引用实体的 ID，以及属性名称和已删除实体的 ID。
(defn- reffing-to [e-id layer]
(let [vaet (:VAET layer)]
(for [[attr-name reffing-set] (e-id vaet)
reffing reffing-set]
[reffing attr-name])))然后，我们将update-entity应用于每个三元组以更新引用我们已删除实体的属性。（我们将在下一节中探讨update-entity的工作原理。）
remove-back-refs的最后一步是从我们的索引中清除引用本身，更具体地说，是从 VAET 索引中清除，因为它是唯一存储引用信息的索引。
从本质上讲，更新是修改实体属性的值。修改过程本身取决于属性的基数：基数为:db/multiple的属性保存一组值，因此我们必须允许将项目添加到或从该集合中删除，或完全替换该集合。基数为:db/single的属性保存单个值，因此仅允许替换。
由于我们还有直接在属性及其值上提供查找的索引，因此也必须更新这些索引。
与add-entity和remove-entity一样，我们实际上不会就地修改我们的实体，而是会添加一个包含更新实体的新层。
(defn update-entity
([db ent-id attr-name new-val]
(update-entity db ent-id attr-name new-val :db/reset-to))
([db ent-id attr-name new-val operation]
(let [update-ts (next-ts db)
layer (last (:layers db))
attr (attr-at db ent-id attr-name)
updated-attr (update-attr attr new-val update-ts operation)
fully-updated-layer (update-layer layer ent-id
attr updated-attr
new-val operation)]
(update-in db [:layers] conj fully-updated-layer))))要更新属性，我们使用attr-at找到它，然后使用update-attr执行实际更新。
(defn- update-attr [attr new-val new-ts operation]
{:pre [(if (single? attr)
(contains? #{:db/reset-to :db/remove} operation)
(contains? #{:db/reset-to :db/add :db/remove} operation))]}
(-> attr
(update-attr-modification-time new-ts)
(update-attr-value new-val operation)))我们使用两个辅助函数来执行更新。update-attr-modification-time更新时间戳以反映图 1 中黑色箭头的创建
(defn- update-attr-modification-time
[attr new-ts]
(assoc attr :ts new-ts :prev-ts (:ts attr)))update-attr-value实际上更新了值
(defn- update-attr-value [attr value operation]
(cond
(single? attr) (assoc attr :value #{value})
; now we're talking about an attribute of multiple values
(= :db/reset-to operation)
(assoc attr :value value)
(= :db/add operation)
(assoc attr :value (CS/union (:value attr) value))
(= :db/remove operation)
(assoc attr :value (CS/difference (:value attr) value))))剩下的就是从索引中删除旧值并向其中添加新值，然后使用我们所有更新的组件构建新层。幸运的是，我们可以利用我们为添加和删除实体编写的代码来做到这一点。
我们低级 API 中的每个操作都作用于单个实体。但是，几乎所有数据库都有一种方法允许用户将多个操作作为单个事务执行。这意味着
我们可以通过一个接口来满足这些要求，该接口使用数据库和要执行的一组操作，并生成一个其状态反映给定更改的数据库。批处理中提交的所有更改都应通过添加单个层来应用。但是，我们有一个问题：我们低级 API 中编写的所有函数都会向数据库添加一个新层。如果我们要执行一个包含n个操作的批处理，那么我们将看到添加了n个新层，而我们真正想要的是只有一个新层。
这里的关键在于我们想要的层是通过按顺序执行这些更新而产生的最顶层。因此，解决方案是依次执行用户的操作，每个操作都创建一个新的层。当创建最后一层时，我们只取最顶层并将其放置在初始数据库上（让所有中间层都“黯然失色”）。只有在我们完成所有这些操作后，才会更新数据库的时间戳。
所有这些都在transact-on-db函数中完成，该函数接收数据库的初始值和要执行的操作批次，并返回其更新后的值。
(defn transact-on-db [initial-db ops]
(loop [[op & rst-ops] ops transacted initial-db]
(if op
(recur rst-ops (apply (first op) transacted (rest op)))
(let [initial-layer (:layers initial-db)
new-layer (last (:layers transacted))]
(assoc initial-db :layers (conj initial-layer new-layer)
:curr-time (next-ts initial-db)
:top-id (:top-id transacted))))))请注意，这里我们使用了术语值，这意味着只有该函数的调用者才能看到更新后的状态；数据库的其他所有用户都无法感知到此更改（因为数据库是一个值，因此无法更改）。为了构建一个允许用户感知其他用户执行的状态更改的系统，用户不会直接与数据库交互，而是使用另一层间接层来引用它。这层额外的间接层是使用Clojure的Atom实现的，Atom是一种引用类型。在这里，我们利用了Atom的三个主要关键特性，它们是
Atom的引用更新到另一个值。事务接受一个Atom和一个函数。该函数对Atom的值进行操作并返回一个新值。在事务执行完成后，Atom将引用从函数返回的值。Atom引用的值是通过取消引用它来完成的，这将返回该Atom在那个时间点的状态。在Clojure的Atom和transact-on-db中完成的工作之间，仍然存在一个需要弥合的差距；即，使用正确的输入调用事务。
为了拥有最简单、最清晰的API，我们希望用户只需提供Atom和操作列表，并让数据库将用户输入转换为适当的事务。
这种转换发生在以下事务调用链中
transact → _transact → swap! → transact-on-db用户使用Atom（即连接）和要执行的操作调用transact，它将其输入中继到_transact，并在其中添加更新Atom的函数名称（swap!）。
(defmacro transact [db-conn & txs] `(_transact ~db-conn swap! ~@txs))_transact准备对swap!的调用。它通过创建一个列表来实现这一点，该列表以swap!开头，后面跟着Atom，然后是transact-on-db符号和操作批次。
(defmacro _transact [db op & txs]
(when txs
(loop [[frst-tx# & rst-tx#] txs res# [op db `transact-on-db] accum-txs# []]
(if frst-tx#
(recur rst-tx# res# (conj accum-txs# (vec frst-tx#)))
(list* (conj res# accum-txs#))))))swap!在事务中调用transact-on-db（使用先前准备好的参数），而transact-on-db创建数据库的新状态并返回它。
在这一点上，我们可以看到，通过一些微小的调整，我们还可以提供一种询问“如果…”问题的方法。这可以通过将swap!替换为一个不会对系统进行任何更改的函数来实现。此场景通过what-if调用链实现
what-if \(\to\) _transact \(\to\) _what-if \(\to\) transact-on-db
用户使用数据库值和要执行的操作调用what-if。然后，它将这些输入中继到_transact，并向其中添加一个模拟swap! API 但不产生其效果的函数（称为_what-if）。
(defmacro what-if [db & ops] `(_transact ~db _what-if ~@ops))_transact准备对_what-if的调用。它通过创建一个列表来实现这一点，该列表以_what-if开头，后面跟着数据库，然后是transact-on-db符号和操作批次。_what-if调用transact-on-db，就像swap!在事务场景中所做的那样，但不会对系统造成任何更改。
(defn- _what-if [db f txs] (f db txs))请注意，我们没有使用函数，而是使用了宏。在这里使用宏的原因是，宏的参数在调用发生时不会被求值；这使我们能够提供更简洁的API设计，其中用户以与Clojure中任何函数调用结构相同的方式来构建操作。
以上过程可以在以下示例中看到。对于事务，用户调用
(transact db-conn (add-entity e1) (update-entity e2 atr2 val2 :db/add)) 变为
(_transact db-conn swap! (add-entity e1) (update-entity e2 atr2 val2 :db/add))最终变为
(swap! db-conn transact-on-db [[add-entity e1][update-entity e2 atr2 val2 :db/add]])对于what-if，用户调用
(what-if my-db (add-entity e3) (remove-entity e4))变为
(_transact my-db _what-if (add-entity e3) (remove-entity e4))然后
(_what-if my-db transact-on-db [[add-entity e3] [remove-entity e4]])最终变为
(transact-on-db my-db [[add-entity e3] [remove-entity e4]])此时，我们已经实现了数据库的核心功能，现在是时候添加它的存在理由：洞察提取。我们在这里使用的架构方法是允许将这些功能作为库添加，因为数据库的不同用法将需要不同的此类机制。
当实体的属性类型为:db/ref时，会在实体之间创建引用连接，这意味着该属性的值是另一个实体的ID。当将引用实体添加到数据库时，该引用将在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）。
我们介绍的第二个库提供了查询功能，这是本节的主要关注点。如果没有强大的查询机制，数据库对用户来说就没有多大用处。此功能通常通过查询语言公开给用户，该语言用于声明性地指定感兴趣的数据集。
我们的数据模型基于随时间积累的事实（即datom）。对于此模型，寻找合适的查询语言的自然方向是逻辑编程。受逻辑编程影响的常用查询语言是Datalog，它不仅非常适合我们的数据模型，而且对Clojure的语法也有非常优雅的适配。我们的查询引擎将实现Datomic数据库中Datalog语言的一个子集。
让我们看看我们提出的语言中的一个示例查询。此查询询问：“喜欢披萨、会说英语并且生日在本月的实体的名字和生日是什么？”
{ :find [?nm ?bd ]
:where [
[?e :likes "pizza"]
[?e :name ?nm]
[?e :speak "English"]
[?e :bday (bday-mo? ?bd)]]}我们直接使用Clojure数据字面量的语法来提供查询的基本语法。这使我们无需编写专门的解析器，同时仍然提供一种对熟悉Clojure的程序员来说熟悉且易于阅读的形式。
查询是一个包含两个项目的映射
:where作为键，并使用规则作为值。规则是子句的向量，子句是由三个谓词组成的向量，每个谓词都对datom的不同组件进行操作。在上面的示例中，[?e :likes "pizza"]是一个子句。此:where项目定义了一个规则，该规则充当数据库中datom的过滤器（类似于SQL的WHERE子句）。:find作为键，并使用向量作为值。该向量定义了应将所选datom的哪些组件投影到结果中（类似于SQL的SELECT子句）。上面的描述省略了一个关键要求：如何使不同的子句在值上同步（即，在它们之间进行连接操作），以及如何在输出中构造找到的值（由:find部分指定）。
我们使用变量来满足这两个要求，变量用前导?表示。此定义的唯一例外是“不关心”变量_（下划线）。
查询中的子句由三个谓词组成；表10.2定义了在我们的查询语言中哪些可以充当谓词。
| 名称 | 含义 | 示例 |
| 常量 | datom中项目的价值是否等于常量？ | :likes |
| 变量 | 将datom中项目的价值绑定到变量并返回true。 | ?e |
| 不关心 | 始终返回true。 | _ |
| 一元运算符 | 以变量作为操作数的一元运算。 将datom项目的价值绑定到变量（除非它是“_”）。 用datom中项目的价值替换变量。 返回操作的应用结果。 |
(bday-mo? _) |
| 二元运算符 | 必须有一个变量作为其操作数之一的二元运算。 将datom项目的价值绑定到变量（除非它是“_”）。 用datom中项目的价值替换变量。 返回操作的结果。 |
(> ?age 20) |
: 表10.2 - 谓词
工程学都是关于权衡取舍的，设计我们的查询引擎也不例外。在我们的案例中，我们必须解决的主要权衡是功能丰富性与复杂性。解决这种权衡需要我们查看系统的常见用例，并由此决定哪些限制是可以接受的。
在我们的数据库中，我们决定构建一个具有以下限制的查询引擎
虽然这些设计决策导致查询语言不如Datalog丰富，但我们仍然能够支持许多类型简单但有用的查询。
虽然我们的查询语言允许用户指定他们想要访问的内容，但它隐藏了如何实现此目的的细节。查询引擎是数据库组件，负责为给定查询生成数据。
这涉及四个步骤
在此阶段，我们将给定的查询从用户易于理解的表示形式转换为查询计划程序可以有效地使用的表示形式。
查询的:find部分转换为给定变量名称的集合
(defmacro symbol-col-to-set [coll] (set (map str coll)))查询的:where部分保留其嵌套向量结构。但是，每个子句中的每个术语都将根据表10.2替换为谓词。
(defmacro clause-term-expr [clause-term]
(cond
(variable? (str clause-term)) ;variable
#(= % %)
(not (coll? clause-term)) ;constant
`#(= % ~clause-term)
(= 2 (count clause-term)) ;unary operator
`#(~(first clause-term) %)
(variable? (str (second clause-term)));binary operator, 1st operand is variable
`#(~(first clause-term) % ~(last clause-term))
(variable? (str (last clause-term)));binary operator, 2nd operand is variable
`#(~(first clause-term) ~(second clause-term) %)))对于每个子句，将使用该子句中使用的变量名称的向量设置为其元数据。
(defmacro clause-term-meta [clause-term]
(cond
(coll? clause-term) (first (filter #(variable? % false) (map str clause-term)))
(variable? (str clause-term) false) (str clause-term)
:no-variable-in-clause nil))我们使用pred-clause迭代每个子句中的术语
(defmacro pred-clause [clause]
(loop [[trm# & rst-trm#] clause exprs# [] metas# []]
(if trm#
(recur rst-trm# (conj exprs# `(clause-term-expr ~ trm#))
(conj metas#`(clause-term-meta ~ trm#)))
(with-meta exprs# {:db/variable metas#}))))迭代子句本身发生在q-clauses-to-pred-clauses中
(defmacro q-clauses-to-pred-clauses [clauses]
(loop [[frst# & rst#] clauses preds-vecs# []]
(if-not frst# preds-vecs#
(recur rst# `(conj ~preds-vecs# (pred-clause ~frst#))))))我们再次依赖于宏不会急切地求值其参数这一事实。这使我们能够定义一个更简单的 API，用户在其中以符号的形式提供变量名（例如，?name），而不是要求用户通过以字符串形式提供变量名（例如，"?name"）来理解引擎的内部机制，甚至更糟糕的是，引用变量名（例如，'?name）。
在此阶段结束时，我们的示例为:find部分生成了以下集合
#{"?nm" "?bd"} 以及表 10.3 中为:where部分生成的以下结构。（“谓词子句”列中的每个单元格都包含其在“元子句”列中相邻单元格中找到的元数据。）
| 查询子句 | 谓词子句 | 元子句 |
| [?e :likes "pizza"] | [#(= % %) #(= % :likes) #(= % "pizza")] | ["?e" nil nil] |
| [?e :name ?nm] | [#(= % %) #(= % :name) #(= % %)] | ["?e" nil "?nm"] |
| [?e :speak "English"] | [#(= % %) #(= % :speak) #(= % "English")] | ["?e" nil nil] |
| [?e :bday (bday-mo? ?bd)] | [#(= % %) #(= % :bday) #(bday-mo? %)] | ["?e" nil "?bd"] |
: 表 10.3 - 子句
此结构充当在引擎确定正确的执行计划后在后续阶段执行的查询。
在此阶段，我们检查查询以构建一个良好的计划来生成它描述的结果。
通常，这将涉及选择合适的索引（表 10.4）并以函数的形式构建计划。我们根据单个连接变量（只能对单一类型的元素进行操作）选择索引。
| 连接变量操作于 | 要使用的索引 |
| 实体 ID | AVET |
| 属性名称 | VEAT |
| 属性值 | EAVT |
: 表 10.4 - 索引选择
当我们实际执行生成的计划时，下一节将更清楚地说明此映射背后的推理。现在，请注意，这里的关键是选择一个其叶子包含连接变量操作的元素的索引。
连接变量的索引定位由index-of-joining-variable完成
(defn index-of-joining-variable [query-clauses]
(let [metas-seq (map #(:db/variable (meta %)) query-clauses)
collapsing-fn (fn [accV v] (map #(when (= %1 %2) %1) accV v))
collapsed (reduce collapsing-fn metas-seq)]
(first (keep-indexed #(when (variable? %2 false) %1) collapsed)))) 我们首先提取查询中每个子句的元数据。提取的元数据是一个 3 元素向量；每个元素要么是变量名，要么是 nil。（请注意，该向量中最多只有一个变量名。）提取向量后，我们从中（通过缩减）生成一个单一值，该值要么是变量名，要么是 nil。如果生成了变量名，则它出现在所有元数据向量中的同一索引处；即，这是连接变量。因此，我们可以根据上面描述的映射选择使用与此连接变量相关的索引。
选择索引后，我们构建我们的计划，这是一个闭包包含查询和索引名称并执行返回查询结果所需操作的函数。
(defn build-query-plan [query]
(let [term-ind (index-of-joining-variable query)
ind-to-use (case term-ind 0 :AVET 1 :VEAT 2 :EAVT)]
(partial single-index-query-plan query ind-to-use)))在我们的示例中，选择的索引是AVET索引，因为连接变量作用于实体 ID。
我们在上一阶段看到，我们的查询计划以调用single-index-query-plan结束。此函数将
(defn single-index-query-plan [query indx db]
(let [q-res (query-index (indx-at db indx) query)]
(bind-variables-to-query q-res (indx-at db indx))))为了更好地解释此过程，我们将使用我们的示例查询进行演示，假设我们的数据库在表 10.5 中保存实体。
| 实体 ID | 属性名称 | 属性值 |
| 1 | :name :likes :speak :bday |
USA Pizza English July 4, 1776 |
| 2 | :name :likes :speak :bday |
France Red wine French July 14, 1789 |
| 3 | :name :likes :speak :bday |
Canada Snow English July 1, 1867 |
: 表 10.5 - 示例实体
现在是时候深入研究兔子洞，看看query-index函数，我们的查询最终开始产生一些结果。
(defn query-index [index pred-clauses]
(let [result-clauses (filter-index index pred-clauses)
relevant-items (items-that-answer-all-conditions (map last result-clauses)
(count pred-clauses))
cleaned-result-clauses (map (partial mask-path-leaf-with-items
relevant-items)
result-clauses)]
(filter #(not-empty (last %)) cleaned-result-clauses)))此函数首先在之前选择的索引上应用谓词子句。在索引上应用谓词子句会返回一个结果子句。
结果的主要特征是
from-eav应用于谓词子句时完成的。所有这些都在函数filter-index中完成。
(defn filter-index [index predicate-clauses]
(for [pred-clause predicate-clauses
:let [[lvl1-prd lvl2-prd lvl3-prd] (apply (from-eav index) pred-clause)]
[k1 l2map] index ; keys and values of the first level
:when (try (lvl1-prd k1) (catch Exception e false))
[k2 l3-set] l2map ; keys and values of the second level
:when (try (lvl2-prd k2) (catch Exception e false))
:let [res (set (filter lvl3-prd l3-set))] ]
(with-meta [k1 k2 res] (meta pred-clause))))假设查询是在 7 月 4 日执行的，则在上述数据上执行查询的结果如表 10.6 所示。
| 结果子句 | 结果元数据 |
| [:likes Pizza #{1}] | ["?e" nil nil] |
| [:name USA #{1}] | ["?e" nil "?nm"] |
| [:speak "English" #{1, 3}] | ["?e" nil nil] |
| [:bday "July 4, 1776" #{1}] | ["?e" nil "?bd"] |
| [:name France #{2}] | ["?e" nil "?nm"] |
| [:bday "July 14, 1789" #{2}] | ["?e" nil "?bd"] |
| [:name Canada #{3}] | ["?e" nil "?nm"] |
| [:bday "July 1, 1867" {3}] | ["?e" nil "?bd"] |
: 表 10.6 - 查询结果
生成所有结果子句后，我们需要在它们之间执行AND操作。这是通过查找通过所有谓词子句的所有元素来完成的
(defn items-that-answer-all-conditions [items-seq num-of-conditions]
(->> items-seq ; take the items-seq
(map vec) ; make each collection (actually a set) into a vector
(reduce into []) ;reduce all the vectors into one vector
(frequencies) ;count for each item in how many collections (sets) it was in
(filter #(<= num-of-conditions (last %))) ;items that answered all conditions
(map first) ; take from the duos the items themselves
(set))) ; return it as set在我们的示例中，此步骤的结果是一个包含值1（即 USA 的实体 ID）的集合。
现在我们必须删除未通过所有条件的项目
(defn mask-path-leaf-with-items [relevant-items path]
(update-in path [2] CS/intersection relevant-items))最后，我们删除所有“空”的结果子句（即，它们的最后一个项目为空）。我们在query-index函数的最后一行执行此操作。我们的示例为我们留下了表 10.7 中的项目。
| 结果子句 | 结果元数据 |
| [:likes Pizza #{1}] | ["?e" nil nil] |
| [:name USA #{1}] | ["?e" nil "?nm"] |
| [:bday "July 4, 1776" #{1}] | ["?e" nil "?bd"] |
| [:speak "English" #{1}] | ["?e" nil nil] |
: 表 10.7 - 过滤后的查询结果
现在我们准备报告结果了。结果子句结构对于此目的来说过于笨拙，因此我们将将其转换为类似索引的结构（映射的映射）——并带有一个重要的变化。
要理解这个变化，我们首先必须介绍绑定对的概念，它是一对将变量名与其值匹配的元素。变量名是在谓词子句中使用的变量名，值是在结果子句中找到的值。
索引结构的变化在于，现在我们在保存实体 ID/属性名称/值的位置保存实体 ID/属性名称/值的绑定对，就像在索引中一样。
(defn bind-variables-to-query [q-res index]
(let [seq-res-path (mapcat (partial combine-path-and-meta (from-eav index))
q-res)
res-path (map #(->> %1 (partition 2)(apply (to-eav index))) seq-res-path)]
(reduce #(assoc-in %1 (butlast %2) (last %2)) {} res-path)))
(defn combine-path-and-meta [from-eav-fn path]
(let [expanded-path [(repeat (first path)) (repeat (second path)) (last path)]
meta-of-path (apply from-eav-fn (map repeat (:db/variable (meta path))))
combined-data-and-meta-path (interleave meta-of-path expanded-path)]
(apply (partial map vector) combined-data-and-meta-path)))在我们的示例执行的第 3 阶段结束时，我们手头有以下结构
{[1 "?e"]{
{[:likes nil] ["Pizza" nil]}
{[:name nil] ["USA" "?nm"]}
{[:speaks nil] ["English" nil]}
{[:bday nil] ["July 4, 1776" "?bd"]}
}}此时，我们已经生成了用户最初要求的结果的超集。在此阶段，我们将提取用户想要的值。此过程称为统一：在这里，我们将绑定对结构与用户在查询的:find子句中定义的变量名向量统一起来。
(defn unify [binded-res-col needed-vars]
(map (partial locate-vars-in-query-res needed-vars) binded-res-col))每个统一步骤都由locate-vars-in-query-result处理，该函数迭代查询结果（结构为索引条目，但包含绑定对）以检测用户要求的所有变量和值。
(defn locate-vars-in-query-res [vars-set q-res]
(let [[e-pair av-map] q-res
e-res (resultify-bind-pair vars-set [] e-pair)]
(map (partial resultify-av-pair vars-set e-res) av-map)))
(defn resultify-bind-pair [vars-set accum pair]
(let [[ var-name _] pair]
(if (contains? vars-set var-name) (conj accum pair) accum)))
(defn resultify-av-pair [vars-set accum-res av-pair]
(reduce (partial resultify-bind-pair vars-set) accum-res av-pair))在此阶段结束时，我们示例的结果为
[("?nm" "USA") ("?bd" "July 4, 1776")]我们终于构建了面向用户查询机制（q宏）所需的所有组件，该机制接收数据库和查询作为参数。
(defmacro q
[db query]
`(let [pred-clauses# (q-clauses-to-pred-clauses ~(:where query))
needed-vars# (symbol-col-to-set ~(:find query))
query-plan# (build-query-plan pred-clauses#)
query-internal-res# (query-plan# ~db)]
(unify query-internal-res# needed-vars#)))我们的旅程始于对不同类型数据库的概念，并以一个能够
我们仍然可以改进很多方面：我们可以为几个组件添加缓存以提高性能；支持更丰富的查询；并添加真正的存储支持以提供数据持久性，仅举几例。
但是，我们的最终产品可以完成很多事情，并且是用 488 行 Clojure 源代码实现的，其中 73 行为空行，55 行是文档字符串。
最后，还有一件事仍然缺失：一个名称。对于一个用 360 行 Clojure 代码实现的内存中、索引优化、支持查询、库开发者友好、时间感知的功能数据库，唯一合理的选项是 CircleDB。