如何使用多个规则以声明方式转换 Prolog 中的数据结构
How to transform data structures in Prolog using multiple rules, declaratively
我想找到一种在给定 constraints/transformation 规则集的 Prolog 中转换数据结构的方法。
励志榜样
假设我们要validate/enrichSQL根据一些规则进行查询。
我们只对简单的 SQL 查询感兴趣，现在只考虑 WHERE/GROUP BY 子句，形式为 WHERE filter(a) AND filter(b) AND ... GROUP BY c,d,...（其中
a、b、c、d 是列名）。
此类查询的模型可能如下所示：
[filter(a), filter(b), group(c), group(d)]
我们可能有这样的规则：
- 列
a 必须出现在过滤器或分组中（但只能出现一次）。如果不存在，通过添加到过滤器和分组来生成 2 个解决方案。
- 分组不能为空（如果为空，按列添加默认分组
a）。
- 不能超过 2 个分组（如果超过 2 个则通过删除额外的分组生成多个解决方案）。
- 过滤器和分组中都不能存在列（如果发生这种情况，则通过从过滤器和分组中删除列来生成 2 个解决方案）。
- 等等
一些规则显然是“冲突的”（例如，如果我们添加强制分组，我们可能会超过分组的最大数量，并且将不得不产生多个解决方案或根本不产生解决方案，具体取决于特定规则）。
我试过的
到目前为止我只能想出这样的东西：
transform(In, Out) :-
has_mandatory_grouping(In, Out1),
limited_grouping_count(Out1, Out2),
another_rule(Out2, Out3),
...
last_rule(OutN, Out).
has_mandatory_grouping(In, Out) :- contains(In, group(a)) -> Out = In; Out = [group(a)|In].
limited_grouping_count(In, Out) :- (length(In, L), L > 2) -> subset2(Out, In), Out = [_,_], contains(Out, group(a)); Out = In.
...
所以基本上是一组有序的步骤，每个步骤都应用一些逻辑来生成要传递给下游的新结构。
我不喜欢这种方法的地方
- 很难以可组合的方式强制执行约束（除非仔细编码，否则后面的步骤可能会更改结构，从而违反先前应用的规则）。也许在最后添加修剪步骤可能会有所帮助，但它看起来像是逻辑重复。
- 看起来我实际上并没有使用 LP 语言的强大功能 - 我基本上做了可以（更容易？）用任何普通语言完成的事情（减去静态类型，加上符号支持）。
- 实际任务会比较复杂（比如我可能需要检查过滤器表达式的可满足性），所以我想找到一个可扩展和可维护的解决方案。
其他想法
我也考虑过 CHR，但由于它的承诺选择性质，我看不出它如何用于需要解决方案分支的任务（探测 - 生成和修剪 - 替代解决方案）。
可能可以通过模拟多个约束存储的存在来支持分支（通过将特殊的“分支”参数附加到所有 constraints/terms），但这绝对超出了我的能力范围。
问题
有没有办法在 Prolog 中对这些规则进行建模，以便代码比非 LP 语言更具表现力？
或者我应该考虑其他系统（从 CLP 开始）？
CHR 更新
基于 CHR 和回溯（@Isabelle Newbie 建议）的解决方案有效，但生成的规则可能仍然缺乏可组合性（例如 post([group(c), group(d)]) 不会终止，因为不同的规则不断相互触发）。
虽然可以通过仔细编码和测试 CHR 来临时解决它，但也许一些更高级别的技术可以提供帮助？就像我们可以设置约束一样：
|groupings| =< 2
(a ∈ groupings) OR (a ∈ filters)
max(|groupings ⋂ original_groupings|)
并让机器找到变体。
我想原则上是可以的，但它是否是开发生产系统的可行方法？也许我应该为此创建一个单独的问题。
我认为 CHR 是一种合理的方式。您 可以 使用 CHR 探索替代解决方案，因为规则的右侧，而 通常 只是约束条件，实际上可以是任意的 Prolog 目标。这包括析取。例如：
:- chr_constraint go/0, a/0, b/0, c/0.
go <=> (a ; b ; c).
这确实探索了回溯的替代方案：
?- go.
a ;
b ;
c.
确实，使用这种表示形式很难强制执行“最多 a、b、c 中的两个，但要探索替代方案”约束。为此，您可以使用带有列表的表示形式来表示您的“约束存储内的约束存储”，如果您愿意：
:- chr_constraint store/1.
at_most_two @
store(Store)
<=>
Store = [_, _, _ | _]
|
store_2(Store).
store_2(Store) :-
select(X, Store, Store1),
select(Y, Store1, _Store2),
store([X, Y]).
go :-
store([a, b, c]).
你得到：
?- go.
store([a, b]) ;
store([a, c]) ;
store([b, a]) ;
store([b, c]) ;
store([c, a]) ;
store([c, b]) ;
false.
所以你可以以这种方式执行“最多两个”规则。
综上所述，这是给定问题的解决方案草图。一、预赛：
:- chr_constraint group/1.
:- chr_constraint grouping/1.
:- chr_constraint filter/1.
:- chr_constraint filters/1.
post_filter @
filter(Filter),
filters(Filters)
<=>
filters([Filter | Filters]).
post_group @
group(Group),
grouping(Groups)
<=>
grouping([Group | Groups]).
为了更严谨一点，这可能应该使用 sort/2 来排除重复项。
您的大部分约束都相当直接：
column_a_present @
grouping(Grouping),
filters(Filters)
<=>
\+ member(a, Grouping),
\+ member(a, Filters)
|
( grouping([a | Grouping]),
filters(Filters)
; grouping(Grouping),
filters([a | Filters]) ).
column_a_not_present_twice @
grouping(Grouping),
filters(Filters)
<=>
member(a, Grouping),
member(a, Filters)
|
false.
not_more_than_two_grouping @
grouping(Grouping)
<=>
Grouping = [_, _, _ | _]
|
select_2_groups(Grouping).
select_2_groups(Grouping) :-
SubGrouping = [X, Y],
select(X, Grouping, Grouping1),
select(Y, Grouping1, _Grouping2),
grouping(SubGrouping).
no_column_in_filter_and_grouping @
grouping(Grouping),
filters(Filters)
<=>
common_column(Grouping, Filters)
|
no_common_column(Grouping, Filters).
common_column(Grouping, Filters) :-
common_column(Grouping, Filters, _Column).
common_column(Grouping, Filters, Column) :-
member(group(Column), Grouping),
member(filter(Column), Filters).
no_common_column(Grouping, Filters) :-
common_column(Grouping, Filters, Column),
( select(group(Column), Grouping, Grouping1),
Filters1 = Filters
; Grouping1 = Grouping,
select(filter(Column), Filters, Filters1) ),
grouping(Grouping1),
filters(Filters1).
“无公共列”的情况有点不雅，但严格来说，您不允许在保护子句中绑定变量（尽管它往往适用于 SWI-Prolog 的 CHR 实现），因此有些工作是在后卫和球门之间复制。
最后，发布所有约束的主要谓词。这也是最容易处理“按列 a 添加默认分组”案例的地方：
is_group(group(_)).
is_filter(filter(_)).
post(Constraints) :-
include(is_group, Constraints, Groups0),
( Groups0 = []
-> Groups = [group(a)]
; Groups0 = Groups ),
include(is_filter, Constraints, Filters),
maplist(call, Groups),
maplist(call, Filters),
grouping([]),
filters([]).
并以此发布一组专栏，您可以回溯所有有效的备选方案：
?- post([filter(a), filter(b), filter(c), group(d), group(e), group(f)]).
grouping([d, e]),
filters([a, b, c]) ;
grouping([d, f]),
filters([a, b, c]) ;
grouping([e, d]),
filters([a, b, c]) ;
grouping([e, f]),
filters([a, b, c]) ;
grouping([f, d]),
filters([a, b, c]) ;
grouping([f, e]),
filters([a, b, c]) ;
false.
我想找到一种在给定 constraints/transformation 规则集的 Prolog 中转换数据结构的方法。
励志榜样
假设我们要validate/enrichSQL根据一些规则进行查询。
我们只对简单的 SQL 查询感兴趣，现在只考虑 WHERE/GROUP BY 子句，形式为 WHERE filter(a) AND filter(b) AND ... GROUP BY c,d,...（其中
a、b、c、d 是列名）。
此类查询的模型可能如下所示：
[filter(a), filter(b), group(c), group(d)]
我们可能有这样的规则：
- 列
a必须出现在过滤器或分组中（但只能出现一次）。如果不存在，通过添加到过滤器和分组来生成 2 个解决方案。 - 分组不能为空（如果为空，按列添加默认分组
a）。 - 不能超过 2 个分组（如果超过 2 个则通过删除额外的分组生成多个解决方案）。
- 过滤器和分组中都不能存在列（如果发生这种情况，则通过从过滤器和分组中删除列来生成 2 个解决方案）。
- 等等
一些规则显然是“冲突的”（例如，如果我们添加强制分组，我们可能会超过分组的最大数量，并且将不得不产生多个解决方案或根本不产生解决方案，具体取决于特定规则）。
我试过的
到目前为止我只能想出这样的东西：
transform(In, Out) :-
has_mandatory_grouping(In, Out1),
limited_grouping_count(Out1, Out2),
another_rule(Out2, Out3),
...
last_rule(OutN, Out).
has_mandatory_grouping(In, Out) :- contains(In, group(a)) -> Out = In; Out = [group(a)|In].
limited_grouping_count(In, Out) :- (length(In, L), L > 2) -> subset2(Out, In), Out = [_,_], contains(Out, group(a)); Out = In.
...
所以基本上是一组有序的步骤，每个步骤都应用一些逻辑来生成要传递给下游的新结构。
我不喜欢这种方法的地方
- 很难以可组合的方式强制执行约束（除非仔细编码，否则后面的步骤可能会更改结构，从而违反先前应用的规则）。也许在最后添加修剪步骤可能会有所帮助，但它看起来像是逻辑重复。
- 看起来我实际上并没有使用 LP 语言的强大功能 - 我基本上做了可以（更容易？）用任何普通语言完成的事情（减去静态类型，加上符号支持）。
- 实际任务会比较复杂（比如我可能需要检查过滤器表达式的可满足性），所以我想找到一个可扩展和可维护的解决方案。
其他想法
我也考虑过 CHR，但由于它的承诺选择性质，我看不出它如何用于需要解决方案分支的任务（探测 - 生成和修剪 - 替代解决方案）。
可能可以通过模拟多个约束存储的存在来支持分支（通过将特殊的“分支”参数附加到所有 constraints/terms），但这绝对超出了我的能力范围。
问题
有没有办法在 Prolog 中对这些规则进行建模，以便代码比非 LP 语言更具表现力？
或者我应该考虑其他系统（从 CLP 开始）？
CHR 更新
基于 CHR 和回溯（@Isabelle Newbie 建议）的解决方案有效，但生成的规则可能仍然缺乏可组合性（例如 post([group(c), group(d)]) 不会终止，因为不同的规则不断相互触发）。
虽然可以通过仔细编码和测试 CHR 来临时解决它，但也许一些更高级别的技术可以提供帮助？就像我们可以设置约束一样：
|groupings| =< 2
(a ∈ groupings) OR (a ∈ filters)
max(|groupings ⋂ original_groupings|)
并让机器找到变体。
我想原则上是可以的，但它是否是开发生产系统的可行方法？也许我应该为此创建一个单独的问题。
我认为 CHR 是一种合理的方式。您 可以 使用 CHR 探索替代解决方案，因为规则的右侧，而 通常 只是约束条件，实际上可以是任意的 Prolog 目标。这包括析取。例如：
:- chr_constraint go/0, a/0, b/0, c/0.
go <=> (a ; b ; c).
这确实探索了回溯的替代方案：
?- go.
a ;
b ;
c.
确实，使用这种表示形式很难强制执行“最多 a、b、c 中的两个，但要探索替代方案”约束。为此，您可以使用带有列表的表示形式来表示您的“约束存储内的约束存储”，如果您愿意：
:- chr_constraint store/1.
at_most_two @
store(Store)
<=>
Store = [_, _, _ | _]
|
store_2(Store).
store_2(Store) :-
select(X, Store, Store1),
select(Y, Store1, _Store2),
store([X, Y]).
go :-
store([a, b, c]).
你得到：
?- go.
store([a, b]) ;
store([a, c]) ;
store([b, a]) ;
store([b, c]) ;
store([c, a]) ;
store([c, b]) ;
false.
所以你可以以这种方式执行“最多两个”规则。
综上所述，这是给定问题的解决方案草图。一、预赛：
:- chr_constraint group/1.
:- chr_constraint grouping/1.
:- chr_constraint filter/1.
:- chr_constraint filters/1.
post_filter @
filter(Filter),
filters(Filters)
<=>
filters([Filter | Filters]).
post_group @
group(Group),
grouping(Groups)
<=>
grouping([Group | Groups]).
为了更严谨一点，这可能应该使用 sort/2 来排除重复项。
您的大部分约束都相当直接：
column_a_present @
grouping(Grouping),
filters(Filters)
<=>
\+ member(a, Grouping),
\+ member(a, Filters)
|
( grouping([a | Grouping]),
filters(Filters)
; grouping(Grouping),
filters([a | Filters]) ).
column_a_not_present_twice @
grouping(Grouping),
filters(Filters)
<=>
member(a, Grouping),
member(a, Filters)
|
false.
not_more_than_two_grouping @
grouping(Grouping)
<=>
Grouping = [_, _, _ | _]
|
select_2_groups(Grouping).
select_2_groups(Grouping) :-
SubGrouping = [X, Y],
select(X, Grouping, Grouping1),
select(Y, Grouping1, _Grouping2),
grouping(SubGrouping).
no_column_in_filter_and_grouping @
grouping(Grouping),
filters(Filters)
<=>
common_column(Grouping, Filters)
|
no_common_column(Grouping, Filters).
common_column(Grouping, Filters) :-
common_column(Grouping, Filters, _Column).
common_column(Grouping, Filters, Column) :-
member(group(Column), Grouping),
member(filter(Column), Filters).
no_common_column(Grouping, Filters) :-
common_column(Grouping, Filters, Column),
( select(group(Column), Grouping, Grouping1),
Filters1 = Filters
; Grouping1 = Grouping,
select(filter(Column), Filters, Filters1) ),
grouping(Grouping1),
filters(Filters1).
“无公共列”的情况有点不雅，但严格来说，您不允许在保护子句中绑定变量（尽管它往往适用于 SWI-Prolog 的 CHR 实现），因此有些工作是在后卫和球门之间复制。
最后，发布所有约束的主要谓词。这也是最容易处理“按列 a 添加默认分组”案例的地方：
is_group(group(_)).
is_filter(filter(_)).
post(Constraints) :-
include(is_group, Constraints, Groups0),
( Groups0 = []
-> Groups = [group(a)]
; Groups0 = Groups ),
include(is_filter, Constraints, Filters),
maplist(call, Groups),
maplist(call, Filters),
grouping([]),
filters([]).
并以此发布一组专栏，您可以回溯所有有效的备选方案：
?- post([filter(a), filter(b), filter(c), group(d), group(e), group(f)]).
grouping([d, e]),
filters([a, b, c]) ;
grouping([d, f]),
filters([a, b, c]) ;
grouping([e, d]),
filters([a, b, c]) ;
grouping([e, f]),
filters([a, b, c]) ;
grouping([f, d]),
filters([a, b, c]) ;
grouping([f, e]),
filters([a, b, c]) ;
false.