演绎数据库中的递归查询评估

### 演绎数据库中的递归查询评估 在演绎数据库中，递归查询的评估是一个重要且具有挑战性的问题。传统的评估方法存在重复推理和不必要推理等问题，下面将详细介绍相关的解决方案。 #### 1. 物料清单（BOM）关系计算 在计算BOM关系时，首先会得到一个包含零件、子零件和数量的实例，如下表所示： | part | subpart | qty | | --- | --- | --- | | trike | frame | 1 | | trike | seat | 1 | | frame | seat | 1 | | frame | pedal | 2 | | seat | cover | 1 | | trike | seat | 1 | | trike | pedal | 2 | | trike | cover | 1 | | frame | cover | 1 | | trike | cover | 1 | 经过多集分组后，会得到一个临时关系实例，对该临时关系第三列的多集应用SUM操作，就可以得到TotParts的实例。 #### 2. 递归查询评估的挑战 评估递归查询时，除了非递归查询的问题外，新引入的不动点操作带来了额外的困难。一种直接的方法是通过反复应用规则来计算不动点，但这种方法存在两个主要缺点： - **重复推理**：在不同的迭代中会重复进行相同的推理，即使用相同的规则和相同的表元组来推断相同的元组。 - **不必要推理**：例如，当我们只想查找一个轮子的组件时，计算整个组件表是浪费的，没有利用查询中的信息。 #### 3. 无重复推理的不动点评估 通过反复应用所有规则来计算不动点的方法称为朴素不动点评估。这种方法虽然能保证计算出最小不动点，但每次应用规则都会重复之前应用该规则时所做的所有推理。 例如，对于规则： ``` Components(Part, Subpart) :- Assembly(Part, Part2, Qty), Components(Part2, Subpart). ``` 第一次应用该规则时，Components表包含Assembly在前两个字段上的投影。第二次应用规则时，会产生新的推理，但也会重复第一次应用规则时的推理。 为了解决这个问题，引入了半朴素不动点评估方法。该方法通过引入一个新的关系（如delta Components）来跟踪在最近一次应用递归规则时首次生成的Components元组。在后续应用递归规则时，只使用delta Components中的元组，避免了重复推理。 半朴素不动点评估的步骤如下： 1. 第一次应用递归规则，将生成的Components元组放入delta Components中。 2. 后续应用递归规则时，只考虑delta Components中的元组。 3. 更新delta Components，使其只包含本次迭代生成的新元组。 4. 重复上述步骤，直到没有新的元组生成。 半朴素不动点评估与朴素不动点评估相比，有两个重要区别： - 为每个递归谓词维护一个delta版本，以跟踪在最近一次迭代中为该谓词生成的元组。 - 重写原始程序规则，确保每个推理至少使用一个delta元组，保证推理不会在早期迭代中进行。 #### 4. 避免无关推理的选择推送 对于非递归视图定义，如果我们只想要满足额外选择条件的元组，可以将选择操作添加到计划的最后，并利用关系代数变换将选择操作提前，以限制计算。但对于递归定义的查询，问题更为复杂。 以SameLevel程序为例： ``` SameLevel(S1, S2) :- Assembly(P1, S1, Q1), Assembly(P1, S2, Q2). SameLevel(S1, S2) :- Assembly(P1, S1, Q1), SameLevel(P1, P2), Assembly(P2, S2, Q2). ``` 如果我们想查找第一个字段等于spoke的所有SameLevel元组，不能只计算第一个字段为spoke的元组，因为SameLevel元组可以用于计算其他SameLevel元组。 为了解决这个问题，定义了一个新的表Magic SameLevel，该表中的每个元组标识一个值m，为了回答给定的查询，我们需要计算所有第一个列中包含m的SameLevel元组。 Magic SameLevel的规则如下： ``` Magic SameLevel(P1) :- Magic SameLevel(S1), Assembly(P1, S1, Q1). Magic SameLevel(spoke) :- . ``` 通过使用Magic SameLevel表作为过滤器，可以限制计算，减少不必要的推理。新的SameLevel规则如下： ``` SameLevel(S1, S2) :- Magic SameLevel(S1), Assembly(P1, S1, Q1), Assembly(P2, S2, Q2). SameLevel(S1, S2) :- Magic SameLevel(S1), Assembly(P1, S1, Q1), SameLevel(P1, P2), Assembly(P2, S2, Q2). ``` #### 5. 魔集算法 魔集算法可以应用于任何Datalog程序，其输入包括程序和查询模式，输出是一个重写后的程序。该算法的步骤如下： 1. **生成修饰程序**：重写程序，使查询和子查询的模式明确。 2. **添加魔过滤器**：通过在修饰程序的每个规则的主体中添加一个魔条件，对该规则生成的元组集进行过滤。 3. **定义魔表**：为每个在修饰程序规则主体中出现的表R创建一个规则来定义Magic R表。 当提出查询时，将相应的魔元组添加到重写后的程序中，并使用半朴素评估方法计算程序的最小不动点。 以SameLevel程序为例，详细介绍魔集算法的步骤： - **修饰程序**：考虑查询模式SameLevelbf，生成修饰程序P ad。对于规则： ``` SameLevelbf(S1, S2) :- Assembly(P1, S1, Q1), SameLevel(P1, P2), Assembly(P2, S2, Q2). ``` 从左到右处理规则主体，遇到第一个递归谓词时，将包含常量或在其左侧出现的变量的列标记为b，其余列标记为f，并将该模式添加到可达模式集中，修改规则如下： ``` SameLevelbf(S1, S2) :- Assembly(P1, S1, Q1), SameLevelbf(P1, P2), Assembly(P2, S2, Q2). ``` 重复上述过程，直到为每个可达查询模式生成修饰后的规则。 - **添加魔过滤器**：在修饰程序的每个规则中添加魔过滤器，得到重写后的程序： ``` SameLevelbf(S1, S2) :- Magic SameLevelbf(S1), Assembly(P1, S1, Q1), Assembly(P2, S2, Q2). SameLevelbf(S1, S2) :- Magic SameLevelbf(S1), Assembly(P1, S1, Q1), SameLevelbf(P1, P2), Assembly(P2, S2, Q2). ``` - **定义魔过滤器表**：从修饰程序规则主体中每个递归谓词的出现处生成一个规则来定义魔谓词。例如，对于递归规则： ``` SameLevelbf(S1, S2) :- Magic SameLevelbf(S1), Assembly(P1, S1, Q1), Magic SameLevelbf(P1). ``` 经过处理后得到： ``` Magic SameLevelbf(P1) :- Magic SameLevelbf(S1), Assembly(P1, S1, Q1). ``` 魔集算法在计算相关嵌套SQL查询时非常有效，即使没有递归，也被许多商业DBMS用于此目的。 下面是魔集算法的流程图： ```mermaid graph TD; A[输入程序和查询模式] --> B[生成修饰程序]; B --> C[添加魔过滤器]; C --> D[定义魔表]; D --> E[添加魔元组到重写程序]; E --> F[使用半朴素评估计算最小不动点]; ``` #### 6. 总结 通过半朴素不动点评估和魔集算法，可以有效解决递归查询评估中的重复推理和不必要推理问题，提高查询评估的效率。在实际应用中，可以根据具体情况选择合适的方法来优化查询性能。 #### 7. 练习 以下是一些相关的练习，帮助读者更好地理解和应用上述概念： 1. 考虑Flights关系，用Datalog和SQL:1999语法编写各种查询，如查找从麦迪逊出发的所有航班的航班号等。 2.