How to transform data structures in Prolog using multiple rules, declaratively

Question

I would like to find a way to transform data structure in Prolog given set of constraints/transformation rules.

Motivating example

Let's say we want to validate/enrich SQL queries according to some rules. We are only interested in simple SQL queries and only consider WHERE/GROUP BY clauses now, of the form WHERE filter(a) AND filter(b) AND ... GROUP BY c,d,... (where a, b, c, d are column names).

The model of such query could look like:

[filter(a), filter(b), group(c), group(d)]

We may have rules like this:

Column a must be present in either filter or grouping (but only once). If not present, generate 2 solutions by adding to filter and to grouping.
Grouping must not be empty (if empty, add default grouping by column a).
Must be not more than 2 grouping (if more than 2 then generate multiple solutions by removing extra grouping).
No column may be present in both filter and grouping (if it happens then generate 2 solutions by removing column from either filter and grouping).
etc.

Some rules are obviously "conflicting" (e.g. if we add mandatory grouping we may exceed max number of groupings and will have to produce multiple solutions or no solutions at all, depending on specific rules).

What I tried

So far I was only able to come up with something like this:

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.
...

So basically an ordered set of steps, each step applying some logic to produce new structure to be passed downstream.

What I don't like about such approach

It's hard to enforce constraints in a composable way (unless carefully coded, later steps may change the structure so that rules applied earlier are violated). Maybe adding pruning steps at the end could help but then it looks like a duplication of logic.
Looks like I don't actually use power of the LP language - I basically doing what can be (more easily?) done in any average language (minus static typing, plus symbols support).
Actual task will be a bit more complicated (e.g. I may need to check filter expression satisfiability), so I would like to find a scalable and maintainable solution.

Other ideas

I also considered CHR but due to its committed-choice nature I can't see how it can be used in the task which requires solution branching (probing - generating and pruning - alternative solutions).

It's probably possible to support branching by simulating presence of the multiple constraint stores (by attaching special "branch" argument to all constraints/terms), but that's definitely over my abilities.

Question

Is there a way to model these rules in Prolog so that the code is more expressive than can be done in the non-LP language?

Or should I consider other systems (starting with CLP)?

Update on CHR

Solution based on CHR and backtracking (suggested by @Isabelle Newbie) works, but resulting rules may still lack composability (e.g. post([group(c), group(d)]) does not terminate because different rules keep triggering each other).

While it can be solved ad-hoc by carefully coding and testing CHR, maybe some higher-level technique could help? Like if we could put constraints:

|groupings| =< 2
(a ∈ groupings) OR (a ∈ filters)
max(|groupings ⋂ original_groupings|)

and make machine find variants.

I guess it's possible in principle, but could it be a feasible approach for developing production system? Maybe I should create a separate question for this.

user_4391743 · Answer

I think CHR is a reasonable way to go here. You can explore alternative solutions with CHR because a rule's right-hand side, while often just constraint terms, can in fact be an arbitrary Prolog goal. This includes disjunctions. For example:

:- chr_constraint go/0, a/0, b/0, c/0.

go <=> (a ; b ; c).

This does explore alternatives on backtracking:

?- go.
a ;
b ;
c.

What is true that with this kind of representation it's difficult to enforce "at most two out of a, b, c, but explore alternatives" constraints. For this you can use a representation with a list for your "constraint store inside the constraint store", if you will:

:- 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]).

Here you get:

?- go.
store([a, b]) ;
store([a, c]) ;
store([b, a]) ;
store([b, c]) ;
store([c, a]) ;
store([c, b]) ;
false.

So you can enforce an "at most two" rule in this way.

With all that, here's a sketch of a solution for your problem as given. First, preliminaries:

:- 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]).

For a bit more rigor, this should probably use sort/2 to exclude duplicates.

Most of your constraints translate fairly directly:

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).

The "no common column" case is a bit inelegant, but strictly speaking you're not allowed to bind variables in a guard clause (although it tends to work in SWI-Prolog's CHR implementation), hence some work is duplicated between the guard and the goal.

Finally, the main predicate for posting all constraints. This is also where it's easiest to take care of the "add default grouping by column a" case:

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([]).

And posting a set of columns with this you get backtracking over all valid alternatives:

?- 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.