Prolog子句的按需索引技术详解

### Prolog子句的按需索引技术详解 #### 1. 静态谓词的按需索引 对于静态谓词，编译器掌握所有子句及其头部参数形状的完整信息。充分利用这些信息进行编译优化是可行且必要的，下面将按有效性和实现复杂度递增的方案展开介绍。 ##### 1.1 任意参数索引的简单WAM扩展 先考虑仅由Datalog事实组成的谓词索引情况，这在所有外延数据库谓词中很常见，索引效果显著且必要。 参考示例，图1(b)的索引代码在第一个参数为变量的调用时会产生小成本（即执行常量开关指令），但在第一个参数绑定的调用中会有回报。然而，当第一个参数是自由变量且其他参数绑定时，会创建选择点，使用try - retry - trust链，执行会遍历所有子句的代码，对于大数据集效率很低。而图1(d)的相对简单方案能改善这一情况。在常量开关指令之后，为每个剩余参数静态生成常量按需索引（dindex on constant）指令。该指令工作方式如下： - 若参数`ri`是自由变量，执行继续到下一条指令。 - 否则，按需索引启动。抽象机扫描子句的WAM代码，为相应参数的值创建索引表。因为指令将需要索引的子句数量`N`和谓词的元数`A`作为参数，对于Datalog事实，这些信息足够。由于子句的WAM字节码结构规则，能快速创建索引表。创建完成后，常量按需索引指令转换为常量开关指令，执行继续。 图2展示了按需索引后为示例创建的索引表`T2`以及调用模式为`(out,in,?)`时的索引代码，第二个参数的索引已创建。该方案的主要优点是简单，编译代码不比基于WAM的编译器生成的代码大很多，若运行时按需索引不必要，额外开销极小。 ```plaintext switch on constant r1 5 T1 switch on constant r2 5 T2 dindex on constant r3 5 3 try L1 retry L2 retry L3 retry L4 trust L5 T1: Hash Table Info d1 try L1 trust L2 d2 try L3 trust L4 d3 jump L5 T2: Hash Table Info salmonella try L1 trust L3 salmonella n jump L2 cytrogen ca try L4 trust L5 ``` 优化方面，由于处理的是静态代码，有一些简单优化机会。若静态确定某些参数不会有`in`模式的调用或区分度不足，可避免为其生成常量按需索引指令；若知道某些参数更可能以`in`模式使用，可将其常量按需索引指令置于其他参数之前，因为索引指令的顺序无关紧要。 ##### 1.2 从任意参数索引到多参数索引 上一节的方案仅提供单参数索引，不过所需基础设施已具备，可直接实现任意固定顺序的多参数按需索引。 编译器确切知道每个查询在第一个参数有特定符号时需尝试的子句集。对于多参数按需索引，编译器可为每个哈希桶添加适当的按需索引指令，而非仅生成try - retry - trust指令。示例中，表`T1`包含四个常量按需索引指令。对于无或只有一个替代方案的哈希桶，无需对剩余参数进行按需索引。图3展示了查询执行后的哈希表状态。 ```plaintext switch on constant r1 5 T1 switch on constant r2 5 T2 dindex on constant r3 5 3 try L1 retry L2 retry L3 retry L4 trust L5 T1: Hash Table Info d1 dindex on constant r2 2 3 dindex on constant r3 2 3 try L1 trust L2 d2 dindex on constant r2 2 3 switch on constant r3 2 T3 try L3 trust L4 d3 jump L5 T2: Hash Table Info salmonella dindex on constant r3 2 3 try L1 trust L3 salmonella n jump L2 cytrogen ca dindex on constant r3 2 3 try L4 trust L5 T3: Hash Table Info p jump L3 n jump L4 ``` 实现方面，图3中常量按需索引指令的整数2表示要索引的子句数量，据此创建适当大小的索引表。通过扫描try - retry - trust指令的标签获取子句，根据标签的字节码偏移获取哈希符号。因此，多参数按需索引容易实现，索引Datalog事实时索引表创建极快。 ##### 1.3 超越Datalog及其他实现问题 对含函数符号的按需子句进行索引难度不会显著增加，但需以下扩展： 1. 除常量按需索引指令，还需项按需索引（dindex on term）和结构按需索引（dindex on structure）指令，它们是WAM的项开关和结构开关的按需索引对应指令。 2. 由于子句头部的字节码结构不一定规则，抽象机需能“遍历”字节码指令并恢复用于索引的符号，编写这样的代码遍历过程不难。 3. 对某些子句中包含无约束变量的位置进行索引较棘手。WAM需对这些子句进行分组，否则会为该参数创建两个选择点。不过，该问题已有解决方案，可参考相关论文并应用于按需索引。简单实现中，可跳过含变量位置的按需索引。 设计决策方面