入门教程#
本教程将介绍Cozo数据库的基本功能。
建议一边学习一边在自己的环境中执行查询语句,也可以做一些修改,以加深印象。你可以用下面这些方式来执行查询:
你可以从 发布页面(国内镜像)下载名为
cozo-*
的可执行文件(请选择与你的操作系统以及 CPU 匹配的版本),解压缩,改名为cozo
,然后在终端中执行命令cozo repl
以开启命令行模式。在执行中如果可以粘贴多行代码。如果要手动输入多行代码,则先输入空格,再输入回车,以进入多行模式。
下面这个单元格是用来初始化Jupyter的:如果你使用的是其它方式,请忽略。
[1]:
%load_ext pycozo.ipyext_direct
基础知识#
Cozo是一个关系型数据库。以下是经典的“你好,世界”查询:
[2]:
?[] <- [['hello', 'world', 'Cozo!']]
[2]:
_0 | _1 | _2 | |
---|---|---|---|
0 | hello | world | Cozo! |
在这个查询中,我们将一个由列表的列表所表示的临时性表传递给了数据库,而数据库将其作为结果返回。
可以传递更多行,或者列:
[3]:
?[] <- [[1, 2, 3], ['a', 'b', 'c']]
[3]:
_0 | _1 | _2 | |
---|---|---|---|
0 | 1 | 2 | 3 |
1 | a | b | c |
这个例子展示了如何输入数字、字符串、布尔值以及空值:
[4]:
?[] <- [[1.5, 2.5, 3, 4, 5.5],
['aA', 'bB', 'cC', 'dD', 'eE'],
[true, false, null, -1.4e-2, "A string with double quotes"]]
[4]:
_0 | _1 | _2 | _3 | _4 | |
---|---|---|---|---|---|
0 | True | False | None | -0.014000 | A string with double quotes |
1 | 1.500000 | 2.500000 | 3 | 4 | 5.500000 |
2 | aA | bB | cC | dD | eE |
可以看出,Cozo中的输入表达式与JavaScript中的类似。Cozo保证对双引号中的字符串的解析方式与JSON中字符串的解析方式完全相同。Cozo的查询结果以JSON格式传递给程序,但它们在屏幕上的显示方式可能不同于JSON,比如在Python中布尔运算会按照Python的类型显示为大写而不是JSON中的小写。
在这个例子中,行返回的顺序与输入的顺序不一样。这是因为在Cozo中,表永远是以树的形式存储的,而树中所存数据是有序的。树在存储数据时每个键只能有一个值,因此Cozo所返回的结果也不会包含重复行:
[5]:
?[] <- [[1], [2], [1], [2], [1]]
[5]:
_0 | |
---|---|
0 | 1 |
1 | 2 |
也就是说,Cozo中的表遵循 集合 语义,会自动去重。相比之下,SQL通常遵循 词袋 语义。(数据库通常通过给每条记录赋一个唯一的内部键来实现词袋语义。在Cozo中如果需要重复行,则需要显性地这么做。)
Cozo采用集合语义的原因是集合语义在处理表之间的递归时要方便得多。Cozo作为一个以图数据为基础的数据库,通常需要处理大量的递归。
表达式#
以下例子展示了表达式和注释的使用:
[6]:
?[] <- [[
1 + 2, # 加法
3 / 4, # 减法
5 == 6, # 等于
7 > 8, # 大于
true || false, # 逻辑或
false && true, # 逻辑与
lowercase('HELLO'), # 函数
rand_float(), # 不需要参数的函数
union([1, 2, 3], [3, 4, 5], [5, 6, 7]), # 参数数量不定的函数
]]
[6]:
_0 | _1 | _2 | _3 | _4 | _5 | _6 | _7 | _8 | |
---|---|---|---|---|---|---|---|---|---|
0 | 3 | 0.750000 | False | False | True | False | hello | 0.342518 | [1, 2, 3, 4, 5, 6, 7] |
可以在 这里 查阅所有的函数。函数的语法与类C语言的函数类似。
规则与表#
之前的例子均以 ?[] <-
开头。包含 <-
这种形式的 规则 叫做 常量规则。?
之后 <-
之前的部分是规则的 头部,<-
之后的部分是规则的 正文。
每个规则均有名。名为 ?
的规则是一个特殊的规则:其结果会作为整个查询的结果返回。
在规则头部中我们可给出返回的每列 绑定 变量:
[7]:
?[first, second, third] <- [[1, 2, 3], ['a', 'b', 'c']]
[7]:
first | second | third | |
---|---|---|---|
0 | 1 | 2 | 3 |
1 | a | b | c |
常量规则的绑定变量的数量必须与实际数据相匹配,否则将会报错:
[8]:
?[first, second] <- [[1, 2, 3], ['a', 'b', 'c']]
[8]:
parser::fixed_rule_head_arity_mismatch
× Fixed rule head arity mismatch
╭────
1 │ ?[first, second] <- [[1, 2, 3], ['a', 'b', 'c']]
· ─────────────────────────────────────────────────
╰────
help: Expected arity: 3, number of arguments given: 2
规则的正文中可以 应用 其它规则:
[9]:
rule[first, second, third] <- [[1, 2, 3], ['a', 'b', 'c']]
?[a, b, c] := rule[a, b, c]
[9]:
a | b | c | |
---|---|---|---|
0 | 1 | 2 | 3 |
1 | a | b | c |
在第一行中,我们定义了一个名为 rule
的常量规则。名为 ?
规则是一个 内联规则 ,用连接符号 :=
来表示。 在它的正文中,它应用了之前定义的固定规则:给出规则的名称与三个 新的绑定 ,即变量 a
、 b
和 c
。
通过内联规则,可以指定返回哪些列,以及返回的列的顺序:
[10]:
rule[first, second, third] <- [[1, 2, 3], ['a', 'b', 'c']]
?[c, b] := rule[a, b, c]
[10]:
c | b | |
---|---|---|
0 | 3 | 2 |
1 | c | b |
内联规则的正文由 原子 组成。在以上例子中,我们以唯一的一个 规则应用原子 作为规则的正文。如果有多个原子,则用逗号连接它们:
[11]:
?[c, b] := rule[a, b, c], is_num(a)
rule[first, second, third] <- [[1, 2, 3], ['a', 'b', 'c']]
[11]:
c | b | |
---|---|---|
0 | 3 | 2 |
这里第二个原子是一个 表达式 is_num(a)
。表达式原子的作用是过滤结果:只有表达式求值为“真”的行会被返回。如果一个查询包含多个规则,他们之间的顺序不重要。
在规则应用原子中,参数也可以直接绑定为常量:
[12]:
rule[first, second, third] <- [[1, 2, 3], ['a', 'b', 'c']]
?[c, b] := rule['a', b, c]
[12]:
c | b | |
---|---|---|
0 | c | b |
归一运算符 =
可用来引入新的绑定:
[13]:
rule[first, second, third] <- [[1, 2, 3], ['a', 'b', 'c']]
?[c, b, d] := rule[a, b, c], is_num(a), d = a + b + 2*c
[13]:
c | b | d | |
---|---|---|---|
0 | 3 | 2 | 9 |
如果在规则正文中包含多个规则应用,返回结果为所有绑定的组合:
[14]:
r1[] <- [[1, 'a'], [2, 'b']]
r2[] <- [[2, 'B'], [3, 'C']]
?[l1, l2] := r1[a, l1],
r2[b, l2]
[14]:
l1 | l2 | |
---|---|---|
0 | a | B |
1 | a | C |
2 | b | B |
3 | b | C |
因为这里两个规则应用中所有的绑定都不同,所以结果给出了关系代数中的笛卡尔乘积。如果绑定被重复使用,就会引发 隐式归一,也就是关系代数中的内连:
[15]:
r1[] <- [[1, 'a'], [2, 'b']]
r2[] <- [[2, 'B'], [3, 'C']]
?[l1, l2] := r1[a, l1],
r2[a, l2] # reused `a`
[15]:
l1 | l2 | |
---|---|---|
0 | b | B |
算符 =
表示与单一值的归一。如果要与列表中所有的值依次进行归一,则可用 in
算符:
[16]:
?[x, y] := x in [1, 2, 3], y in ['x', 'y']
[16]:
x | y | |
---|---|---|
0 | 1 | x |
1 | 1 | y |
2 | 2 | x |
3 | 2 | y |
4 | 3 | x |
5 | 3 | y |
内联规则的头部不需要使用正文中出现的所有变量,但是头部中的任何变量都必须在主体中至少出现一次,这叫做 安全规则:
[17]:
r1[] <- [[1, 'a'], [2, 'b']]
r2[] <- [[2, 'B'], [3, 'C']]
?[l1, l2, x] := r1[a, l1],
r2[a, l2]
[17]:
eval::unbound_symb_in_head
× Symbol 'x' in rule head is unbound
╭─[3:1]
3 │
4 │ ?[l1, l2, x] := r1[a, l1],
· ─
5 │ r2[a, l2]
╰────
help: Note that symbols occurring only in negated positions are not considered bound
存储表#
Cozo中,持久化的表叫做 存储表,创建起来很简单:
[18]:
r1[] <- [[1, 'a'], [2, 'b']]
r2[] <- [[2, 'B'], [3, 'C']]
?[l1, l2] := r1[a, l1],
r2[a, l2]
:create stored {l1, l2}
[18]:
status | |
---|---|
0 | OK |
在这个例子中,:create
查询选项声明将返回结果存储在一个名为 stored
的存储表中,包含列 l1
和 l2
。
注意:给表起名时不要以下划线 _
开头。如果你使用了下划线开头的表名,程序并不会报错,但是你会发现表并没有被存储:实际上你创建的是 临时表 而非存储表。 这里 有详细的说明。
如果只是想创建存储表而不添加任何数据,可以省略查询,只保留 :create
选项。
可以通过运行一个 系统操作符 来验证目前系统中已经有刚刚创建的存储表:
[19]:
::relations
[19]:
name | arity | access_level | n_keys | n_non_keys | n_put_triggers | n_rm_triggers | n_replace_triggers | |
---|---|---|---|---|---|---|---|---|
0 | stored | 2 | normal | 2 | 0 | 0 | 0 | 0 |
也可以列出存储表所包含的列:
[20]:
::columns stored
[20]:
column | is_key | index | type | has_default | |
---|---|---|---|---|---|
0 | l1 | True | 0 | Any? | False |
1 | l2 | True | 1 | Any? | False |
应用一个存储表时,在其名字前加一个 *
符号,以和内联规则的应用区分:
[21]:
?[a, b] := *stored[a, b]
[21]:
a | b | |
---|---|---|
0 | b | B |
与内联表不同,存储表的列有固定的名称。利用这一点,我们可以不必每次都列出所有的列名,而是有选择地通过名称引用列:
[22]:
?[a, b] := *stored{l2: b, l1: a}
[22]:
a | b | |
---|---|---|
0 | b | B |
如果列名与欲绑定的变量同名,我们可以使用简略的写法:
[23]:
?[l2] := *stored{l2}
[23]:
l2 | |
---|---|
0 | B |
使用 :put
加入数据至存储表中:
[24]:
?[l1, l2] <- [['e', 'E']]
:put stored {l1, l2}
[24]:
status | |
---|---|
0 | OK |
[25]:
?[l1, l2] := *stored[l1, l2]
[25]:
l1 | l2 | |
---|---|---|
0 | b | B |
1 | e | E |
使用 :rm
删除数据:
[26]:
?[l1, l2] <- [['e', 'E']]
:rm stored {l1, l2}
[26]:
status | |
---|---|
0 | OK |
[27]:
?[l1, l2] := *stored[l1, l2]
[27]:
l1 | l2 | |
---|---|---|
0 | b | B |
使用 ::remove
(注意:两个冒号)删除整个存储表:
[28]:
::remove stored
[28]:
status | |
---|---|
0 | OK |
[29]:
::relations
[29]:
name | arity | access_level | n_keys | n_non_keys | n_put_triggers | n_rm_triggers | n_replace_triggers |
---|
到目前为止,所有存储表的数据都存在了其键中。我们可以指示Cozo只将一部分列数据作为键,从而声明数据的 函数性依赖:
[30]:
?[a, b, c] <- [[1, 'a', 'A'],
[2, 'b', 'B'],
[3, 'c', 'C'],
[4, 'd', 'D']]
:create fd {a, b => c}
[30]:
status | |
---|---|
0 | OK |
[31]:
?[a, b, c] := *fd[a, b, c]
[31]:
a | b | c | |
---|---|---|---|
0 | 1 | a | A |
1 | 2 | b | B |
2 | 3 | c | C |
3 | 4 | d | D |
在这个表中,插入一条包含已有键的数据,该行的值会被更新:
[32]:
?[a, b, c] <- [[3, 'c', 'CCCCCCC']]
:put fd {a, b => c}
[32]:
status | |
---|---|
0 | OK |
[33]:
?[a, b, c] := *fd[a, b, c]
[33]:
a | b | c | |
---|---|---|---|
0 | 1 | a | A |
1 | 2 | b | B |
2 | 3 | c | CCCCCCC |
3 | 4 | d | D |
以下命令返回的 is_key
列显示了存储表中每列是否为键:
[34]:
::columns fd
[34]:
column | is_key | index | type | has_default | |
---|---|---|---|---|---|
0 | a | True | 0 | Any? | False |
1 | b | True | 1 | Any? | False |
2 | c | False | 2 | Any? | False |
我们也可以看到,每列都有其声明的类型与默认值,而且每个存储表可以有关联的 触发器。此章节 将详述这些问题。
在进入下一小节前,我们先删除之前创建的存储表:
[35]:
::remove fd
[35]:
status | |
---|---|
0 | OK |
图#
下面我们将一张 图 (也叫 网络)存入一个存储表:
[36]:
?[loving, loved] <- [['alice', 'eve'],
['bob', 'alice'],
['eve', 'alice'],
['eve', 'bob'],
['eve', 'charlie'],
['charlie', 'eve'],
['david', 'george'],
['george', 'george']]
:replace love {loving, loved}
[36]:
status | |
---|---|
0 | OK |
这个图表述了一段复杂的恋爱关系:Alice爱Eve,Bob爱Alice;没人爱David,但David爱George,而George只爱自己,等等。创建此存储表时我们使用了 :replace
而不是 :create
,其区别在于,如果已经存在名为 love
的存储表,则将其现有数据抹去,再加入新的数据。
有了这张图,我们就可以研究一些恋爱中的竞争关系:
[37]:
?[loved_by_b_e] := *love['eve', loved_by_b_e],
*love['bob', loved_by_b_e]
[37]:
loved_by_b_e | |
---|---|
0 | alice |
到目前为止所有规则的正文都只包含了原子间的 结合(类似于“与关系”)。通过 or
算符,我们也可以表达原子之间的 析取(类似于“或”关系):
[38]:
?[loved_by_b_e] := *love['eve', loved_by_b_e] or *love['bob', loved_by_b_e],
loved_by_b_e != 'bob',
loved_by_b_e != 'eve'
[38]:
loved_by_b_e | |
---|---|
0 | alice |
1 | charlie |
表达析取关系的另一种方式是给一条规则赋予多段不同的正文:
[39]:
?[loved_by_b_e] := *love['eve', loved_by_b_e],
loved_by_b_e != 'bob',
loved_by_b_e != 'eve'
?[loved_by_b_e] := *love['bob', loved_by_b_e],
loved_by_b_e != 'bob',
loved_by_b_e != 'eve'
[39]:
loved_by_b_e | |
---|---|
0 | alice |
1 | charlie |
当同一内联规则有多条正文时,这一规则下的所有头部都必须兼容。只有内联规则可以有多条正文,常量规则不行。
否定#
首先是用 !
算符对表达式进行否定:
[40]:
?[loved] := *love[person, loved], !ends_with(person, 'e')
[40]:
loved | |
---|---|
0 | alice |
1 | george |
我们也可以否定一条规则应用,但是不用算符 !
,而使用 not
:
[41]:
?[loved_by_e_not_b] := *love['eve', loved_by_e_not_b],
not *love['bob', loved_by_e_not_b]
[41]:
loved_by_e_not_b | |
---|---|
0 | bob |
1 | charlie |
在Cozo中有两个层次的逻辑运算,一层作用于表达式,另层作用于原子:
原子:
,
,and
为“与”,or
为“或”,not
为“非”表达式:
&&
为“与”,||
为“或”,!
为“非”
,
与 and
的区别是他们的运算优先级:and
的优先级比 or
高,而 or
的优先级比 ,
高。
在对原子进行否定时,必须保证 安全:
[42]:
?[not_loved_by_b] := not *love['bob', not_loved_by_b]
[42]:
eval::unbound_symb_in_head
× Symbol 'not_loved_by_b' in rule head is unbound
╭────
1 │ ?[not_loved_by_b] := not *love['bob', not_loved_by_b]
· ──────────────
╰────
help: Note that symbols occurring only in negated positions are not considered bound
这个查询因为不安全而被禁止。不安全的原因是,此查询的结果是一个无穷大的集合。例如,根据现有的数据,Bob没有明确表现出过对“钱”的兴趣,因此“钱”就应该包含在结果中。
为了保证此查询能够返回有限的结果,我们必须明确地给出一个 封闭的世界:
[43]:
the_population[p] := *love[p, _a]
the_population[p] := *love[_a, p]
?[not_loved_by_b] := the_population[not_loved_by_b],
not *love['bob', not_loved_by_b]
[43]:
not_loved_by_b | |
---|---|
0 | bob |
1 | charlie |
2 | david |
3 | eve |
4 | george |
递归#
内联规则可以应用其他规则,并且可以有多条正文。将此两者结合起来,便有了递归:
[44]:
alice_love_chain[person] := *love['alice', person]
alice_love_chain[person] := alice_love_chain[in_person],
*love[in_person, person]
?[chained] := alice_love_chain[chained]
[44]:
chained | |
---|---|
0 | alice |
1 | bob |
2 | charlie |
3 | eve |
实际上,只需要能够应用其他规则,而不需要多条正文,便可以递归。但只有单条正文的递归没什么实际作用:
[45]:
alice_love_chain[person] := alice_love_chain[in_person],
*love[in_person, person]
?[chained] := alice_love_chain[chained]
[45]:
chained |
---|
与“否定”一节中的情况类似,如果没有办法从给定的事实中推导出一条事实,那么这条事实就被认为是“假”的。多条正文的作用在于给出一开始便为“真”的一些事实,以启动递归程序。
聚合#
聚合 通常用于计算统计数据。在Cozo中,在内联规则的头部以函数的形式来表达聚合计算:
[46]:
?[person, count(loved_by)] := *love[loved_by, person]
[46]:
person | count(loved_by) | |
---|---|---|
0 | alice | 2 |
1 | bob | 1 |
2 | charlie | 1 |
3 | eve | 2 |
4 | george | 2 |
Cozo支持诸如求和 sum
、平均数 mean
等常见的聚合。在后面我们将看到,将聚合表达在规则的头部而不是正文中,使得查询语言的表达力更加强大。
完整的聚合列表 在此。
查询选项#
在上面我们已经见过了诸如 :create
、:put
、:rm
等操作存储表的查询选项。另一些查询选项可以改变返回值的各种方面,比如只返回一行:
[47]:
?[loving, loved] := *love{ loving, loved }
:limit 1
[47]:
loving | loved | |
---|---|---|
0 | alice | eve |
在下面这个例子,我们要求返回值以 love
列正向排序,在顺序相同时再以 loving
列反向排序,然后省略结果里面的第一行:
[48]:
?[loving, loved] := *love{ loving, loved }
:order -loved, loving
:offset 1
[48]:
loving | loved | |
---|---|---|
0 | george | george |
1 | alice | eve |
2 | charlie | eve |
3 | eve | charlie |
4 | eve | bob |
5 | bob | alice |
6 | eve | alice |
在 :order
选项子句中的变量前面加上 -
表示降序,+
或者不写表示升序。
这一章 介绍了所有的查询选项。
固定规则#
用于常量规则的 <-
语法是语法糖,去糖后的写法是:
[49]:
?[] <~ Constant(data: [['hello', 'world', 'Cozo!']])
[49]:
_0 | _1 | _2 | |
---|---|---|---|
0 | hello | world | Cozo! |
这是一个名为 Constant
的 固定规则,其需要一个名为 data
的选项。“摇尾巴算符” <~
表示固定规则。
固定规则除了选项外,也接受表作为参数,表可以是存储表也可以是内联表。固定规则对这些表进行计算并输出结果。上面我们介绍的固定规则 Constant
接受 0 个表作为参数。
如果在浏览器中使用Cozo,则 Constant
是唯一可以使用的固定规则。其它平台的Cozo包含了图算法模块,其中所有的图算法都是作为固定规则来实现的。比如,我们可以使用PageRank算法来找出谁在上面的爱情大三角中最受欢迎:
[50]:
?[person, page_rank] <~ PageRank(*love[])
:order -page_rank
[50]:
person | page_rank | |
---|---|---|
0 | george | 0.280443 |
1 | eve | 0.275376 |
2 | alice | 0.191205 |
3 | bob | 0.103023 |
4 | charlie | 0.103023 |
5 | david | 0.025000 |
在这个例子中,我们将存储表 *love
作为参数。如上所述,在浏览器中运行此查询将会报错。
所有的固定规则 见此。
[51]:
::remove love
[51]:
status | |
---|---|
0 | OK |
历史穿梭#
一般来说,当我们 :put
键值至一个表中时,旧的值会被覆盖,而我们 :rm
键时,该键值就被删除。如果这种操作的历史记录本身就具有价值,那我们就应当将其保存下来:参见 这个小故事。历史穿梭 就是 Cozo 对于这种场景的解决方案:存储表中的数据不单单是当前所有的事实,也同时包括所有事实完整的历史(对于还在不停产生的数据来说,到目前为止所有的历史)。
当然确实并不是所有项目都需要这种功能。Cozo 奉行“零成本、零脑力开销的抽象”的理念,也就是说,如果你不使用某个功能(抽象),那你第一不需要承担这个功能所带来的性能损失,第二你也不用费脑力理解这个功能的任何东西。所以如果你不需要历史穿梭,可以直接跳到下一节继续阅读。
从简单的例子开始:存储国家元首的表。首先我们创建这个表:
[52]:
:create hos {state: String, year: Validity => hos: String}
[52]:
status | |
---|---|
0 | OK |
这里 hos
是“国家元首”的简写。与之前我们创建的表相比,这个表唯一特殊的地方是它年份 year
这一列的类型为 Validity
(有效性)。有效性看作是一个包含两个元素的数组,其中第一个元素是一个整数,记录该行所表示事实的“时间戳”;第二个元素是一个布尔值,若为真,则表示该事实是从这个时间开始 有效
的断言,若为假,则表示前一个同键事实到此时间时不再有效。注意,这里的“时间戳”的具体意义由用户来决定,你可以将时间戳记录为秒,记录为年,甚至只是一个没有具体间隔的递增的数列。在这个存储表中,为了简单起见,我们的时间以年份记录。
先插入一些数据:
[53]:
?[state, year, hos] <- [['US', [2001, true], 'Bush'],
['US', [2005, true], 'Bush'],
['US', [2009, true], 'Obama'],
['US', [2013, true], 'Obama'],
['US', [2017, true], 'Trump'],
['US', [2021, true], 'Biden']]
:put hos {state, year => hos}
[53]:
status | |
---|---|
0 | OK |
上面插入的 2005
的数据其实即使省略了,历史穿梭的查询结果也一样,因为其值与前一条相同。这个存储表可以当做一个普通的存储表使用:
[54]:
?[state, year, hos] := *hos{state, year, hos}
[54]:
state | year | hos | |
---|---|---|---|
0 | US | [2021, True] | Biden |
1 | US | [2017, True] | Trump |
2 | US | [2013, True] | Obama |
3 | US | [2009, True] | Obama |
4 | US | [2005, True] | Bush |
5 | US | [2001, True] | Bush |
以上我们看出,有效性类型并不是一个真正的数组,因为它是按时间降序排列的。
如果一个存储表的最后一个键列具有显性的 Validity
类型,那这个表就支持历史穿梭查询。比如,我们忘了 2019 年美国元首是谁。那就查查:
[55]:
?[hos, year] := *hos{state: 'US', year, hos @ 2019}
[55]:
hos | year | |
---|---|---|
0 | Trump | [2017, True] |
这也能忘?结果中除了名字之外,还返回了行本身的有效性。
2099 年的时候,美国元首是谁呢?
[56]:
?[hos, year] := *hos{state: 'US', year, hos @ 2099}
[56]:
hos | year | |
---|---|---|
0 | Biden | [2021, True] |
这……可能不太对。其实 2025 年之后是谁,我们目前都 不知道。我们可以显性地表示我们这种无知:
[57]:
?[state, year, hos] <- [['US', [2025, false], '']]
:put hos {state, year => hos}
[57]:
status | |
---|---|
0 | OK |
这种对于无知的表示对应于普通存储表中的 删除 操作。如果你想要你的存储表不可变,则永远只在其中 插入 数据,永远也不要 删除 或 覆盖 数据。由于有效性是键的一部分,所以只要两个键的有效性不同,它们之间就不构成覆盖。
我们再执行一次上一个查询:
[58]:
?[hos, year] := *hos{state: 'US', year, hos @ 2099}
[58]:
hos | year |
---|
由于我们明确地表示了我们的无知,数据库现在也说“不知道”。
历史穿梭是作用于每一个存储表的应用的:我们可以在同一查询中对于同一个存储表给出不同的穿梭时间戳:
[59]:
?[hos2018, hos2010] := *hos{state: 'US', hos: hos2018 @ 2018},
*hos{state: 'US', hos: hos2010 @ 2010}
[59]:
hos2018 | hos2010 | |
---|---|---|
0 | Trump | Obama |
我们已经说过,有效性中的时间戳如何解释由用户来定。而 Cozo 中有一些其他的功能,基于对这个时间戳的一种默认的解释。让我们先创建一个存储表,用来记录每个人的心情:
[60]:
:create mood {name: String, at: Validity => mood: String}
[60]:
status | |
---|---|
0 | OK |
记录自己 当前 的心情:
[61]:
?[name, at, mood] <- [['me', 'ASSERT', 'curious']]
:put mood {name, at => mood}
[61]:
status | |
---|---|
0 | OK |
注意这里我们给出的有效性不是一个二元数组,而是字符串 ASSERT
,这意味着我们要求系统应用 当前的 时间戳,且有效性中的布尔值应为真。什么是“当前”呢?
[62]:
?[name, at, mood] := *mood{name, at, mood}
[62]:
name | at | mood | |
---|---|---|---|
0 | me | [1672047587447466, True] | curious |
这个挺大的整数代表的意义是以 微秒(百万分之一秒)记录的 UNIX 时间戳。我们可以把它转化成更易读的字符串形式:
[63]:
?[name, time, mood] := *mood{name, at, mood},
time = format_timestamp(at)
[63]:
name | time | mood | |
---|---|---|---|
0 | me | 2022-12-26T09:39:47.447+00:00 | curious |
想知道 现在 的事实,我们可以用字符串 NOW
作为有效性的时间戳:
[64]:
?[name, time, mood] := *mood{name, at, mood @ 'NOW'},
time = format_timestamp(at)
[64]:
name | time | mood | |
---|---|---|---|
0 | me | 2022-12-26T09:39:47.447+00:00 | curious |
我们同样也可以在插入数据时手动给出未来的时间戳。由于以微秒计的时间戳不易读,系统同时也接受表示时间的字符串作为有效性:
[65]:
?[name, at, mood] <- [['me', '2030-01-01T00:00:00.000+00:00', 'hopeful']]
:put mood {name, at => mood}
[65]:
status | |
---|---|
0 | OK |
未来的事实不改变当前的查询:
[66]:
?[name, time, mood] := *mood{name, at, mood @ 'NOW'},
time = format_timestamp(at)
[66]:
name | time | mood | |
---|---|---|---|
0 | me | 2022-12-26T09:39:47.447+00:00 | curious |
除了 NOW
之外,我们也可以使用字符串 END
来作为查询时有效性的声明,其意义为我们想知道世界末日时的事实:
[67]:
?[name, time, mood] := *mood{name, at, mood @ 'END'},
time = format_timestamp(at)
[67]:
name | time | mood | |
---|---|---|---|
0 | me | 2030-01-01T00:00:00+00:00 | hopeful |
当我们想声明我们 从现在开始 对未来的无知时,可以使用 RETRACT
字符串:
[68]:
?[name, at, mood] <- [['me', 'RETRACT', '']]
:put mood {name, at => mood}
[68]:
status | |
---|---|
0 | OK |
从某个时刻开始的无知,也可以用表示时间的字符串来声明:只需要在字符串前添加 ~
符号:
[69]:
?[name, at, mood] <- [['me', '~9999-01-01T00:00:00.000+00:00', 'who cares']]
:put mood {name, at => mood}
[69]:
status | |
---|---|
0 | OK |
同时,作为一个普通的存储表,我们可以一次性查看历史的全局:
[70]:
?[name, time, is_assert, mood] := *mood{name, at, mood},
time = format_timestamp(at),
is_assert = to_bool(at)
[70]:
name | time | is_assert | mood | |
---|---|---|---|---|
0 | me | 2022-12-26T09:39:47.447+00:00 | True | curious |
1 | me | 2022-12-26T09:40:19.999+00:00 | False | |
2 | me | 2030-01-01T00:00:00+00:00 | True | hopeful |
3 | me | 9999-01-01T00:00:00+00:00 | False | who cares |
是不是觉得历史穿梭还挺好使的?而且,由于这个功能是在底层实现的,这些查询运行起来比直接拿规则拼出来的等价查询 快得多。
在 此章节 中有更多的关于历史穿梭的技术性论述。
[71]:
::remove mood, hos
[71]:
status | |
---|---|
0 | OK |
延伸案例:航空路线数据集#
我们已经对 Cozo 的使用有了一个基本的了解。接下来我们会研究一个小型的真实数据集,这个数据集是一个图,有大约 3700 个节点和 57000 条边。
这个数据集以及以下的不少具体例子,都改编自 《实用Gremlin》 一书。Gremlin 是一种命令式的图查询语言,与声明式的 Datalog 有很大不同。
我们先创建所需的存储表:
[52]:
{:create airport {
code: String
=>
icao: String,
desc: String,
region: String,
runways: Int,
longest: Float,
elev: Float,
country: String,
city: String,
lat: Float,
lon: Float
}}
{:create country {
code: String
=>
desc: String
}}
{:create continent {
code: String
=>
desc: String
}}
{:create contain { entity: String, contained: String }}
{:create route { fr: String, to: String => dist: Float }}
[52]:
status | |
---|---|
0 | OK |
这里我们一次性执行了多条查询,每条查询都包含在一对花括号中。这多条查询构成了一个 事务:同一个事务中的所有查询对存储层的写入是 原子化 的,要么全部成功,要么全部失败,没有中间状态。
以下命令仅限于使用 Jupyter 的情况:它下载一个包含了所有数据的 JSON 文件并将其导入数据库。注释的行干的也是类似的事情,只是使用了本地文件而不是网络文件。如果你是在浏览器中学习此教程,浏览器界面上有按钮可以让你导入网络或本地的文件。
[53]:
%cozo_import_remote_file 'https://raw.githubusercontent.com/cozodb/cozo/dev/cozo-core/tests/air-routes.json'
# %cozo_import_local_file '../../cozo/cozo-core/tests/air-routes.json'
如果你是在 cozo repl
的命令行中执行查询的,则应当使用以下命令:
%import https://raw.githubusercontent.com/cozodb/cozo/dev/cozo-core/tests/air-routes.json
以上的网址可以替换为本地文件的路径,或国内镜像的地址(见此)。其他环境中也有达成同样事情的不同手段:请参阅各个环境自己的文档。
当然,这个 JSON 文件是我们事先特地准备好的。一般来说原始的数据文件不长这样。在本教程的末尾,我们会介绍如何直接导入原始文件。
现在我们先确认存储表都成功创建了:
[54]:
::relations
[54]:
name | arity | access_level | n_keys | n_non_keys | n_put_triggers | n_rm_triggers | n_replace_triggers | |
---|---|---|---|---|---|---|---|---|
0 | airport | 11 | normal | 1 | 10 | 0 | 0 | 0 |
1 | contain | 2 | normal | 2 | 0 | 0 | 0 | 0 |
2 | continent | 2 | normal | 1 | 1 | 0 | 0 | 0 |
3 | country | 2 | normal | 1 | 1 | 0 | 0 | 0 |
4 | route | 3 | normal | 2 | 1 | 0 | 0 | 0 |
为了防止误操作,让我们把这些表都锁成只读状态:
[55]:
::access_level read_only airport, contain, continent, country, route
[55]:
status | |
---|---|
0 | OK |
更多关于状态的信息,参见 这一章。
我们先看看关于机场的存储表:
[56]:
?[code, city, desc, region, runways, lat, lon] := *airport{code, city, desc, region, runways, lat, lon}
:limit 5
[56]:
code | city | desc | region | runways | lat | lon | |
---|---|---|---|---|---|---|---|
0 | AAA | Anaa | Anaa Airport | PF-U-A | 1 | -17.352600 | -145.509995 |
1 | AAE | Annabah | Annaba Airport | DZ-36 | 2 | 36.822201 | 7.809170 |
2 | AAL | Aalborg | Aalborg Airport | DK-81 | 2 | 57.092759 | 9.849243 |
3 | AAN | Al Ain | Al Ain International Airport | AE-AZ | 1 | 24.261700 | 55.609200 |
4 | AAQ | Anapa | Anapa Airport | RU-KDA | 1 | 45.002102 | 37.347301 |
哪些机场跑道最多呢?
[57]:
?[code, city, desc, region, runways, lat, lon] := *airport{code, city, desc, region, runways, lat, lon}
:order -runways
:limit 10
[57]:
code | city | desc | region | runways | lat | lon | |
---|---|---|---|---|---|---|---|
0 | DFW | Dallas | Dallas/Fort Worth International Airport | US-TX | 7 | 32.896801 | -97.038002 |
1 | ORD | Chicago | Chicago O'Hare International Airport | US-IL | 7 | 41.978600 | -87.904800 |
2 | AMS | Amsterdam | Amsterdam Airport Schiphol | NL-NH | 6 | 52.308601 | 4.763890 |
3 | BOS | Boston | Boston Logan | US-MA | 6 | 42.364300 | -71.005203 |
4 | DEN | Denver | Denver International Airport | US-CO | 6 | 39.861698 | -104.672997 |
5 | DTW | Detroit | Detroit Metropolitan, Wayne County | US-MI | 6 | 42.212399 | -83.353401 |
6 | ATL | Atlanta | Hartsfield - Jackson Atlanta International Airport | US-GA | 5 | 33.636700 | -84.428101 |
7 | GIS | Gisborne | Gisborne Airport | NZ-GIS | 5 | -38.663300 | 177.977997 |
8 | HLZ | Hamilton | Hamilton International Airport | NZ-WKO | 5 | -37.866699 | 175.332001 |
9 | IAH | Houston | George Bush Intercontinental | US-TX | 5 | 29.984400 | -95.341400 |
数据集里面一共有多少个机场?
[58]:
?[count(code)] := *airport{code}
[58]:
count(code) | |
---|---|
0 | 3504 |
通过以下查询我们可以看出,机场代码的首字母分布并不是均匀的:
[59]:
?[count(initial), initial] := *airport{code}, initial = first(chars(code))
:order initial
[59]:
count(initial) | initial | |
---|---|---|
0 | 212 | A |
1 | 235 | B |
2 | 214 | C |
3 | 116 | D |
4 | 95 | E |
5 | 76 | F |
6 | 135 | G |
7 | 129 | H |
8 | 112 | I |
9 | 80 | J |
10 | 197 | K |
11 | 184 | L |
12 | 228 | M |
13 | 111 | N |
14 | 89 | O |
15 | 203 | P |
16 | 7 | Q |
17 | 121 | R |
18 | 245 | S |
19 | 205 | T |
20 | 77 | U |
21 | 86 | V |
22 | 59 | W |
23 | 28 | X |
24 | 211 | Y |
25 | 49 | Z |
以下是关于机场跑道数量的一些统计:
[60]:
?[count(r), count_unique(r), sum(r), min(r), max(r), mean(r), std_dev(r)] :=
*airport{runways: r}
[60]:
count(r) | count_unique(r) | sum(r) | min(r) | max(r) | mean(r) | std_dev(r) | |
---|---|---|---|---|---|---|---|
0 | 3504 | 7 | 4980.000000 | 1 | 7 | 1.421233 | 0.743083 |
关联“国家”表之后,我们可以找出哪些国家一个机场都没有:
[61]:
?[desc] := *country{code, desc}, not *airport{country: code}
[61]:
desc | |
---|---|
0 | Andorra |
1 | Liechtenstein |
2 | Monaco |
3 | Pitcairn |
4 | San Marino |
“航线”表单独看起来信息量并不大:
[62]:
?[fr, to, dist] := *route{fr, to, dist}
:limit 10
[62]:
fr | to | dist | |
---|---|---|---|
0 | AAA | FAC | 48.000000 |
1 | AAA | MKP | 133.000000 |
2 | AAA | PPT | 270.000000 |
3 | AAA | RAR | 968.000000 |
4 | AAE | ALG | 254.000000 |
5 | AAE | CDG | 882.000000 |
6 | AAE | IST | 1161.000000 |
7 | AAE | LYS | 631.000000 |
8 | AAE | MRS | 477.000000 |
9 | AAE | ORN | 477.000000 |
这个表有三列,分别记录了航线的始发机场、到达机场,以及此航线的实际距离(英里)。这个表记录了图数据里关于边的信息,所以只有在图查询中其中蕴含的内容才能显现出来。
哪些机场没有任何航线:
[63]:
?[code, desc] := *airport{code, desc}, not *route{fr: code}, not *route{to: code}
[63]:
code | desc | |
---|---|---|
0 | AFW | Fort Worth Alliance Airport |
1 | APA | Centennial Airport |
2 | APK | Apataki Airport |
3 | BID | Block Island State Airport |
4 | BVS | Breves Airport |
5 | BWU | Sydney Bankstown Airport |
6 | CRC | Santa Ana Airport |
7 | CVT | Coventry Airport |
8 | EKA | Murray Field |
9 | GYZ | Gruyere Airport |
10 | HFN | Hornafjordur Airport |
11 | HZK | Husavik Airport |
12 | ILG | New Castle Airport |
13 | INT | Smith Reynolds Airport |
14 | ISL | Ataturk International Airport |
15 | KGG | Kédougou Airport |
16 | NBW | Leeward Point Field |
17 | NFO | Mata'aho Airport |
18 | PSY | Stanley Airport |
19 | RIG | Rio Grande Airport |
20 | SFD | San Fernando De Apure Airport |
21 | SFH | San Felipe International Airport |
22 | SXF | Berlin-Schönefeld International Airport *Closed* |
23 | TUA | Teniente Coronel Luis a Mantilla Airport |
24 | TWB | Toowoomba Airport |
25 | TXL | Berlin, Tegel International Airport *Closed* |
26 | VCV | Southern California Logistics Airport |
27 | YEI | Bursa Yenişehir Airport |
航线最多的机场:
[64]:
route_count[fr, count(fr)] := *route{fr}
?[code, n] := route_count[code, n]
:sort -n
:limit 5
[64]:
code | n | |
---|---|---|
0 | FRA | 310 |
1 | IST | 309 |
2 | CDG | 293 |
3 | AMS | 283 |
4 | MUC | 270 |
从欧盟到美国一共有多少条航线?
[65]:
routes[unique(r)] := *contain['EU', fr],
*route{fr, to},
*airport{code: to, country: 'US'},
r = [fr, to]
?[n] := routes[rs], n = length(rs)
[65]:
n | |
---|---|
0 | 435 |
美国有多少个机场,有来自欧盟的航线?
[66]:
?[count_unique(to)] := *contain['EU', fr],
*route{fr, to},
*airport{code: to, country: 'US'}
[66]:
count_unique(to) | |
---|---|
0 | 45 |
英国伦敦每个机场都有多少条航线?
[67]:
?[code, count(code)] := *airport{code, city: 'London', region: 'GB-ENG'}, *route{fr: code}
[67]:
code | count(code) | |
---|---|---|
0 | LCY | 51 |
1 | LGW | 232 |
2 | LHR | 221 |
3 | LTN | 130 |
4 | STN | 211 |
这里我们必须指明 GB-ENG
区域,因为世界上不止一个城市叫做伦敦。
从伦敦起飞,转机两次,能到多少个不同的机场?
[68]:
lon_uk_airports[code] := *airport{code, city: 'London', region: 'GB-ENG'}
one_hop[to] := lon_uk_airports[fr], *route{fr, to}, not lon_uk_airports[to];
?[count_unique(a3)] := one_hop[a2], *route{fr: a2, to: a3}, not lon_uk_airports[a3];
[68]:
count_unique(a3) | |
---|---|
0 | 2353 |
不转机,从伦敦盖特威克机场能飞到的最远的城市(不是机场)有哪些?
[69]:
?[city, dist] := *route{fr: 'LGW', to, dist},
*airport{code: to, city}
:order -dist
:limit 10
[69]:
city | dist | |
---|---|---|
0 | Buenos Aires | 6908.000000 |
1 | Singapore | 6751.000000 |
2 | Langkawi | 6299.000000 |
3 | Duong Dong | 6264.000000 |
4 | Taipei | 6080.000000 |
5 | Port Louis | 6053.000000 |
6 | Rayong | 6008.000000 |
7 | Cape Town | 5987.000000 |
8 | Hong Kong | 5982.000000 |
9 | Shanghai | 5745.000000 |
在格林威治子午线经度 0.1 之内的机场有哪些?
[70]:
?[code, desc, lon, lat] := *airport{lon, lat, code, desc}, lon > -0.1, lon < 0.1
[70]:
code | desc | lon | lat | |
---|---|---|---|---|
0 | CDT | Castellon De La Plana Airport | 0.026111 | 39.999199 |
1 | LCY | London City Airport | 0.055278 | 51.505278 |
2 | LDE | Tarbes-Lourdes-Pyrénées Airport | -0.006439 | 43.178699 |
3 | LEH | Le Havre Octeville Airport | 0.088056 | 49.533901 |
以伦敦希思罗机场为中心画一个方块,里面包含的机场有哪些?
[71]:
h_box[lon, lat] := *airport{code: 'LHR', lon, lat}
?[code, desc] := h_box[lhr_lon, lhr_lat], *airport{code, lon, lat, desc},
abs(lhr_lon - lon) < 1, abs(lhr_lat - lat) < 1
[71]:
code | desc | |
---|---|---|
0 | LCY | London City Airport |
1 | LGW | London Gatwick |
2 | LHR | London Heathrow |
3 | LTN | London Luton Airport |
4 | SOU | Southampton Airport |
5 | STN | London Stansted Airport |
下面我们来做点球面几何:SFO
和 NRT
这两个机场,与地球中心所构成的角度是多少?
[72]:
?[deg_diff] := *airport{code: 'SFO', lat: a_lat, lon: a_lon},
*airport{code: 'NRT', lat: b_lat, lon: b_lon},
deg_diff = rad_to_deg(haversine_deg_input(a_lat, a_lon, b_lat, b_lon))
[72]:
deg_diff | |
---|---|
0 | 73.992112 |
之前我们提到过,在 Cozo 中,聚合与递归的结合使其查询语句有了更加强大的表达力。下面这个例子就展示了这种表达力。
我们需要找出两个机场之间的最短路线距离。最朴素的方法是列举这两个机场之间的所有路线,然后对结果应用最小聚合。然而两个机场之间一般来说有无穷多条路线,因为我们可以绕着圈儿飞,造成航线上的死循环。
所以这种朴素的方法不可行。那我们试试递归式思考:如果我们已经知道了所有机场之间的所有最短路线,我们就可以推导出一个最短路线满足的方程:a 与 b 之间的最短路线,要么是一条直飞航线的距离,要么是从 a 到某个 c 之间的最短路线的距离与从 c 到 d 的直飞航线的距离之和。这样以来,我们需要考虑的 a 与 b 之间的情况数量就小得多,而且是有限的。我们对这些情况来做最小聚合。
把上面这个思路直接写出来,就可以得到以下计算 LHR
机场与 YPO
机场之间最短路线的查询:
[73]:
shortest[b, min(dist)] := *route{fr: 'LHR', to: b, dist}
# 从 'LHR' 出发,列举直航航线到达的机场 b
shortest[b, min(dist)] := shortest[c, d1], # 已知的到达 c 的最短路径
*route{fr: c, to: b, dist: d2}, # 从 c 到 d 的直航航线
dist = d1 + d2 # 新航线的距离
?[dist] := shortest['YPO', dist] # 从所有答案中提取关于 YPO 的答案
# 为什么这个例子选 YPO?因为它是最难到达的机场之一
[73]:
dist | |
---|---|
0 | 4147.000000 |
这里有一点需要注意:如果用下面的方法来写这个查询(不要尝试运行):
shortest[a, b, min(dist)] := *route{fr: a, to: b, dist}
shortest[a, b, min(dist)] := shortest[a, c, d1],
*route{fr: c, to: b, dist: d2},
dist = d1 + d2
?[dist] := shortest['LHR', 'YPO', dist]
这个查询从语义上来说和之前的是等价的,但是跑起来就像进了死循环一样长时间不返回结果。为什么?
在这个新的查询中,内联规则 shortest
包含了所有机场间的最短路线。如果这个规则不含聚合操作,则 Cozo 在编译查询语句时会发现其实不需要计算所有的中间结果就能得出答案,然后使用一种叫做“魔法集重写”的方法优化掉这些中间结果(详见 此章)。但是这个优化不能用于包含聚合操作的查询。因此,系统会尝试计算一千三百多万个机场组合之间的最短距离,显然无法很快返回结果。
如果聚合加递归的查询迟迟不返回结果,我们可以粗略估算一下与聚合递归规则相关的中间结果大概有多大。如果像这个例子似的特别大,那我们就需要通过手动改写查询来避免它。
图算法巡礼#
现在我们用图算法来研究这个图。如前所述,浏览器中运行的 Cozo 并没有图算法模块,下面的例子,需要使用原生的 Cozo 实现(例如 Python 的)来运行。
寻路是最常用的图算法,因此 Cozo 有几个寻路的固定规则:
[74]:
starting[] <- [['LHR']]
goal[] <- [['YPO']]
?[starting, goal, distance, path] <~ ShortestPathDijkstra(*route[], starting[], goal[])
[74]:
starting | goal | distance | path | |
---|---|---|---|---|
0 | LHR | YPO | 4147.000000 | ['LHR', 'YUL', 'YVO', 'YKQ', 'YMO', 'YFA', 'ZKE', 'YAT', 'YPO'] |
这比直接拿内联规则写不但更简单,效率也高不少,而且直接就给出了具体的最短路径。
以下算法计算最短的 10 条路径:
[75]:
starting[] <- [['LHR']]
goal[] <- [['YPO']]
?[starting, goal, distance, path] <~ KShortestPathYen(*route[], starting[], goal[], k: 10)
[75]:
starting | goal | distance | path | |
---|---|---|---|---|
0 | LHR | YPO | 4147.000000 | ['LHR', 'YUL', 'YVO', 'YKQ', 'YMO', 'YFA', 'ZKE', 'YAT', 'YPO'] |
1 | LHR | YPO | 4150.000000 | ['LHR', 'DUB', 'YUL', 'YVO', 'YKQ', 'YMO', 'YFA', 'ZKE', 'YAT', 'YPO'] |
2 | LHR | YPO | 4164.000000 | ['LHR', 'YUL', 'YMT', 'YKQ', 'YMO', 'YFA', 'ZKE', 'YAT', 'YPO'] |
3 | LHR | YPO | 4167.000000 | ['LHR', 'DUB', 'YUL', 'YMT', 'YKQ', 'YMO', 'YFA', 'ZKE', 'YAT', 'YPO'] |
4 | LHR | YPO | 4187.000000 | ['LHR', 'MAN', 'DUB', 'YUL', 'YVO', 'YKQ', 'YMO', 'YFA', 'ZKE', 'YAT', 'YPO'] |
5 | LHR | YPO | 4202.000000 | ['LHR', 'IOM', 'DUB', 'YUL', 'YVO', 'YKQ', 'YMO', 'YFA', 'ZKE', 'YAT', 'YPO'] |
6 | LHR | YPO | 4204.000000 | ['LHR', 'MAN', 'DUB', 'YUL', 'YMT', 'YKQ', 'YMO', 'YFA', 'ZKE', 'YAT', 'YPO'] |
7 | LHR | YPO | 4209.000000 | ['LHR', 'YUL', 'YMT', 'YNS', 'YKQ', 'YMO', 'YFA', 'ZKE', 'YAT', 'YPO'] |
8 | LHR | YPO | 4211.000000 | ['LHR', 'MAN', 'IOM', 'DUB', 'YUL', 'YVO', 'YKQ', 'YMO', 'YFA', 'ZKE', 'YAT', 'YPO'] |
9 | LHR | YPO | 4212.000000 | ['LHR', 'DUB', 'YUL', 'YMT', 'YNS', 'YKQ', 'YMO', 'YFA', 'ZKE', 'YAT', 'YPO'] |
上面这些算法都要求先把整个图编译成内存中的数据结构再进行运算。如果你的图很大,顶点很多,你也能给出一个相对靠谱的距离下限,下面这个 A* 算法可能会更快:
[76]:
code_lat_lon[code, lat, lon] := *airport{code, lat, lon}
starting[code, lat, lon] := code = 'LHR', *airport{code, lat, lon};
goal[code, lat, lon] := code = 'YPO', *airport{code, lat, lon};
?[] <~ ShortestPathAStar(*route[],
code_lat_lon[node, lat1, lon1],
starting[],
goal[goal, lat2, lon2],
heuristic: haversine_deg_input(lat1, lon1, lat2, lon2) * 3963);
[76]:
_0 | _1 | _2 | _3 | |
---|---|---|---|---|
0 | LHR | YPO | 4147.000000 | ['LHR', 'YUL', 'YVO', 'YKQ', 'YMO', 'YFA', 'ZKE', 'YAT', 'YPO'] |
使用 A* 算法需要更多的设置:我们得提取机场的经纬度,并用两个机场的经纬度算出这两个机场之间的球面距离作为飞行距离的下限。上面的数字 3963(英里)是地球的半径。
下面我们用 PageRank 来找出最重要的机场:
[77]:
rank[code, score] <~ PageRank(*route[a, b])
?[code, desc, score] := rank[code, score], *airport{code, desc}
:limit 10;
:order -score
[77]:
code | desc | score | |
---|---|---|---|
0 | IST | Istanbul International Airport | 0.004889 |
1 | DFW | Dallas/Fort Worth International Airport | 0.004696 |
2 | ORD | Chicago O'Hare International Airport | 0.004452 |
3 | DEN | Denver International Airport | 0.004252 |
4 | PEK | Beijing Capital International Airport | 0.004044 |
5 | FRA | Frankfurt am Main | 0.004027 |
6 | ATL | Hartsfield - Jackson Atlanta International Airport | 0.004022 |
7 | DXB | Dubai International Airport | 0.004002 |
8 | CDG | Paris Charles de Gaulle | 0.003998 |
9 | DME | Moscow, Domodedovo International Airport | 0.003817 |
下面的查询计算的是中心度。中心度的算法复杂度高,计算需要一些时间:
[78]:
centrality[code, score] <~ BetweennessCentrality(*route[a, b])
?[code, desc, score] := centrality[code, score], *airport{code, desc}
:limit 10;
:order -score
[78]:
code | desc | score | |
---|---|---|---|
0 | ANC | Anchorage Ted Stevens | 1074868.250000 |
1 | KEF | Reykjavik, Keflavik International Airport | 928450.437500 |
2 | HEL | Helsinki Ventaa | 581588.500000 |
3 | PEK | Beijing Capital International Airport | 532021.062500 |
4 | DEL | Indira Gandhi International Airport | 472979.968750 |
5 | IST | Istanbul International Airport | 457882.156250 |
6 | PKC | Yelizovo Airport | 408571.000000 |
7 | MSP | Minneapolis-St.Paul International Airport | 396433.250000 |
8 | LAX | Los Angeles International Airport | 393309.968750 |
9 | DEN | Denver International Airport | 374339.531250 |
中心度高的机场,如果停止运营,将会对整个航线网络造成最大的影响。这个指标很重要,然而我们也可以看到,对于稍微大一点的数据集,计算这个指标就比较慢了。
使用社区检测,我们可以将原始的图折叠成一个 超级图 并将其存为存储表:
[79]:
community[detailed_cluster, code] <~ CommunityDetectionLouvain(*route[a, b])
?[code, cluster, detailed_cluster] := community[detailed_cluster, code], cluster = first(detailed_cluster)
:replace community {code => cluster, detailed_cluster}
[79]:
status | |
---|---|
0 | OK |
我们可以查询某个具体的机场包含在哪个超级节点中。以下例子表明,和预想的一样,伦敦盖特威克机场的超级节点主要由英国和其他欧洲城市的机场组成:
[80]:
community[code] := *community{code: 'LGW', cluster}, *community{code, cluster}
?[country, count(code)] :=
community[code],
*airport{code, desc, country: country_code},
*country{code: country_code, desc: country},
:order -count(code)
:limit 5
[80]:
country | count(code) | |
---|---|---|
0 | United Kingdom | 54 |
1 | France | 50 |
2 | Norway | 49 |
3 | Spain | 40 |
4 | Greece | 38 |
肯尼迪机场的超级节点则主要包括美国的机场:
[81]:
community[code] := *community{code: 'JFK', cluster}, *community{code, cluster}
?[country, count(code)] :=
community[code],
*airport{code, desc, country: country_code},
*country{code: country_code, desc: country},
:order -count(code)
:limit 5
[81]:
country | count(code) | |
---|---|---|
0 | United States | 444 |
1 | Canada | 111 |
2 | Brazil | 108 |
3 | Mexico | 57 |
4 | Colombia | 50 |
当然这个结果并不是由地理划分的。比如法兰克福机场在德国:
[82]:
?[desc, country_desc] := *airport{code: 'FRA', desc, country: country_code}, *country{code: country_code, desc: country_desc}
[82]:
desc | country_desc | |
---|---|---|
0 | Frankfurt am Main | Germany |
但这是其超级节点:
[83]:
community[code] := *community{code: 'FRA', cluster}, *community{code, cluster}
?[country, count(code)] :=
community[code],
*airport{code, desc, country: country_code},
*country{code: country_code, desc: country},
:order -count(code)
:limit 5
[83]:
country | count(code) | |
---|---|---|
0 | United States | 444 |
1 | Canada | 111 |
2 | Brazil | 108 |
3 | Mexico | 57 |
4 | Colombia | 50 |
德国甚至不在前五位里。实际上法兰克福机场和肯尼迪机场的超级节点是同一个。在这里,重要的是机场间的航线关系,而不是纯粹的地理。更好的例子是下面这个:
[84]:
community[code] := *community{code: 'SIN', cluster}, *community{code, cluster}
?[country, count(code)] :=
community[code],
*airport{code, desc, country: country_code},
*country{code: country_code, desc: country},
:order -count(code)
:limit 5
[84]:
country | count(code) | |
---|---|---|
0 | China | 216 |
1 | Australia | 125 |
2 | Indonesia | 68 |
3 | Japan | 65 |
4 | Philippines | 40 |
看起来 SIN
好像是个中国的机场,但是:
[85]:
?[desc, country_desc] := *airport{code: 'SIN', desc, country: country_code}, *country{code: country_code, desc: country_desc}
[85]:
desc | country_desc | |
---|---|---|
0 | Singapore, Changi International Airport | Singapore |
实际上它是新加坡樟宜机场。
接下来我们把整个航线关系折叠到超级节点上:
[86]:
?[fr_cluster, to_cluster, count(dist), sum(dist)] := *route{fr, to, dist},
*community{code: fr, cluster: fr_cluster},
*community{code: to, cluster: to_cluster}
:replace super_route {fr_cluster, to_cluster => n_routes=count(dist), total_distance=sum(dist)}
[86]:
status | |
---|---|
0 | OK |
我们可以看到,在这个折叠后的关系中,“对角线”关系 fr_cluster == to_cluster
,不管是航线数量还是总距离,值都是最大的:
[87]:
?[fr_cluster, to_cluster, n_routes, total_distance] := *super_route{fr_cluster, to_cluster, n_routes, total_distance}, fr_cluster < 2
[87]:
fr_cluster | to_cluster | n_routes | total_distance | |
---|---|---|---|---|
0 | 0 | 0 | 9041 | 8933554.000000 |
1 | 0 | 1 | 434 | 1695379.000000 |
2 | 0 | 2 | 228 | 761661.000000 |
3 | 0 | 3 | 530 | 1681865.000000 |
4 | 0 | 4 | 163 | 391892.000000 |
5 | 0 | 8 | 3 | 300.000000 |
6 | 0 | 11 | 2 | 283.000000 |
7 | 0 | 19 | 1 | 238.000000 |
8 | 0 | 21 | 2 | 705.000000 |
9 | 0 | 22 | 1 | 975.000000 |
10 | 1 | 0 | 434 | 1696858.000000 |
11 | 1 | 1 | 4474 | 5142452.000000 |
12 | 1 | 2 | 1160 | 1492734.000000 |
13 | 1 | 3 | 526 | 1724591.000000 |
14 | 1 | 4 | 223 | 361986.000000 |
15 | 1 | 9 | 1 | 808.000000 |
折叠后的超级图很小,所以所有图算法都可以瞬间返回结果:
[88]:
?[cluster, score] <~ PageRank(*super_route[])
:order -score
:limit 5
[88]:
cluster | score | |
---|---|---|
0 | 3 | 0.173309 |
1 | 0 | 0.093072 |
2 | 1 | 0.053465 |
3 | 2 | 0.053389 |
4 | 4 | 0.044654 |
对这些结果,我们可以试着给出解释。例如,对于以上结果一个朴素的解释是,北美仍然是世界上最发达的地区,然后东亚第二名,南亚第三名,欧洲第四名(三、四名之间差距很小)。
“硬派”地导入数据#
之前我们导入了专门制作的 JSON 文件数据。接下来我们介绍如何使用 Cozo 直接导入 CSV 格式的原始数据。
我们先把之前的表解锁,然后删掉:
[89]:
::access_level normal airport, contain, continent, country, route
[89]:
status | |
---|---|
0 | OK |
[92]:
::remove airport, contain, continent, country, route, community, super_route
[92]:
status | |
---|---|
0 | OK |
接下来我们定义一些变量,变量里的值是需要导入的文件的位置(注释掉的行内容是本地文件):
[94]:
%cozo_set AIR_ROUTES_NODES_URL 'https://raw.githubusercontent.com/cozodb/cozo/dev/cozo-core/tests/air-routes-latest-nodes.csv'
%cozo_set AIR_ROUTES_EDGES_URL 'https://raw.githubusercontent.com/cozodb/cozo/dev/cozo-core/tests/air-routes-latest-edges.csv'
# %cozo_set AIR_ROUTES_NODES_URL 'file://./../../cozo/cozo-core/tests/air-routes-latest-nodes.csv'
# %cozo_set AIR_ROUTES_EDGES_URL 'file://./../../cozo/cozo-core/tests/air-routes-latest-edges.csv'
首先我们导入机场:
[95]:
res[idx, label, typ, code, icao, desc, region, runways, longest, elev, country, city, lat, lon] <~
CsvReader(types: ['Int', 'Any', 'Any', 'Any', 'Any', 'Any', 'Any', 'Int?', 'Float?', 'Float?', 'Any', 'Any', 'Float?', 'Float?'],
url: $AIR_ROUTES_NODES_URL,
has_headers: true)
?[code, icao, desc, region, runways, longest, elev, country, city, lat, lon] :=
res[idx, label, typ, code, icao, desc, region, runways, longest, elev, country, city, lat, lon],
label == 'airport'
:replace airport {
code: String
=>
icao: String,
desc: String,
region: String,
runways: Int,
longest: Float,
elev: Float,
country: String,
city: String,
lat: Float,
lon: Float
}
[95]:
status | |
---|---|
0 | OK |
工具规则 CsvReader
的作用是下载 CSV 文件,并根据设置将其内容解析为一个表。我们储存表的时候给出了所有列的类型,并将机场代码作为主键。
接下来导入国家:
[96]:
res[idx, label, typ, code, icao, desc] <~
CsvReader(types: ['Int', 'Any', 'Any', 'Any', 'Any', 'Any'],
url: $AIR_ROUTES_NODES_URL,
has_headers: true)
?[code, desc] :=
res[idx, label, typ, code, icao, desc],
label == 'country'
:replace country {
code: String
=>
desc: String
}
[96]:
status | |
---|---|
0 | OK |
大陆:
[97]:
res[idx, label, typ, code, icao, desc] <~
CsvReader(types: ['Int', 'Any', 'Any', 'Any', 'Any', 'Any'],
url: $AIR_ROUTES_NODES_URL,
has_headers: true)
?[idx, code, desc] :=
res[idx, label, typ, code, icao, desc],
label == 'continent'
:replace continent {
code: String
=>
desc: String
}
[97]:
status | |
---|---|
0 | OK |
由于原始数据中每个机场的数字 ID 不是我们想要的(我们直接拿机场代码作为主键),而原始数据的航线通过这些数字表示,我们先建立一个主键转换表:
[98]:
res[idx, label, typ, code] <~
CsvReader(types: ['Int', 'Any', 'Any', 'Any'],
url: $AIR_ROUTES_NODES_URL,
has_headers: true)
?[idx, code] :=
res[idx, label, typ, code],
:replace idx2code { idx => code }
[98]:
status | |
---|---|
0 | OK |
接下来的表储存地理上的包含关系:
[99]:
res[] <~
CsvReader(types: ['Int', 'Int', 'Int', 'String'],
url: $AIR_ROUTES_EDGES_URL,
has_headers: true)
?[entity, contained] :=
res[idx, fr_i, to_i, typ],
typ == 'contains',
*idx2code[fr_i, entity],
*idx2code[to_i, contained]
:replace contain { entity: String, contained: String }
[99]:
status | |
---|---|
0 | OK |
最后,我们使用转换表导入航线(一共大概 6 万多条航线):
[100]:
res[] <~
CsvReader(types: ['Int', 'Int', 'Int', 'String', 'Float?'],
url: $AIR_ROUTES_EDGES_URL,
has_headers: true)
?[fr, to, dist] :=
res[idx, fr_i, to_i, typ, dist],
typ == 'route',
*idx2code[fr_i, fr],
*idx2code[to_i, to]
:replace route { fr: String, to: String => dist: Float }
[100]:
status | |
---|---|
0 | OK |
导入完毕,转换表可以删了:
[101]:
::remove idx2code
[101]:
status | |
---|---|
0 | OK |
最后,让我们确认一下确实所有表都导入了:
[102]:
::relations
[102]:
name | arity | access_level | n_keys | n_non_keys | n_put_triggers | n_rm_triggers | n_replace_triggers | |
---|---|---|---|---|---|---|---|---|
0 | airport | 11 | normal | 1 | 10 | 0 | 0 | 0 |
1 | contain | 2 | normal | 2 | 0 | 0 | 0 | 0 |
2 | continent | 2 | normal | 1 | 1 | 0 | 0 | 0 |
3 | country | 2 | normal | 1 | 1 | 0 | 0 | 0 |
4 | route | 3 | normal | 2 | 1 | 0 | 0 | 0 |
教程至此结束!