mihaibudiu commented on code in PR #4540: URL: https://github.com/apache/calcite/pull/4540#discussion_r2363949425
########## core/src/main/java/org/apache/calcite/rel/metadata/FunctionalDependencySet.java: ########## @@ -0,0 +1,369 @@ +/* + * Licensed to the Apache Software Foundation (ASF) under one or more + * contributor license agreements. See the NOTICE file distributed with + * this work for additional information regarding copyright ownership. + * The ASF licenses this file to you under the Apache License, Version 2.0 + * (the "License"); you may not use this file except in compliance with + * the License. You may obtain a copy of the License at + * + * http://www.apache.org/licenses/LICENSE-2.0 + * + * Unless required by applicable law or agreed to in writing, software + * distributed under the License is distributed on an "AS IS" BASIS, + * WITHOUT WARRANTIES OR CONDITIONS OF ANY KIND, either express or implied. + * See the License for the specific language governing permissions and + * limitations under the License. + */ +package org.apache.calcite.rel.metadata; + +import org.apache.calcite.util.ImmutableBitSet; + +import com.google.common.collect.ImmutableSet; + +import java.util.ArrayDeque; +import java.util.ArrayList; +import java.util.Collections; +import java.util.Comparator; +import java.util.HashMap; +import java.util.HashSet; +import java.util.List; +import java.util.Map; +import java.util.PriorityQueue; +import java.util.Queue; +import java.util.Set; + +/** + * A set of functional dependencies with closure and minimal cover operations. + * This class implements standard algorithms for functional dependency reasoning. + */ +public class FunctionalDependencySet { + // Maximum number of attributes supported in closure computation + private static final int MAX_CLOSURE_ATTRS = 10000; + + private final Set<FunctionalDependency> fdSet = new HashSet<>(); + + public FunctionalDependencySet() {} + + public FunctionalDependencySet(Set<FunctionalDependency> fds) { + this.fdSet.addAll(fds); + } + + public void addFD(FunctionalDependency fd) { + if (!fd.isTrivial()) { + fdSet.add(fd); + } + } + + public void addFD(ImmutableBitSet determinants, ImmutableBitSet dependents) { + addFD(new FunctionalDependency(determinants, dependents)); + } + + public void addFD(int determinant, int dependent) { + addFD(ImmutableBitSet.of(determinant), ImmutableBitSet.of(dependent)); + } + + public void removeFD(FunctionalDependency fd) { + fdSet.remove(fd); + } + + public Set<FunctionalDependency> getFDs() { + return Collections.unmodifiableSet(fdSet); + } + + public boolean isEmpty() { + return fdSet.isEmpty(); + } + + public int size() { + return fdSet.size(); + } + + /** + * Returns an ImmutableBitSet containing all attribute indexes that appear in any FD in the set. + */ + public static ImmutableBitSet allAttributesFromFds(FunctionalDependencySet fds) { + ImmutableBitSet.Builder builder = ImmutableBitSet.builder(); + Set<FunctionalDependency> fdSet = fds.getFDs(); + for (FunctionalDependency fd : fdSet) { + builder.addAll(fd.getDeterminants()); + builder.addAll(fd.getDependents()); + } + return builder.build(); + } + + /** + * Computes the closure of a set of attributes under this functional dependency set. + * The closure of X, denoted X+, is the set of all attributes that can be functionally + * determined by X using the functional dependencies in this set and Armstrong's axioms. Review Comment: can you add a link to https://en.wikipedia.org/wiki/Armstrong%27s_axioms? ########## core/src/main/java/org/apache/calcite/rel/metadata/RelMdFunctionalDependency.java: ########## @@ -64,212 +76,422 @@ protected RelMdFunctionalDependency() {} return BuiltInMetadata.FunctionalDependency.DEF; } + /** + * Determines if column is functionally dependent on key for a given rel node. + */ public @Nullable Boolean determines(RelNode rel, RelMetadataQuery mq, int key, int column) { - return determinesImpl2(rel, mq, key, column); + return determinesSet(rel, mq, ImmutableBitSet.of(key), ImmutableBitSet.of(column)); } - public @Nullable Boolean determines(SetOp rel, RelMetadataQuery mq, - int key, int column) { - return determinesImpl2(rel, mq, key, column); + /** + * Determines if a set of columns functionally determines another set of columns. + */ + public Boolean determinesSet(RelNode rel, RelMetadataQuery mq, + ImmutableBitSet determinants, ImmutableBitSet dependents) { + FunctionalDependencySet fdSet = mq.getFunctionalDependencies(rel); + return fdSet.implies(determinants, dependents); } - public @Nullable Boolean determines(Join rel, RelMetadataQuery mq, - int key, int column) { - return determinesImpl2(rel, mq, key, column); + /** + * Returns the closure of a set of columns under all functional dependencies. + */ + public ImmutableBitSet closure(RelNode rel, RelMetadataQuery mq, ImmutableBitSet attrs) { + FunctionalDependencySet fdSet = mq.getFunctionalDependencies(rel); + return fdSet.closure(attrs); } - public @Nullable Boolean determines(Correlate rel, RelMetadataQuery mq, - int key, int column) { - return determinesImpl2(rel, mq, key, column); + /** + * Returns candidate keys for the relation within the specified set of attributes. + */ + public Set<ImmutableBitSet> candidateKeys( + RelNode rel, RelMetadataQuery mq, ImmutableBitSet attributes) { + FunctionalDependencySet fdSet = mq.getFunctionalDependencies(rel); + return fdSet.findCandidateKeys(attributes); } - public @Nullable Boolean determines(Aggregate rel, RelMetadataQuery mq, - int key, int column) { - return determinesImpl(rel, mq, key, column); + /** + * Main dispatch method for getFunctionalDependencies. + * Routes to appropriate handler based on RelNode type. + */ + public FunctionalDependencySet getFunctionalDependencies(RelNode rel, RelMetadataQuery mq) { + if (rel instanceof TableScan) { + return getTableScanFD((TableScan) rel); + } else if (rel instanceof Project) { + return getProjectFD((Project) rel, mq); + } else if (rel instanceof Aggregate) { + return getAggregateFD((Aggregate) rel, mq); + } else if (rel instanceof Join) { + return getJoinFD((Join) rel, mq); + } else if (rel instanceof Calc) { + return getCalcFD((Calc) rel, mq); + } else if (rel instanceof SetOp) { + // TODO: Handle UNION, INTERSECT, EXCEPT functional dependencies + return new FunctionalDependencySet(); + } else if (rel instanceof Correlate) { + // TODO: Handle CORRELATE functional dependencies + return new FunctionalDependencySet(); + } + return getFD(rel.getInputs(), mq); } - public @Nullable Boolean determines(Calc rel, RelMetadataQuery mq, - int key, int column) { - return determinesImpl(rel, mq, key, column); + private static FunctionalDependencySet getFD(List<RelNode> inputs, RelMetadataQuery mq) { + FunctionalDependencySet result = new FunctionalDependencySet(); + for (RelNode input : inputs) { + FunctionalDependencySet fdSet = mq.getFunctionalDependencies(input); + result = result.union(fdSet); + } + return result; } - public @Nullable Boolean determines(Project rel, RelMetadataQuery mq, - int key, int column) { - return determinesImpl(rel, mq, key, column); - } + private static FunctionalDependencySet getTableScanFD(TableScan rel) { + FunctionalDependencySet fdSet = new FunctionalDependencySet(); - /** - * Checks if a column is functionally determined by a key column through expression analysis. - * - * @param rel The input relation - * @param mq Metadata query instance - * @param key Index of the determinant expression - * @param column Index of the dependent expression - * @return TRUE if column is determined by key, - * FALSE if not determined, - * NULL if undetermined - */ - private static @Nullable Boolean determinesImpl(RelNode rel, RelMetadataQuery mq, - int key, int column) { - if (preCheck(rel, key, column)) { - return true; + RelOptTable table = rel.getTable(); + List<ImmutableBitSet> keys = table.getKeys(); + if (keys == null || keys.isEmpty()) { + return fdSet; } - ImmutableBitSet keyInputIndices = null; - ImmutableBitSet columnInputIndices = null; - if (rel instanceof Project || rel instanceof Calc) { - List<RexNode> exprs = null; - if (rel instanceof Project) { - Project project = (Project) rel; - exprs = project.getProjects(); - } else { - Calc calc = (Calc) rel; - final RexProgram program = calc.getProgram(); - exprs = program.expandList(program.getProjectList()); + for (ImmutableBitSet key : keys) { + ImmutableBitSet allColumns = ImmutableBitSet.range(rel.getRowType().getFieldCount()); + ImmutableBitSet dependents = allColumns.except(key); + if (!dependents.isEmpty()) { + fdSet.addFD(key, dependents); } + } - // TODO: Supports dependency analysis for all types of expressions - if (!(exprs.get(column) instanceof RexInputRef)) { - return false; - } + return fdSet; + } - RexNode keyExpr = exprs.get(key); - RexNode columnExpr = exprs.get(column); + private static FunctionalDependencySet getProjectFD(Project rel, RelMetadataQuery mq) { + return getProjectionFD(rel.getInput(), rel.getProjects(), mq); + } - // Identical expressions imply functional dependency - if (keyExpr.equals(columnExpr)) { - return true; + /** + * Common method to compute functional dependencies for projection operations. + * Used by both Project and Calc nodes. + * + * @param input the input relation + * @param projections the list of projection expressions + * @param mq the metadata query + * @return the functional dependency set for the projection + */ + private static FunctionalDependencySet getProjectionFD( + RelNode input, List<RexNode> projections, RelMetadataQuery mq) { + FunctionalDependencySet inputFdSet = mq.getFunctionalDependencies(input); + FunctionalDependencySet projectionFdSet = new FunctionalDependencySet(); + int fieldCount = projections.size(); + + // Create mapping from input column indices to project column indices + Mappings.TargetMapping inputToOutputMap = + RelOptUtil.permutation(projections, input.getRowType()); + + // Map input functional dependencies to project dependencies + mapInputFDs(inputFdSet, inputToOutputMap, projectionFdSet); + + // For each pair of output columns, determine if one determines the other Review Comment: for a relation with 10000 columns, the cost of this would be 100,000,000. ########## core/src/main/java/org/apache/calcite/rel/metadata/FunctionalDependencySet.java: ########## @@ -0,0 +1,267 @@ +/* + * Licensed to the Apache Software Foundation (ASF) under one or more + * contributor license agreements. See the NOTICE file distributed with + * this work for additional information regarding copyright ownership. + * The ASF licenses this file to you under the Apache License, Version 2.0 + * (the "License"); you may not use this file except in compliance with + * the License. You may obtain a copy of the License at + * + * http://www.apache.org/licenses/LICENSE-2.0 + * + * Unless required by applicable law or agreed to in writing, software + * distributed under the License is distributed on an "AS IS" BASIS, + * WITHOUT WARRANTIES OR CONDITIONS OF ANY KIND, either express or implied. + * See the License for the specific language governing permissions and + * limitations under the License. + */ +package org.apache.calcite.rel.metadata; + +import org.apache.calcite.util.ImmutableBitSet; + +import com.google.common.collect.ImmutableSet; + +import java.util.Collections; +import java.util.HashSet; +import java.util.Set; + +/** + * A set of functional dependencies with closure and minimal cover operations. + * This class implements standard algorithms for functional dependency reasoning. + */ +public class FunctionalDependencySet { + private final Set<FunctionalDependency> fdSet = new HashSet<>(); + + public FunctionalDependencySet() {} Review Comment: You said yourself that a functional dependency is always defined over a relation. But here you don't know anything about the relation in question - not even how many columns it has. Storing the number of columns of the relation would enable you to check that no one accidentally combines two functional dependencies that belong to different relations. ########## core/src/test/java/org/apache/calcite/rel/metadata/FunctionalDependencyTest.java: ########## @@ -0,0 +1,272 @@ +/* + * Licensed to the Apache Software Foundation (ASF) under one or more + * contributor license agreements. See the NOTICE file distributed with + * this work for additional information regarding copyright ownership. + * The ASF licenses this file to you under the Apache License, Version 2.0 + * (the "License"); you may not use this file except in compliance with + * the License. You may obtain a copy of the License at + * + * http://www.apache.org/licenses/LICENSE-2.0 + * + * Unless required by applicable law or agreed to in writing, software + * distributed under the License is distributed on an "AS IS" BASIS, + * WITHOUT WARRANTIES OR CONDITIONS OF ANY KIND, either express or implied. + * See the License for the specific language governing permissions and + * limitations under the License. + */ +package org.apache.calcite.rel.metadata; + +import org.apache.calcite.util.ImmutableBitSet; + +import org.junit.jupiter.api.Test; + +import java.util.Set; + +import static org.hamcrest.CoreMatchers.is; +import static org.hamcrest.MatcherAssert.assertThat; +import static org.hamcrest.Matchers.containsInAnyOrder; +import static org.hamcrest.Matchers.equalTo; +import static org.hamcrest.Matchers.hasSize; + +/** + * Tests for {@link FunctionalDependency} and {@link FunctionalDependencySet}. + */ +public class FunctionalDependencyTest { + + @Test void testFunctionalDependencyBasic() { + // Test FD creation and basic properties + FunctionalDependency fd = FunctionalDependency.of(new int[]{0}, new int[]{1}); + assertThat(fd.getDeterminants(), equalTo(ImmutableBitSet.of(0))); + assertThat(fd.getDependents(), equalTo(ImmutableBitSet.of(1))); + assertThat(fd.isTrivial(), is(false)); + + // Test trivial FD + FunctionalDependency trivialFd = FunctionalDependency.of(new int[]{0, 1}, new int[]{0}); + assertThat(trivialFd.isTrivial(), is(true)); + } + + @Test void testFunctionalDependencySet() { + FunctionalDependencySet fdSet = new FunctionalDependencySet(); + + // FDs: 0 -> 1, 1 -> 2 + fdSet.addFD(0, 1); + fdSet.addFD(1, 2); + + // Test closure: {0}+ should include 0, 1, 2 + ImmutableBitSet closure = fdSet.closure(ImmutableBitSet.of(0)); + assertThat(closure.get(0), is(true)); + assertThat(closure.get(1), is(true)); + assertThat(closure.get(2), is(true)); // 2 (0 -> 1, 1 -> 2, so 0 -> 2 by transitivity) + + // Test determines + assertThat(fdSet.determines(0, 1), is(true)); + assertThat(fdSet.determines(0, 2), is(true)); // 0 -> 2 (transitive) + assertThat(fdSet.determines(2, 0), is(false)); // 2 doesn't determine 0 + } + + @Test void testMinimalCover() { + FunctionalDependencySet fdSet = new FunctionalDependencySet(); + + // FDs: 0 -> 1, 1 -> 2, 0 -> 2 (0 -> 2 is redundant) + fdSet.addFD(ImmutableBitSet.of(0), ImmutableBitSet.of(1)); + fdSet.addFD(ImmutableBitSet.of(1), ImmutableBitSet.of(2)); + fdSet.addFD(ImmutableBitSet.of(0), ImmutableBitSet.of(2)); + + FunctionalDependencySet minimal = fdSet.minimalCover(); + + // The minimal cover should not contain 0 -> 2 since it's implied by 0 -> 1 and 1 -> 2 + assertThat( + minimal.implies(ImmutableBitSet.of(0), + ImmutableBitSet.of(1)), is(true)); + assertThat( + minimal.implies(ImmutableBitSet.of(1), + ImmutableBitSet.of(2)), is(true)); + assertThat( + minimal.implies(ImmutableBitSet.of(0), + ImmutableBitSet.of(2)), is(true)); + + // Should be equivalent to original + assertThat(fdSet.equalTo(minimal), is(true)); + } + + @Test void testKeyFinding() { + FunctionalDependencySet fdSet = new FunctionalDependencySet(); + + // FDs: 0 -> 1, {1,2} -> 3 + fdSet.addFD(0, 1); + fdSet.addFD(ImmutableBitSet.of(1, 2), ImmutableBitSet.of(3)); + + ImmutableBitSet allAttributes = FunctionalDependencySet.allAttributesFromFds(fdSet); + Set<ImmutableBitSet> keys = fdSet.findCandidateKeys(allAttributes); + + // {0,2} should be a key: 0 -> 1, and {1,2} -> 3, so {0,2} -> {0,1,2,3} + assertThat(keys, containsInAnyOrder(ImmutableBitSet.of(0, 2))); + + // Verify it's actually a key + assertThat(fdSet.isKey(ImmutableBitSet.of(0, 2), allAttributes), is(true)); + + // Verify non-keys + assertThat(fdSet.isKey(ImmutableBitSet.of(0), allAttributes), is(false)); + assertThat(fdSet.isKey(ImmutableBitSet.of(2), allAttributes), is(false)); + } + + @Test void testSplit() { + // FD: 0 -> {1,2,3} + FunctionalDependency fd = FunctionalDependency.of(new int[]{0}, new int[]{1, 2, 3}); + + Set<FunctionalDependency> split = fd.split(); + + FunctionalDependency fd01 = FunctionalDependency.of(0, 1); + FunctionalDependency fd02 = FunctionalDependency.of(0, 2); + FunctionalDependency fd03 = FunctionalDependency.of(0, 3); + + assertThat(split, hasSize(3)); + assertThat(split, containsInAnyOrder(fd01, fd02, fd03)); + } + + @Test void testEquivalence() { + FunctionalDependencySet fdSet1 = new FunctionalDependencySet(); + fdSet1.addFD(0, 1); + fdSet1.addFD(1, 2); + + FunctionalDependencySet fdSet2 = new FunctionalDependencySet(); + fdSet2.addFD(0, 1); + fdSet2.addFD(1, 2); + fdSet2.addFD(0, 2); // 0 -> 2 (redundant) + + // Should be equivalent despite fdSet2 having a redundant FD + assertThat(fdSet1.equalTo(fdSet2), is(true)); + assertThat(fdSet2.equalTo(fdSet1), is(true)); + } + + @Test void testUnion() { + FunctionalDependencySet fdSet1 = new FunctionalDependencySet(); + + // FD: 0 -> 1 + fdSet1.addFD(0, 1); + + FunctionalDependencySet fdSet2 = new FunctionalDependencySet(); + + // FD: 1 -> 2 + fdSet2.addFD(1, 2); + + FunctionalDependencySet union = fdSet1.union(fdSet2); + + assertThat(union.determines(0, 1), is(true)); + assertThat(union.determines(1, 2), is(true)); + assertThat(union.determines(0, 2), is(true)); // 0 -> 2 (transitive) + } + + @Test void testMultipleCandidateKeys() { + FunctionalDependencySet fdSet = new FunctionalDependencySet(); + + ImmutableBitSet bitSet02 = ImmutableBitSet.of(0, 2); + ImmutableBitSet bitSet12 = ImmutableBitSet.of(1, 2); + ImmutableBitSet bitSet3 = ImmutableBitSet.of(3); + + // FDs: 0 <-> 1, {0,2} -> 3, {1,2} -> 3 + fdSet.addFD(0, 1); + fdSet.addFD(1, 0); + fdSet.addFD(bitSet02, bitSet3); + fdSet.addFD(bitSet12, bitSet3); + + ImmutableBitSet allAttributes = FunctionalDependencySet.allAttributesFromFds(fdSet); + Set<ImmutableBitSet> keys = fdSet.findCandidateKeys(allAttributes); + + // Should have two candidate keys + assertThat(keys, hasSize(2)); + + // Both {0,2} and {1,2} should be candidate keys + assertThat(keys, containsInAnyOrder(bitSet02, bitSet12)); + + // Verify both are actually keys + assertThat(fdSet.isKey(bitSet02, allAttributes), is(true)); + assertThat(fdSet.isKey(bitSet12, allAttributes), is(true)); + + // Verify that individual attributes are not keys + assertThat(fdSet.isKey(ImmutableBitSet.of(0), allAttributes), is(false)); + assertThat(fdSet.isKey(ImmutableBitSet.of(1), allAttributes), is(false)); + assertThat(fdSet.isKey(ImmutableBitSet.of(2), allAttributes), is(false)); + assertThat(fdSet.isKey(ImmutableBitSet.of(3), allAttributes), is(false)); + + // Verify superkeys (should not be minimal keys) + assertThat(fdSet.isSuperkey(ImmutableBitSet.of(0, 1, 2), allAttributes), is(true)); + assertThat(fdSet.isKey(ImmutableBitSet.of(0, 1, 2), allAttributes), is(false)); + } + + @Test void testProjectFunctionalDependencies() { + FunctionalDependencySet fdSet = new FunctionalDependencySet(); + + // FDs: 0 -> 1, 1 -> 2 + fdSet.addFD(0, 1); + fdSet.addFD(1, 2); + + // Test closure: {0}+ should include {0, 1, 2} + ImmutableBitSet closure = fdSet.closure(ImmutableBitSet.of(0)); + assertThat(closure, equalTo(ImmutableBitSet.of(0, 1, 2))); + + // Test key finding + Set<ImmutableBitSet> keys = fdSet.findCandidateKeys(ImmutableBitSet.of(0, 1, 2)); + assertThat(keys, hasSize(1)); + assertThat(keys, containsInAnyOrder(ImmutableBitSet.of(0))); + } + + @Test void testClosureWithLargeRelation() { + int numAttrs = 10000; Review Comment: is this the worst case? How about a case where you have several primary keys that have a largish number of columns (e.g., 10)? ########## core/src/main/java/org/apache/calcite/rel/metadata/FunctionalDependencySet.java: ########## @@ -0,0 +1,369 @@ +/* + * Licensed to the Apache Software Foundation (ASF) under one or more + * contributor license agreements. See the NOTICE file distributed with + * this work for additional information regarding copyright ownership. + * The ASF licenses this file to you under the Apache License, Version 2.0 + * (the "License"); you may not use this file except in compliance with + * the License. You may obtain a copy of the License at + * + * http://www.apache.org/licenses/LICENSE-2.0 + * + * Unless required by applicable law or agreed to in writing, software + * distributed under the License is distributed on an "AS IS" BASIS, + * WITHOUT WARRANTIES OR CONDITIONS OF ANY KIND, either express or implied. + * See the License for the specific language governing permissions and + * limitations under the License. + */ +package org.apache.calcite.rel.metadata; + +import org.apache.calcite.util.ImmutableBitSet; + +import com.google.common.collect.ImmutableSet; + +import java.util.ArrayDeque; +import java.util.ArrayList; +import java.util.Collections; +import java.util.Comparator; +import java.util.HashMap; +import java.util.HashSet; +import java.util.List; +import java.util.Map; +import java.util.PriorityQueue; +import java.util.Queue; +import java.util.Set; + +/** + * A set of functional dependencies with closure and minimal cover operations. + * This class implements standard algorithms for functional dependency reasoning. + */ +public class FunctionalDependencySet { + // Maximum number of attributes supported in closure computation + private static final int MAX_CLOSURE_ATTRS = 10000; + + private final Set<FunctionalDependency> fdSet = new HashSet<>(); + + public FunctionalDependencySet() {} + + public FunctionalDependencySet(Set<FunctionalDependency> fds) { + this.fdSet.addAll(fds); + } + + public void addFD(FunctionalDependency fd) { + if (!fd.isTrivial()) { + fdSet.add(fd); + } + } + + public void addFD(ImmutableBitSet determinants, ImmutableBitSet dependents) { + addFD(new FunctionalDependency(determinants, dependents)); + } + + public void addFD(int determinant, int dependent) { + addFD(ImmutableBitSet.of(determinant), ImmutableBitSet.of(dependent)); + } + + public void removeFD(FunctionalDependency fd) { + fdSet.remove(fd); + } + + public Set<FunctionalDependency> getFDs() { + return Collections.unmodifiableSet(fdSet); + } + + public boolean isEmpty() { + return fdSet.isEmpty(); + } + + public int size() { + return fdSet.size(); + } + + /** + * Returns an ImmutableBitSet containing all attribute indexes that appear in any FD in the set. + */ + public static ImmutableBitSet allAttributesFromFds(FunctionalDependencySet fds) { + ImmutableBitSet.Builder builder = ImmutableBitSet.builder(); + Set<FunctionalDependency> fdSet = fds.getFDs(); + for (FunctionalDependency fd : fdSet) { + builder.addAll(fd.getDeterminants()); + builder.addAll(fd.getDependents()); + } + return builder.build(); + } + + /** + * Computes the closure of a set of attributes under this functional dependency set. + * The closure of X, denoted X+, is the set of all attributes that can be functionally + * determined by X using the functional dependencies in this set and Armstrong's axioms. + * + * @param attributes the input attribute set + * @return the closure of the input attributes + */ + public ImmutableBitSet closure(ImmutableBitSet attributes) { + if (attributes.isEmpty()) { + return attributes; + } + + if (attributes.cardinality() > MAX_CLOSURE_ATTRS) { + throw new IllegalArgumentException( + "closure only supports up to " + MAX_CLOSURE_ATTRS + + " attributes, but got " + attributes.cardinality()); + } + + Set<Integer> closureSet = new HashSet<>(); + Queue<Integer> queue = new ArrayDeque<>(); + for (int attr : attributes) { + closureSet.add(attr); + queue.add(attr); + } + + Map<FunctionalDependency, Integer> fdMissingCount = new HashMap<>(); + Map<Integer, List<FunctionalDependency>> attrToFDs = new HashMap<>(); + for (FunctionalDependency fd : fdSet) { + fdMissingCount.put(fd, fd.getDeterminants().cardinality()); + for (int det : fd.getDeterminants()) { + attrToFDs.computeIfAbsent(det, k -> new ArrayList<>()).add(fd); + } + } + + while (!queue.isEmpty()) { + Integer attr = queue.poll(); + if (attr == null) { + continue; + } + List<FunctionalDependency> fds = attrToFDs.get(attr); + if (fds == null) { + continue; + } + for (FunctionalDependency fd : fds) { + Integer missing = fdMissingCount.get(fd); + if (missing == null) { + continue; + } + missing = missing - 1; + fdMissingCount.put(fd, missing); + if (missing == 0) { + for (int dep : fd.getDependents()) { + if (closureSet.add(dep)) { + queue.add(dep); + } + } + } + } + } + + return ImmutableBitSet.of(closureSet); + } + + /** + * Check if X determined Y is implied by this FD set. + */ + public boolean implies(ImmutableBitSet determinants, ImmutableBitSet dependents) { + return closure(determinants).contains(dependents); + } + + /** + * Check if a single column is functionally determined by another column. + */ + public boolean determines(int determinant, int dependent) { + return closure(ImmutableBitSet.of(determinant)).get(dependent); + } + + /** + * Compute the minimal cover of this functional dependency set. + * Returns an equivalent set with minimal dependencies. + */ + public FunctionalDependencySet minimalCover() { + // Split multi-attribute right sides into single attributes + Set<FunctionalDependency> splitFDs = new HashSet<>(); + for (FunctionalDependency fd : fdSet) { + splitFDs.addAll(fd.split()); + } + splitFDs.removeIf(FunctionalDependency::isTrivial); + + // Remove redundant attributes from left sides + Set<FunctionalDependency> reducedFDs = new HashSet<>(); + for (FunctionalDependency fd : splitFDs) { + FunctionalDependencySet tempSet = new FunctionalDependencySet(splitFDs); + tempSet.removeFD(fd); + reducedFDs.add(reduceLeft(fd, tempSet)); + } + + // Remove redundant functional dependencies + reducedFDs.removeIf(fd -> { + FunctionalDependencySet remainingFDs = new FunctionalDependencySet(reducedFDs); + remainingFDs.removeFD(fd); + return remainingFDs.implies(fd.getDeterminants(), fd.getDependents()); + }); + + return new FunctionalDependencySet(reducedFDs); + } + + /** + * Reduce left side by removing redundant columns from determinants. + */ + private static FunctionalDependency reduceLeft(FunctionalDependency fd, + FunctionalDependencySet fdSet) { + ImmutableBitSet determinants = fd.getDeterminants(); + ImmutableBitSet dependents = fd.getDependents(); + + // Try removing each attribute to find minimal determinant set + for (int attr : fd.getDeterminants()) { + ImmutableBitSet reduced = determinants.clear(attr); + if (fdSet.closure(reduced).contains(dependents)) { + determinants = reduced; + } + } + return new FunctionalDependency(determinants, dependents); + } + + /** + * Check if this FD set is equivalent to another FD set. + * Two FD sets are equivalent if they have the same closure for any attribute set. + */ + public boolean equalTo(FunctionalDependencySet other) { + // Check if every FD in this set is implied by the other set + for (FunctionalDependency fd : fdSet) { + if (!other.implies(fd.getDeterminants(), fd.getDependents())) { + return false; + } + } + // Check if every FD in the other set is implied by this set + for (FunctionalDependency fd : other.fdSet) { + if (!implies(fd.getDeterminants(), fd.getDependents())) { + return false; + } + } + return true; + } + + /** + * Find all candidate keys within the given attribute set. + * A candidate key is a minimal subset of the given attributes such that + * its closure contains all the given attributes. + * + * @param attributes the set of attributes to search for candidate keys within + * @return a set of minimal attribute subsets that can determine all given attributes + */ + public Set<ImmutableBitSet> findCandidateKeys(ImmutableBitSet attributes) { Review Comment: The number of keys can be exponential in the size of the attributes in the worst case. I don't know how often this happens in practice. ########## core/src/main/java/org/apache/calcite/rel/metadata/RelMdFunctionalDependency.java: ########## @@ -64,212 +76,422 @@ protected RelMdFunctionalDependency() {} return BuiltInMetadata.FunctionalDependency.DEF; } + /** + * Determines if column is functionally dependent on key for a given rel node. + */ public @Nullable Boolean determines(RelNode rel, RelMetadataQuery mq, int key, int column) { - return determinesImpl2(rel, mq, key, column); + return determinesSet(rel, mq, ImmutableBitSet.of(key), ImmutableBitSet.of(column)); } - public @Nullable Boolean determines(SetOp rel, RelMetadataQuery mq, - int key, int column) { - return determinesImpl2(rel, mq, key, column); + /** + * Determines if a set of columns functionally determines another set of columns. + */ + public Boolean determinesSet(RelNode rel, RelMetadataQuery mq, + ImmutableBitSet determinants, ImmutableBitSet dependents) { + FunctionalDependencySet fdSet = mq.getFunctionalDependencies(rel); + return fdSet.implies(determinants, dependents); } - public @Nullable Boolean determines(Join rel, RelMetadataQuery mq, - int key, int column) { - return determinesImpl2(rel, mq, key, column); + /** + * Returns the closure of a set of columns under all functional dependencies. + */ + public ImmutableBitSet closure(RelNode rel, RelMetadataQuery mq, ImmutableBitSet attrs) { + FunctionalDependencySet fdSet = mq.getFunctionalDependencies(rel); + return fdSet.closure(attrs); } - public @Nullable Boolean determines(Correlate rel, RelMetadataQuery mq, - int key, int column) { - return determinesImpl2(rel, mq, key, column); + /** + * Returns candidate keys for the relation within the specified set of attributes. + */ + public Set<ImmutableBitSet> candidateKeys( + RelNode rel, RelMetadataQuery mq, ImmutableBitSet attributes) { + FunctionalDependencySet fdSet = mq.getFunctionalDependencies(rel); + return fdSet.findCandidateKeys(attributes); } - public @Nullable Boolean determines(Aggregate rel, RelMetadataQuery mq, - int key, int column) { - return determinesImpl(rel, mq, key, column); + /** + * Main dispatch method for getFunctionalDependencies. + * Routes to appropriate handler based on RelNode type. + */ + public FunctionalDependencySet getFunctionalDependencies(RelNode rel, RelMetadataQuery mq) { + if (rel instanceof TableScan) { + return getTableScanFD((TableScan) rel); + } else if (rel instanceof Project) { + return getProjectFD((Project) rel, mq); + } else if (rel instanceof Aggregate) { + return getAggregateFD((Aggregate) rel, mq); + } else if (rel instanceof Join) { + return getJoinFD((Join) rel, mq); + } else if (rel instanceof Calc) { + return getCalcFD((Calc) rel, mq); + } else if (rel instanceof SetOp) { + // TODO: Handle UNION, INTERSECT, EXCEPT functional dependencies + return new FunctionalDependencySet(); + } else if (rel instanceof Correlate) { + // TODO: Handle CORRELATE functional dependencies + return new FunctionalDependencySet(); + } + return getFD(rel.getInputs(), mq); } - public @Nullable Boolean determines(Calc rel, RelMetadataQuery mq, - int key, int column) { - return determinesImpl(rel, mq, key, column); + private static FunctionalDependencySet getFD(List<RelNode> inputs, RelMetadataQuery mq) { + FunctionalDependencySet result = new FunctionalDependencySet(); + for (RelNode input : inputs) { + FunctionalDependencySet fdSet = mq.getFunctionalDependencies(input); + result = result.union(fdSet); + } + return result; } - public @Nullable Boolean determines(Project rel, RelMetadataQuery mq, - int key, int column) { - return determinesImpl(rel, mq, key, column); - } + private static FunctionalDependencySet getTableScanFD(TableScan rel) { + FunctionalDependencySet fdSet = new FunctionalDependencySet(); - /** - * Checks if a column is functionally determined by a key column through expression analysis. - * - * @param rel The input relation - * @param mq Metadata query instance - * @param key Index of the determinant expression - * @param column Index of the dependent expression - * @return TRUE if column is determined by key, - * FALSE if not determined, - * NULL if undetermined - */ - private static @Nullable Boolean determinesImpl(RelNode rel, RelMetadataQuery mq, - int key, int column) { - if (preCheck(rel, key, column)) { - return true; + RelOptTable table = rel.getTable(); + List<ImmutableBitSet> keys = table.getKeys(); + if (keys == null || keys.isEmpty()) { + return fdSet; } - ImmutableBitSet keyInputIndices = null; - ImmutableBitSet columnInputIndices = null; - if (rel instanceof Project || rel instanceof Calc) { - List<RexNode> exprs = null; - if (rel instanceof Project) { - Project project = (Project) rel; - exprs = project.getProjects(); - } else { - Calc calc = (Calc) rel; - final RexProgram program = calc.getProgram(); - exprs = program.expandList(program.getProjectList()); + for (ImmutableBitSet key : keys) { + ImmutableBitSet allColumns = ImmutableBitSet.range(rel.getRowType().getFieldCount()); + ImmutableBitSet dependents = allColumns.except(key); + if (!dependents.isEmpty()) { + fdSet.addFD(key, dependents); } + } - // TODO: Supports dependency analysis for all types of expressions - if (!(exprs.get(column) instanceof RexInputRef)) { - return false; - } + return fdSet; + } - RexNode keyExpr = exprs.get(key); - RexNode columnExpr = exprs.get(column); + private static FunctionalDependencySet getProjectFD(Project rel, RelMetadataQuery mq) { + return getProjectionFD(rel.getInput(), rel.getProjects(), mq); + } - // Identical expressions imply functional dependency - if (keyExpr.equals(columnExpr)) { - return true; + /** + * Common method to compute functional dependencies for projection operations. + * Used by both Project and Calc nodes. + * + * @param input the input relation + * @param projections the list of projection expressions + * @param mq the metadata query + * @return the functional dependency set for the projection + */ + private static FunctionalDependencySet getProjectionFD( + RelNode input, List<RexNode> projections, RelMetadataQuery mq) { + FunctionalDependencySet inputFdSet = mq.getFunctionalDependencies(input); + FunctionalDependencySet projectionFdSet = new FunctionalDependencySet(); + int fieldCount = projections.size(); + + // Create mapping from input column indices to project column indices + Mappings.TargetMapping inputToOutputMap = + RelOptUtil.permutation(projections, input.getRowType()); + + // Map input functional dependencies to project dependencies + mapInputFDs(inputFdSet, inputToOutputMap, projectionFdSet); + + // For each pair of output columns, determine if one determines the other + for (int i = 0; i < fieldCount; i++) { + for (int j = i + 1; j < fieldCount; j++) { + RexNode expr1 = projections.get(i); + RexNode expr2 = projections.get(j); + + // Handle identical expressions, they determine each other + if (expr1.equals(expr2) && RexUtil.isDeterministic(expr1)) { + projectionFdSet.addFD(i, j); + projectionFdSet.addFD(j, i); + continue; + } + + // Handle literal constants, all columns determine literals + if (expr1 instanceof RexLiteral) { + projectionFdSet.addFD(j, i); + } + if (expr2 instanceof RexLiteral) { + projectionFdSet.addFD(i, j); + } + + // For complex expressions, check if they have functional dependencies + if (!(expr1 instanceof RexLiteral) && !(expr2 instanceof RexLiteral) + && RexUtil.isDeterministic(expr1) && RexUtil.isDeterministic(expr2)) { + ImmutableBitSet inputs1 = RelOptUtil.InputFinder.bits(expr1); + ImmutableBitSet inputs2 = RelOptUtil.InputFinder.bits(expr2); + + if (!inputs1.isEmpty() && !inputs2.isEmpty()) { + if (inputFdSet.implies(inputs1, inputs2)) { + projectionFdSet.addFD(i, j); + } + if (inputFdSet.implies(inputs2, inputs1)) { + projectionFdSet.addFD(j, i); + } + } + } } + } - keyInputIndices = extractDeterministicRefs(keyExpr); - columnInputIndices = extractDeterministicRefs(columnExpr); - } else if (rel instanceof Aggregate) { - Aggregate aggregate = (Aggregate) rel; + return projectionFdSet; + } - int groupByCnt = aggregate.getGroupCount(); - if (key < groupByCnt && column >= groupByCnt) { - return false; + /** + * Maps input functional dependencies to output dependencies based on column mapping. + */ + private static void mapInputFDs(FunctionalDependencySet inputFdSet, + Mappings.TargetMapping mapping, FunctionalDependencySet outputFdSet) { + for (FunctionalDependency inputFd : inputFdSet.getFDs()) { + ImmutableBitSet determinants = inputFd.getDeterminants(); + ImmutableBitSet dependents = inputFd.getDependents(); + + // Skip this FD if any determinant column is unmappable + boolean allMappable = + determinants.stream().allMatch(col -> col >= 0 + && col < mapping.getSourceCount() + && mapping.getTargetOpt(col) >= 0); + if (!allMappable) { + continue; } - keyInputIndices = extractDeterministicRefs(aggregate, key); - columnInputIndices = extractDeterministicRefs(aggregate, column); - } else { - throw new UnsupportedOperationException("Unsupported RelNode type: " - + rel.getClass().getSimpleName()); - } + // Map all determinant columns + ImmutableBitSet mappedDeterminants = mapAllCols(determinants, mapping); + if (mappedDeterminants.isEmpty()) { + continue; + } - // Early return if invalid cases - if (keyInputIndices.isEmpty() - || columnInputIndices.isEmpty()) { - return false; + // Map only the dependent columns that can be mapped + ImmutableBitSet mappedDependents = mapAvailableCols(dependents, mapping); + if (!mappedDependents.isEmpty()) { + outputFdSet.addFD(mappedDeterminants, mappedDependents); + } } + } - // Currently only supports multiple (keyInputIndices) to one (columnInputIndices) - // dependency detection - for (Integer keyRef : keyInputIndices) { - if (Boolean.FALSE.equals( - mq.determines(rel.getInput(0), keyRef, - columnInputIndices.nextSetBit(0)))) { - return false; + /** + * Maps all columns in the set. Returns empty set if any column cannot be mapped. + */ + private static ImmutableBitSet mapAllCols( + ImmutableBitSet columns, Mappings.TargetMapping mapping) { + ImmutableBitSet.Builder builder = ImmutableBitSet.builder(); + for (int col : columns) { + if (col < 0 || col >= mapping.getSourceCount()) { + return ImmutableBitSet.of(); + } + int mappedCol = mapping.getTargetOpt(col); + if (mappedCol >= 0) { + builder.set(mappedCol); + } else { + return ImmutableBitSet.of(); } } - - return true; + return builder.build(); } /** - * determinesImpl2is similar to determinesImpl, but it doesn't need to handle the - * mapping between output and input columns. + * Maps only the columns that can be mapped, ignoring unmappable ones. */ - private static @Nullable Boolean determinesImpl2(RelNode rel, RelMetadataQuery mq, - int key, int column) { - if (preCheck(rel, key, column)) { - return true; + private static ImmutableBitSet mapAvailableCols( + ImmutableBitSet columns, Mappings.TargetMapping mapping) { + ImmutableBitSet.Builder builder = ImmutableBitSet.builder(); + for (int col : columns) { + if (col < 0 || col >= mapping.getSourceCount()) { + continue; + } + int mappedCol = mapping.getTargetOpt(col); + if (mappedCol >= 0) { + builder.set(mappedCol); + } + } + return builder.build(); + } + + private static FunctionalDependencySet getAggregateFD(Aggregate rel, RelMetadataQuery mq) { + FunctionalDependencySet fdSet = new FunctionalDependencySet(); + + FunctionalDependencySet inputFdSet = mq.getFunctionalDependencies(rel.getInput()); + + // Group set columns in the output + ImmutableBitSet groupSet = rel.getGroupSet(); + + // 1. Preserve input FDs that only involve group columns + for (FunctionalDependency inputFd : inputFdSet.getFDs()) { + ImmutableBitSet determinants = inputFd.getDeterminants(); + ImmutableBitSet dependents = inputFd.getDependents(); + + // Only preserve if both determinants and dependents are within group columns + if (groupSet.contains(determinants) && groupSet.contains(dependents)) { + fdSet.addFD(determinants, dependents); + } } - if (rel instanceof TableScan) { - TableScan tableScan = (TableScan) rel; - RelOptTable table = tableScan.getTable(); - List<ImmutableBitSet> keys = table.getKeys(); - return keys != null - && keys.size() == 1 - && keys.get(0).equals(ImmutableBitSet.of(column)); - } else if (rel instanceof Join) { - Join join = (Join) rel; - // TODO Considering column mapping based on equality conditions in join - int leftFieldCnt = join.getLeft().getRowType().getFieldCount(); - if (key < leftFieldCnt && column < leftFieldCnt) { - return mq.determines(join.getLeft(), key, column); - } else if (key >= leftFieldCnt && column >= leftFieldCnt) { - return mq.determines(join.getRight(), key - leftFieldCnt, column - leftFieldCnt); + // 2. Group keys determine all aggregate columns + if (!groupSet.isEmpty() && !rel.getAggCallList().isEmpty()) { + for (int i = rel.getGroupCount(); i < rel.getRowType().getFieldCount(); i++) { + fdSet.addFD(groupSet, ImmutableBitSet.of(i)); } - return false; - } else if (rel instanceof Correlate) { - // TODO Support Correlate. - return false; - } else if (rel instanceof SetOp) { - // TODO Support SetOp - return false; } - return mq.determines(rel.getInput(0), key, column); + return fdSet; } - private static Boolean preCheck(RelNode rel, int key, int column) { - verifyIndex(rel, key, column); + private static FunctionalDependencySet getJoinFD(Join rel, RelMetadataQuery mq) { + FunctionalDependencySet leftFdSet = mq.getFunctionalDependencies(rel.getLeft()); + FunctionalDependencySet rightFdSet = mq.getFunctionalDependencies(rel.getRight()); + + int leftFieldCount = rel.getLeft().getRowType().getFieldCount(); + JoinRelType joinType = rel.getJoinType(); + + switch (joinType) { + case INNER: + // Inner join: preserve all FDs and derive cross-table dependencies + FunctionalDependencySet innerJoinFdSet + = leftFdSet.union(shiftFdSet(rightFdSet, leftFieldCount)); + deriveTransitiveFDs(rel, innerJoinFdSet, leftFieldCount); + return innerJoinFdSet; + case LEFT: + // Left join: preserve left FDs, right FDs may be invalidated by NULLs + FunctionalDependencySet leftJoinFdSet = new FunctionalDependencySet(leftFdSet.getFDs()); + deriveTransitiveFDs(rel, leftJoinFdSet, leftFieldCount); + return leftJoinFdSet; + case RIGHT: + // Right join: preserve right FDs, left FDs may be invalidated by NULLs + FunctionalDependencySet shiftedRightFdSet = shiftFdSet(rightFdSet, leftFieldCount); Review Comment: this is still not symmetric with left - the transitive part is missing. ########## core/src/main/java/org/apache/calcite/rel/metadata/FunctionalDependencySet.java: ########## @@ -0,0 +1,369 @@ +/* + * Licensed to the Apache Software Foundation (ASF) under one or more + * contributor license agreements. See the NOTICE file distributed with + * this work for additional information regarding copyright ownership. + * The ASF licenses this file to you under the Apache License, Version 2.0 + * (the "License"); you may not use this file except in compliance with + * the License. You may obtain a copy of the License at + * + * http://www.apache.org/licenses/LICENSE-2.0 + * + * Unless required by applicable law or agreed to in writing, software + * distributed under the License is distributed on an "AS IS" BASIS, + * WITHOUT WARRANTIES OR CONDITIONS OF ANY KIND, either express or implied. + * See the License for the specific language governing permissions and + * limitations under the License. + */ +package org.apache.calcite.rel.metadata; + +import org.apache.calcite.util.ImmutableBitSet; + +import com.google.common.collect.ImmutableSet; + +import java.util.ArrayDeque; +import java.util.ArrayList; +import java.util.Collections; +import java.util.Comparator; +import java.util.HashMap; +import java.util.HashSet; +import java.util.List; +import java.util.Map; +import java.util.PriorityQueue; +import java.util.Queue; +import java.util.Set; + +/** + * A set of functional dependencies with closure and minimal cover operations. + * This class implements standard algorithms for functional dependency reasoning. + */ +public class FunctionalDependencySet { + // Maximum number of attributes supported in closure computation + private static final int MAX_CLOSURE_ATTRS = 10000; + + private final Set<FunctionalDependency> fdSet = new HashSet<>(); + + public FunctionalDependencySet() {} + + public FunctionalDependencySet(Set<FunctionalDependency> fds) { + this.fdSet.addAll(fds); + } + + public void addFD(FunctionalDependency fd) { + if (!fd.isTrivial()) { + fdSet.add(fd); + } + } + + public void addFD(ImmutableBitSet determinants, ImmutableBitSet dependents) { + addFD(new FunctionalDependency(determinants, dependents)); + } + + public void addFD(int determinant, int dependent) { + addFD(ImmutableBitSet.of(determinant), ImmutableBitSet.of(dependent)); + } + + public void removeFD(FunctionalDependency fd) { + fdSet.remove(fd); + } + + public Set<FunctionalDependency> getFDs() { + return Collections.unmodifiableSet(fdSet); + } + + public boolean isEmpty() { + return fdSet.isEmpty(); + } + + public int size() { + return fdSet.size(); + } + + /** + * Returns an ImmutableBitSet containing all attribute indexes that appear in any FD in the set. + */ + public static ImmutableBitSet allAttributesFromFds(FunctionalDependencySet fds) { + ImmutableBitSet.Builder builder = ImmutableBitSet.builder(); + Set<FunctionalDependency> fdSet = fds.getFDs(); + for (FunctionalDependency fd : fdSet) { + builder.addAll(fd.getDeterminants()); + builder.addAll(fd.getDependents()); + } + return builder.build(); + } + + /** + * Computes the closure of a set of attributes under this functional dependency set. + * The closure of X, denoted X+, is the set of all attributes that can be functionally + * determined by X using the functional dependencies in this set and Armstrong's axioms. + * + * @param attributes the input attribute set + * @return the closure of the input attributes + */ + public ImmutableBitSet closure(ImmutableBitSet attributes) { + if (attributes.isEmpty()) { + return attributes; + } + + if (attributes.cardinality() > MAX_CLOSURE_ATTRS) { + throw new IllegalArgumentException( + "closure only supports up to " + MAX_CLOSURE_ATTRS + + " attributes, but got " + attributes.cardinality()); + } + + Set<Integer> closureSet = new HashSet<>(); + Queue<Integer> queue = new ArrayDeque<>(); + for (int attr : attributes) { + closureSet.add(attr); + queue.add(attr); + } + + Map<FunctionalDependency, Integer> fdMissingCount = new HashMap<>(); + Map<Integer, List<FunctionalDependency>> attrToFDs = new HashMap<>(); + for (FunctionalDependency fd : fdSet) { + fdMissingCount.put(fd, fd.getDeterminants().cardinality()); + for (int det : fd.getDeterminants()) { + attrToFDs.computeIfAbsent(det, k -> new ArrayList<>()).add(fd); + } + } + + while (!queue.isEmpty()) { + Integer attr = queue.poll(); + if (attr == null) { + continue; + } + List<FunctionalDependency> fds = attrToFDs.get(attr); + if (fds == null) { + continue; + } + for (FunctionalDependency fd : fds) { + Integer missing = fdMissingCount.get(fd); + if (missing == null) { + continue; + } + missing = missing - 1; + fdMissingCount.put(fd, missing); + if (missing == 0) { + for (int dep : fd.getDependents()) { + if (closureSet.add(dep)) { + queue.add(dep); + } + } + } + } + } + + return ImmutableBitSet.of(closureSet); + } + + /** + * Check if X determined Y is implied by this FD set. + */ + public boolean implies(ImmutableBitSet determinants, ImmutableBitSet dependents) { + return closure(determinants).contains(dependents); + } + + /** + * Check if a single column is functionally determined by another column. + */ + public boolean determines(int determinant, int dependent) { + return closure(ImmutableBitSet.of(determinant)).get(dependent); + } + + /** + * Compute the minimal cover of this functional dependency set. + * Returns an equivalent set with minimal dependencies. + */ + public FunctionalDependencySet minimalCover() { + // Split multi-attribute right sides into single attributes + Set<FunctionalDependency> splitFDs = new HashSet<>(); + for (FunctionalDependency fd : fdSet) { + splitFDs.addAll(fd.split()); + } + splitFDs.removeIf(FunctionalDependency::isTrivial); + + // Remove redundant attributes from left sides + Set<FunctionalDependency> reducedFDs = new HashSet<>(); + for (FunctionalDependency fd : splitFDs) { + FunctionalDependencySet tempSet = new FunctionalDependencySet(splitFDs); + tempSet.removeFD(fd); + reducedFDs.add(reduceLeft(fd, tempSet)); + } + + // Remove redundant functional dependencies + reducedFDs.removeIf(fd -> { + FunctionalDependencySet remainingFDs = new FunctionalDependencySet(reducedFDs); + remainingFDs.removeFD(fd); + return remainingFDs.implies(fd.getDeterminants(), fd.getDependents()); + }); + + return new FunctionalDependencySet(reducedFDs); + } + + /** + * Reduce left side by removing redundant columns from determinants. + */ + private static FunctionalDependency reduceLeft(FunctionalDependency fd, + FunctionalDependencySet fdSet) { + ImmutableBitSet determinants = fd.getDeterminants(); + ImmutableBitSet dependents = fd.getDependents(); + + // Try removing each attribute to find minimal determinant set + for (int attr : fd.getDeterminants()) { + ImmutableBitSet reduced = determinants.clear(attr); + if (fdSet.closure(reduced).contains(dependents)) { + determinants = reduced; + } + } + return new FunctionalDependency(determinants, dependents); + } + + /** + * Check if this FD set is equivalent to another FD set. + * Two FD sets are equivalent if they have the same closure for any attribute set. + */ + public boolean equalTo(FunctionalDependencySet other) { + // Check if every FD in this set is implied by the other set + for (FunctionalDependency fd : fdSet) { + if (!other.implies(fd.getDeterminants(), fd.getDependents())) { Review Comment: implies calls closure, so this test looks quite expensive in the worst case. ########## core/src/main/java/org/apache/calcite/rel/metadata/RelMdFunctionalDependency.java: ########## @@ -64,212 +76,445 @@ protected RelMdFunctionalDependency() {} return BuiltInMetadata.FunctionalDependency.DEF; } + /** + * Determines if column is functionally dependent on key for a given rel node. + */ public @Nullable Boolean determines(RelNode rel, RelMetadataQuery mq, int key, int column) { - return determinesImpl2(rel, mq, key, column); + return determinesSet(rel, mq, ImmutableBitSet.of(key), ImmutableBitSet.of(column)); } - public @Nullable Boolean determines(SetOp rel, RelMetadataQuery mq, - int key, int column) { - return determinesImpl2(rel, mq, key, column); + /** + * Determines if a set of columns functionally determines another set of columns. + */ + public Boolean determinesSet(RelNode rel, RelMetadataQuery mq, + ImmutableBitSet determinants, ImmutableBitSet dependents) { + FunctionalDependencySet fdSet = mq.getFunctionalDependencies(rel); + return fdSet.implies(determinants, dependents); } - public @Nullable Boolean determines(Join rel, RelMetadataQuery mq, - int key, int column) { - return determinesImpl2(rel, mq, key, column); + /** + * Returns the closure of a set of columns under all functional dependencies. + */ + public ImmutableBitSet closure(RelNode rel, RelMetadataQuery mq, ImmutableBitSet attrs) { + FunctionalDependencySet fdSet = mq.getFunctionalDependencies(rel); + return fdSet.closure(attrs); } - public @Nullable Boolean determines(Correlate rel, RelMetadataQuery mq, - int key, int column) { - return determinesImpl2(rel, mq, key, column); + /** + * Returns candidate keys for the relation within the specified set of attributes. + */ + public Set<ImmutableBitSet> candidateKeys( + RelNode rel, RelMetadataQuery mq, ImmutableBitSet attributes) { + FunctionalDependencySet fdSet = mq.getFunctionalDependencies(rel); + return fdSet.findKeys(attributes); } - public @Nullable Boolean determines(Aggregate rel, RelMetadataQuery mq, - int key, int column) { - return determinesImpl(rel, mq, key, column); + /** + * Main dispatch method for getFunctionalDependencies. + * Routes to appropriate handler based on RelNode type. + */ + public FunctionalDependencySet getFunctionalDependencies(RelNode rel, RelMetadataQuery mq) { + if (rel instanceof TableScan) { + return getTableScanFD((TableScan) rel); + } else if (rel instanceof Project) { + return getProjectFD((Project) rel, mq); + } else if (rel instanceof Aggregate) { + return getAggregateFD((Aggregate) rel, mq); + } else if (rel instanceof Join) { + return getJoinFD((Join) rel, mq); + } else if (rel instanceof Calc) { + return getCalcFD((Calc) rel, mq); + } else if (rel instanceof SetOp) { + // TODO: Handle UNION, INTERSECT, EXCEPT functional dependencies + return new FunctionalDependencySet(); + } else if (rel instanceof Correlate) { + // TODO: Handle CORRELATE functional dependencies + return new FunctionalDependencySet(); + } + return getFD(rel.getInputs(), mq); } - public @Nullable Boolean determines(Calc rel, RelMetadataQuery mq, - int key, int column) { - return determinesImpl(rel, mq, key, column); + private static FunctionalDependencySet getFD(List<RelNode> inputs, RelMetadataQuery mq) { + FunctionalDependencySet result = new FunctionalDependencySet(); + for (RelNode input : inputs) { + FunctionalDependencySet fdSet = mq.getFunctionalDependencies(input); + result = result.union(fdSet); Review Comment: if the inputs are supposed to have the same schema for this to work, please document this. Just because a function is private does not mean it should not have JavaDoc. -- This is an automated message from the Apache Git Service. To respond to the message, please log on to GitHub and use the URL above to go to the specific comment. To unsubscribe, e-mail: [email protected] For queries about this service, please contact Infrastructure at: [email protected]
