关系数据库和面向服务的体系结构中的单调性

单调性是关系数据库中的一个重要概念，正如我将在本博文中所演示的那样，单调性也适用于面向服务的体系结构中的API。

直观地，如果信息“不会消失”，则数据库或API是单调的。单调数据库查询比非单调查询可以更有效地分析和优化，单调API可以帮助开发人员避免竞争条件和未定义状态。在Palantir，我们显然关心快速的数据库查询和安全，行为良好的API，在与团队讨论数据库或API体系结构时，我会定期使用单调性框架。因此，让我们深入探讨吧！

我怀疑大多数读者会熟悉单调函数的演算概念：将函数f称为单调递增，如果对于x≤y的所有x，y，我们都有f（x）≤f（y）。左图显示了此功能。在数据库理论中，我们可以类推地定义单调查询的概念：如果对于所有具有D1 with D2的数据库D1，D2有Q（D1）⊆Q（D2），则查询Q是单调的。用简单的英语来说，如果我们在数据库D2上评估行比其他数据库D1多的单调查询Q，那么在较大的数据库D2上查询结果将始终更大（或相等）。

现在，让我们回顾一下关系数据库中查询优化的一些关键结果，特别关注单调查询。作为一个正在运行的示例，请考虑一个具有两个实体的数据域，即帐户和访问策略（简称策略）：每个帐户仅与一个策略相关联，但是同一策略可能与多个帐户相关联。我们可以将此模型建模为两个表，即帐户和策略，并使用以下SQL查询获取帐户列表和相应的访问策略：

通过将策略分为活动策略和禁用策略，我们可以使示例更加有趣。查询所有与禁用策略无关的帐户的查询可以编写如下。 （请注意，此数据库架构仅用于说明目的，我认为我不会在现实中对禁用的策略进行建模。）

-Q2 SELECT * FROM帐户NATURAL JOIN（SELECT * FROM策略，除SELECT * FROM disable_policies外）AS active_policies；

查询Q1是单调的：从直觉上讲，这意味着如果我们向基础数据库添加更多行，查询将不会产生更少的结果。相反，查询Q2不是单调的，因为我们可以通过将行添加到disabled_policies表中来从查询结果中删除行。否定（此处为EXCEPT语句）是数据库查询语言中非单调性的常见来源。

现在，单调查询的意义是什么？好吧，事实证明，单调查询可以解决许多查询分析和优化问题，而大类非单调查询则不能解决。例如，在给定查询Q1和Q2的情况下，所有数据库D？的查询等价问题为Q1（D）= Q2（D），对于单调查询是可确定的，但对于关系演算（包括非单调差分算子）是不可确定的）。

在SQL查询方面，这意味着我们可以确定两个select / project / join SQL查询是否等效，但对于select / project / join / union / difference SQL查询，我们通常无法确定这一点（请参阅Abiteboul等，Foundation of数据库）。

操作中查询等效性的最简单示例是谓词下推：很容易验证Q1：SELECT * FROM帐户NATURAL JOIN策略WHERE policy.id == 42等同于Q2：SELECT * FROM帐户NATURAL JOIN（SELECT * FROM政策（WHERE Policies.id == 42）。上面回顾的结果表明，对于单调选择/项目/联接SQL查询，我们始终可以确定Q1 = Q2，而对于任意SQL查询，没有通用的算法可以确定Q1 = Q2。无法确定性结果的一个有趣的推论是，对于关系演算来说，全局句法查询优化是不可能的：给定查询Q，没有算法可以计算与Q相等的最小关系演算查询。

非单调性不是关系查询语言的复杂性的唯一来源。例如，即使数据记录查询是单调的，其等效性问题对于数据日志查询（大致来说，具有递归的选择/投影/联接查询）也无法确定。

直观地讲，关系数据库的要点是，对于许多查询分析任务而言，非单调性是相当大的困难来源。

让我们进行调整，看看在面向服务的体系结构中我称之为“ API单调性”的角色，特别是在REST API的情况下。在上面的同一帐户/策略域中，我们可以想象一个分别管理帐户和策略对象的帐户服务和单独的策略服务：

＃帐户和策略服务的HTTP / JSON实现＃帐户服务-> {“ account_id”：{account_id}，“ policy_id”：{policy_id}} PUT / accounts / {account_id} GET / accounts / {account_id} {“ policy_id”：{policy_id}，“ policy”：{...}} PUT / policies / {policy_id} GET / policies / {policy_id} {“ policy_id”：123，“ policy”：{...}} PUT / policies / 123 GET / policies / 123 {“ policy_id”：123，“ policy”：{...}} PUT / policies / 123 GET / policies / 123 <-{“ policy_id”：123，“ policy”：{...}， isDeleted：false}删除/ policies / 123 GET / policies / 123 <-{“ policy_id”：123，“ policy”：{...}，isDeleted：true}

帐户服务可以使用isDeleted标志来启动用户操作以解决不一致问题，例如通过显示帐户以及“无效策略：请选择新策略”警告消息。更重要的是，如果帐户服务仅存储policy_id（而不是完整的策略对象），则它始终有权访问引用的策略，甚至删除的策略也是如此。

一个有趣的推论是，单调性API不能很好地与删除融合。例如，假设我们有删除政策信息的法律义务，例如因为它包含PII数据。删除要求与单调性属性不一致，因为我们不能同时删除策略并保留它。 API设计人员在平衡法律约束（例如，一方面GDPR中的数据最小化原则与另一方面，体系结构或性能要求）时必须牢记这一折衷。我知道这有点困难，但是我想我会在以后的博客文章中对此主题保留更多的想法，请继续关注！

最后，让我们看一下面向服务的体系结构中跨服务通信的事件源范例。简而言之，事件源背后的想法是存储不可变的变更事件，而不是变异数据。 API使用者可以访问事件日志并按顺序处理事件。

从上面调用PUT和DELETE的顺序将引起两个事件的顺序，即[putPolicy（123），deletePolicy（123）]。帐户服务尾随策略服务的事件日志，并且可以保留策略服务中可用策略的内部表示。例如，我们可以保留所有创建的策略，并在接收到deletePolicy（..）事件时将其标记为isDeleted，从而从上面实现REST示例中描述的单调行为。此外，请注意，事件日志本身仅是追加操作，因此根据定义是单调的。

如果您对事件外包感兴趣，我也鼓励您阅读我以前的博客文章，《重新思考Foundry的业务流程后端：从CRUD到事件外包》。

单调性之类的抽象概念通常应用于计算机科学和软件工程的各个领域。这篇博文说明单调数据库查询更易于分析和优化，单调服务API允许开发人员强制执行所需的数据一致性不变量。