feat: model query functional dependencies

9 files changed, 137 insertions, 23 deletions

diff --git a/subprojects/store/src/main/java/tools/refinery/store/query/DNF.java b/subprojects/store/src/main/java/tools/refinery/store/query/DNF.java
index 336c25a1..3ce4eed9 100644
--- a/subprojects/store/src/main/java/tools/refinery/store/query/DNF.java
+++ b/subprojects/store/src/main/java/tools/refinery/store/query/DNF.java
@@ -5,22 +5,48 @@ import tools.refinery.store.query.atom.DNFAtom;
 
 import java.util.*;
 
-public class DNF implements SymbolLike {
+public final class DNF implements SymbolLike {
         private final String name;
 
         private final String uniqueName;
 
         private final List<Variable> parameters;
 
+        private final List<FunctionalDependency<Variable>> functionalDependencies;
+
         private final List<DNFAnd> clauses;
 
-        private DNF(String name, List<Variable> parameters, List<DNFAnd> clauses) {
+        private DNF(String name, List<Variable> parameters, List<FunctionalDependency<Variable>> functionalDependencies,
+                                List<DNFAnd> clauses) {
+                validateFunctionalDependencies(parameters, functionalDependencies);
                 this.name = name;
                 this.uniqueName = DNFUtils.generateUniqueName(name);
                 this.parameters = parameters;
+                this.functionalDependencies = functionalDependencies;
                 this.clauses = clauses;
         }
 
+        private static void validateFunctionalDependencies(
+                        Collection<Variable> parameters, Collection<FunctionalDependency<Variable>> functionalDependencies) {
+                var parameterSet = new HashSet<>(parameters);
+                for (var functionalDependency : functionalDependencies) {
+                        validateParameters(parameters, parameterSet, functionalDependency.forEach(), functionalDependency);
+                        validateParameters(parameters, parameterSet, functionalDependency.unique(), functionalDependency);
+                }
+        }
+
+        private static void validateParameters(Collection<Variable> parameters, Set<Variable> parameterSet,
+                                                                                   Collection<Variable> toValidate,
+                                                                                   FunctionalDependency<Variable> functionalDependency) {
+                for (var variable : toValidate) {
+                        if (!parameterSet.contains(variable)) {
+                                throw new IllegalArgumentException(
+                                                "Variable %s of functional dependency %s does not appear in the parameter list %s"
+                                                                .formatted(variable, functionalDependency, parameters));
+                        }
+                }
+        }
+
         @Override
         public String name() {
                 return name;
@@ -34,6 +60,10 @@ public class DNF implements SymbolLike {
                 return parameters;
         }
 
+        public List<FunctionalDependency<Variable>> getFunctionalDependencies() {
+                return functionalDependencies;
+        }
+
         @Override
         public int arity() {
                 return parameters.size();
@@ -57,6 +87,8 @@ public class DNF implements SymbolLike {
 
                 private final List<Variable> parameters = new ArrayList<>();
 
+                private final List<FunctionalDependency<Variable>> functionalDependencies = new ArrayList<>();
+
                 private final List<List<DNFAtom>> clauses = new ArrayList<>();
 
                 private Builder(String name) {
@@ -64,7 +96,7 @@ public class DNF implements SymbolLike {
                 }
 
                 public Builder parameter(Variable variable) {
-                        this.parameters.add(variable);
+                        parameters.add(variable);
                         return this;
                 }
 
@@ -73,10 +105,24 @@ public class DNF implements SymbolLike {
                 }
 
                 public Builder parameters(Collection<Variable> variables) {
-                        this.parameters.addAll(variables);
+                        parameters.addAll(variables);
                         return this;
                 }
 
+                public Builder functionalDependencies(Collection<FunctionalDependency<Variable>> functionalDependencies) {
+                        this.functionalDependencies.addAll(functionalDependencies);
+                        return this;
+                }
+
+                public Builder functionalDependency(FunctionalDependency<Variable> functionalDependency) {
+                        functionalDependencies.add(functionalDependency);
+                        return this;
+                }
+
+                public Builder functionalDependency(Set<Variable> forEach, Set<Variable> unique) {
+                        return functionalDependency(new FunctionalDependency<>(forEach, unique));
+                }
+
                 public Builder clause(DNFAtom... atoms) {
                         clauses.add(List.of(atoms));
                         return this;
@@ -113,9 +159,12 @@ public class DNF implements SymbolLike {
                                         constraint.collectAllVariables(variables);
                                 }
                                 parameters.forEach(variables::remove);
-                                postProcessedClauses.add(new DNFAnd(variables, constraints));
+                                postProcessedClauses.add(new DNFAnd(Collections.unmodifiableSet(variables),
+                                                Collections.unmodifiableList(constraints)));
                         }
-                        return new DNF(name, List.copyOf(parameters), postProcessedClauses);
+                        return new DNF(name, Collections.unmodifiableList(parameters),
+                                        Collections.unmodifiableList(functionalDependencies),
+                                        Collections.unmodifiableList(postProcessedClauses));
                 }
         }
 }
diff --git a/subprojects/store/src/main/java/tools/refinery/store/query/FunctionalDependency.java b/subprojects/store/src/main/java/tools/refinery/store/query/FunctionalDependency.java
new file mode 100644
index 00000000..63a81713
--- /dev/null
+++ b/subprojects/store/src/main/java/tools/refinery/store/query/FunctionalDependency.java
@@ -0,0 +1,15 @@
+package tools.refinery.store.query;
+
+import java.util.HashSet;
+import java.util.Set;
+
+public record FunctionalDependency<T>(Set<T> forEach, Set<T> unique) {
+        public FunctionalDependency {
+                var uniqueForEach = new HashSet<>(unique);
+                uniqueForEach.retainAll(forEach);
+                if (!uniqueForEach.isEmpty()) {
+                        throw new IllegalArgumentException("Variables %s appear on both sides of the functional dependency"
+                                        .formatted(uniqueForEach));
+                }
+        }
+}
diff --git a/subprojects/store/src/main/java/tools/refinery/store/query/ModelQueryBuilder.java b/subprojects/store/src/main/java/tools/refinery/store/query/ModelQueryBuilder.java
index 853a1796..4364d844 100644
--- a/subprojects/store/src/main/java/tools/refinery/store/query/ModelQueryBuilder.java
+++ b/subprojects/store/src/main/java/tools/refinery/store/query/ModelQueryBuilder.java
@@ -11,7 +11,7 @@ public interface ModelQueryBuilder extends ModelAdapterBuilder {
                 return queries(List.of(queries));
         }
 
-        default ModelQueryBuilder queries(Collection<? extends DNF> queries) {
+        default ModelQueryBuilder queries(Collection<DNF> queries) {
                 queries.forEach(this::query);
                 return this;
         }
diff --git a/subprojects/store/src/main/java/tools/refinery/store/query/view/AnyRelationView.java b/subprojects/store/src/main/java/tools/refinery/store/query/view/AnyRelationView.java
index 9df1038b..eb64b589 100644
--- a/subprojects/store/src/main/java/tools/refinery/store/query/view/AnyRelationView.java
+++ b/subprojects/store/src/main/java/tools/refinery/store/query/view/AnyRelationView.java
@@ -1,12 +1,23 @@
 package tools.refinery.store.query.view;
 
 import tools.refinery.store.model.Model;
-import tools.refinery.store.representation.SymbolLike;
+import tools.refinery.store.query.FunctionalDependency;
 import tools.refinery.store.representation.AnySymbol;
+import tools.refinery.store.representation.SymbolLike;
+
+import java.util.Set;
 
 public sealed interface AnyRelationView extends SymbolLike permits RelationView {
         AnySymbol getSymbol();
 
+        default Set<FunctionalDependency<Integer>> getFunctionalDependencies() {
+                return Set.of();
+        }
+
+        default Set<RelationViewImplication> getImpliedRelationViews() {
+                return Set.of();
+        }
+
         boolean get(Model model, Object[] tuple);
 
         Iterable<Object[]> getAll(Model model);
diff --git a/subprojects/store/src/main/java/tools/refinery/store/query/view/FunctionalRelationView.java b/subprojects/store/src/main/java/tools/refinery/store/query/view/FunctionalRelationView.java
index d263679a..3d278a8b 100644
--- a/subprojects/store/src/main/java/tools/refinery/store/query/view/FunctionalRelationView.java
+++ b/subprojects/store/src/main/java/tools/refinery/store/query/view/FunctionalRelationView.java
@@ -1,11 +1,16 @@
 package tools.refinery.store.query.view;
 
 import tools.refinery.store.model.Model;
+import tools.refinery.store.query.FunctionalDependency;
+import tools.refinery.store.representation.Symbol;
 import tools.refinery.store.tuple.Tuple;
 import tools.refinery.store.tuple.Tuple1;
-import tools.refinery.store.representation.Symbol;
 
-public class FunctionalRelationView<T> extends RelationView<T> {
+import java.util.Set;
+import java.util.stream.Collectors;
+import java.util.stream.IntStream;
+
+public final class FunctionalRelationView<T> extends RelationView<T> {
         public FunctionalRelationView(Symbol<T> symbol, String name) {
                 super(symbol, name);
         }
@@ -15,13 +20,35 @@ public class FunctionalRelationView<T> extends RelationView<T> {
         }
 
         @Override
+        public Set<FunctionalDependency<Integer>> getFunctionalDependencies() {
+                var arity = getSymbol().arity();
+                var forEach = IntStream.range(0, arity).boxed().collect(Collectors.toUnmodifiableSet());
+                var unique = Set.of(arity);
+                return Set.of(new FunctionalDependency<>(forEach, unique));
+        }
+
+        @Override
+        public Set<RelationViewImplication> getImpliedRelationViews() {
+                var symbol = getSymbol();
+                var impliedIndices = IntStream.range(0, symbol.arity()).boxed().toList();
+                var keyOnlyRelationView = new KeyOnlyRelationView<>(symbol);
+                return Set.of(new RelationViewImplication(this, keyOnlyRelationView, impliedIndices));
+        }
+
+        @Override
         public boolean filter(Tuple key, T value) {
                 return true;
         }
 
         @Override
         public Object[] forwardMap(Tuple key, T value) {
-                return toTuple1ArrayPlusValue(key, value);
+                int size = key.getSize();
+                Object[] result = new Object[size + 1];
+                for (int i = 0; i < size; i++) {
+                        result[i] = Tuple.of(key.get(i));
+                }
+                result[key.getSize()] = value;
+                return result;
         }
 
         @Override
@@ -41,13 +68,4 @@ public class FunctionalRelationView<T> extends RelationView<T> {
         public int arity() {
                 return getSymbol().arity() + 1;
         }
-
-        private static <D> Object[] toTuple1ArrayPlusValue(Tuple t, D value) {
-                Object[] result = new Object[t.getSize() + 1];
-                for (int i = 0; i < t.getSize(); i++) {
-                        result[i] = Tuple.of(t.get(i));
-                }
-                result[t.getSize()] = value;
-                return result;
-        }
 }
diff --git a/subprojects/store/src/main/java/tools/refinery/store/query/view/KeyOnlyRelationView.java b/subprojects/store/src/main/java/tools/refinery/store/query/view/KeyOnlyRelationView.java
index fdfcdf28..e1b2e45b 100644
--- a/subprojects/store/src/main/java/tools/refinery/store/query/view/KeyOnlyRelationView.java
+++ b/subprojects/store/src/main/java/tools/refinery/store/query/view/KeyOnlyRelationView.java
@@ -5,7 +5,7 @@ import tools.refinery.store.tuple.Tuple;
 
 import java.util.Objects;
 
-public class KeyOnlyRelationView<T> extends TuplePreservingRelationView<T> {
+public final class KeyOnlyRelationView<T> extends TuplePreservingRelationView<T> {
         public static final String VIEW_NAME = "key";
 
         private final T defaultValue;
diff --git a/subprojects/store/src/main/java/tools/refinery/store/query/view/RelationViewImplication.java b/subprojects/store/src/main/java/tools/refinery/store/query/view/RelationViewImplication.java
new file mode 100644
index 00000000..2ba1fcc4
--- /dev/null
+++ b/subprojects/store/src/main/java/tools/refinery/store/query/view/RelationViewImplication.java
@@ -0,0 +1,19 @@
+package tools.refinery.store.query.view;
+
+import java.util.List;
+
+public record RelationViewImplication(AnyRelationView implyingRelationView, AnyRelationView impliedRelationView,
+                                                                          List<Integer> impliedIndices) {
+        public RelationViewImplication {
+                if (impliedIndices.size() != impliedRelationView.arity()) {
+                        throw new IllegalArgumentException("Expected %d implied indices for %s, but %d are provided"
+                                        .formatted(impliedRelationView.arity(), impliedRelationView, impliedIndices.size()));
+                }
+                for (var index : impliedIndices) {
+                        if (impliedRelationView.invalidIndex(index)) {
+                                throw new IllegalArgumentException("%d is not a valid index for %s".formatted(index,
+                                                implyingRelationView));
+                        }
+                }
+        }
+}
diff --git a/subprojects/store/src/main/java/tools/refinery/store/representation/Symbol.java b/subprojects/store/src/main/java/tools/refinery/store/representation/Symbol.java
index 404b5ddb..77fae5f4 100644
--- a/subprojects/store/src/main/java/tools/refinery/store/representation/Symbol.java
+++ b/subprojects/store/src/main/java/tools/refinery/store/representation/Symbol.java
@@ -2,8 +2,6 @@ package tools.refinery.store.representation;
 
 import java.util.Objects;
 
-// Deliberately not a record, because we want equality by reference.
-@SuppressWarnings({"squid:S6206", "ClassCanBeRecord"})
 public final class Symbol<T> implements AnySymbol {
         private final String name;
         private final int arity;
diff --git a/subprojects/store/src/main/java/tools/refinery/store/representation/SymbolLike.java b/subprojects/store/src/main/java/tools/refinery/store/representation/SymbolLike.java
index 8c84500c..30a892ae 100644
--- a/subprojects/store/src/main/java/tools/refinery/store/representation/SymbolLike.java
+++ b/subprojects/store/src/main/java/tools/refinery/store/representation/SymbolLike.java
@@ -4,4 +4,8 @@ public interface SymbolLike {
         String name();
 
         int arity();
+
+        default boolean invalidIndex(int i) {
+                return i < 0 || i >= arity();
+        }
 }