diff options
Diffstat (limited to 'subprojects/viatra-runtime/src/main/java/tools/refinery/viatra/runtime/matchers/planning/helpers/FunctionalDependencyHelper.java')
-rw-r--r-- | subprojects/viatra-runtime/src/main/java/tools/refinery/viatra/runtime/matchers/planning/helpers/FunctionalDependencyHelper.java | 143 |
1 files changed, 143 insertions, 0 deletions
diff --git a/subprojects/viatra-runtime/src/main/java/tools/refinery/viatra/runtime/matchers/planning/helpers/FunctionalDependencyHelper.java b/subprojects/viatra-runtime/src/main/java/tools/refinery/viatra/runtime/matchers/planning/helpers/FunctionalDependencyHelper.java new file mode 100644 index 00000000..40835f52 --- /dev/null +++ b/subprojects/viatra-runtime/src/main/java/tools/refinery/viatra/runtime/matchers/planning/helpers/FunctionalDependencyHelper.java | |||
@@ -0,0 +1,143 @@ | |||
1 | /******************************************************************************* | ||
2 | * Copyright (c) 2010-2013, Adam Dudas, Istvan Rath and Daniel Varro | ||
3 | * This program and the accompanying materials are made available under the | ||
4 | * terms of the Eclipse Public License v. 2.0 which is available at | ||
5 | * http://www.eclipse.org/legal/epl-v20.html. | ||
6 | * | ||
7 | * SPDX-License-Identifier: EPL-2.0 | ||
8 | *******************************************************************************/ | ||
9 | package tools.refinery.viatra.runtime.matchers.planning.helpers; | ||
10 | |||
11 | import java.util.Collection; | ||
12 | import java.util.Collections; | ||
13 | import java.util.HashMap; | ||
14 | import java.util.HashSet; | ||
15 | import java.util.Map; | ||
16 | import java.util.Map.Entry; | ||
17 | import java.util.Set; | ||
18 | |||
19 | import tools.refinery.viatra.runtime.matchers.util.Sets; | ||
20 | |||
21 | /** | ||
22 | * Helper utility class for functional dependency analysis. | ||
23 | * | ||
24 | * Throughout this class attribute sets are represented as generic sets and functional dependencies as maps from | ||
25 | * attribute set (generic sets) to attribute set (generic sets) | ||
26 | * | ||
27 | * @author Adam Dudas | ||
28 | * | ||
29 | */ | ||
30 | public class FunctionalDependencyHelper { | ||
31 | |||
32 | private FunctionalDependencyHelper() { | ||
33 | // Hiding constructor for utility class | ||
34 | } | ||
35 | |||
36 | /** | ||
37 | * Get the closure of the specified attribute set relative to the specified functional dependencies. | ||
38 | * | ||
39 | * @param attributes | ||
40 | * The attributes to get the closure of. | ||
41 | * @param dependencies | ||
42 | * The functional dependencies of which the closure operation is relative to. | ||
43 | * @return The closure of the specified attribute set relative to the specified functional dependencies. | ||
44 | */ | ||
45 | public static <A> Set<A> closureOf(Collection<A> attributes, Map<Set<A>, Set<A>> dependencies) { | ||
46 | Set<A> closureSet = new HashSet<A>(); | ||
47 | |||
48 | for (Set<A> closureSet1 = new HashSet<A>(attributes); closureSet.addAll(closureSet1);) { | ||
49 | closureSet1 = new HashSet<A>(); | ||
50 | for (Entry<Set<A>, Set<A>> dependency : dependencies.entrySet()) { | ||
51 | if (closureSet.containsAll(dependency.getKey())) | ||
52 | closureSet1.addAll(dependency.getValue()); | ||
53 | } | ||
54 | } | ||
55 | |||
56 | return closureSet; | ||
57 | } | ||
58 | |||
59 | /** | ||
60 | * @return true if the dependency from the left set to the right set is trivial | ||
61 | * @since 1.5 | ||
62 | */ | ||
63 | public static <A> boolean isTrivial(Set<A> left, Set<A> right) { | ||
64 | return left.containsAll(right); | ||
65 | } | ||
66 | |||
67 | /*** | ||
68 | * Returns the dependency set over attributes in {@link targetAttributes} that are implied by a given source dependency set. | ||
69 | * <p> Note: exponential in the size of the target attribute set. | ||
70 | * <p> Note: minimality of the returned dependency set is currently not guaranteed. | ||
71 | * @param originalDependencies all dependencies that are known to hold on a wider set of attributes | ||
72 | * @param targetAttributes the set of attributes we are interested in | ||
73 | * @since 1.5 | ||
74 | */ | ||
75 | public static <A> Map<Set<A>, Set<A>> projectDependencies(Map<Set<A>, Set<A>> originalDependencies, Set<A> targetAttributes) { | ||
76 | // only those attributes are considered as left-hand-side candidates that occur at least once in dependencies | ||
77 | Set<A> leftCandidates = new HashSet<A>(); | ||
78 | for (Entry<Set<A>, Set<A>> dependency : originalDependencies.entrySet()) { | ||
79 | if (!isTrivial(dependency.getKey(), dependency.getValue())) // only if non-trivial | ||
80 | leftCandidates.addAll(Sets.intersection(dependency.getKey(), targetAttributes)); | ||
81 | } | ||
82 | |||
83 | // Compute an initial list of nontrivial projected dependencies - it does not have to be minimal yet | ||
84 | Map<Set<A>, Set<A>> initialDependencies = new HashMap<Set<A>, Set<A>>(); | ||
85 | for (Set<A> leftSet : Sets.powerSet(leftCandidates)) { | ||
86 | Set<A> rightSet = Sets.intersection(closureOf(leftSet, originalDependencies), targetAttributes); | ||
87 | if (!isTrivial(leftSet, rightSet)) { | ||
88 | initialDependencies.put(leftSet, rightSet); | ||
89 | } | ||
90 | } | ||
91 | // Don't forget to include constants! | ||
92 | Set<A> constants = Sets.intersection(closureOf(Collections.<A>emptySet(), originalDependencies), targetAttributes); | ||
93 | if (! constants.isEmpty()) { | ||
94 | initialDependencies.put(Collections.<A>emptySet(), constants); | ||
95 | } | ||
96 | |||
97 | // Omit those dependencies where the LHS has superfluous attributes | ||
98 | Map<Set<A>, Set<A>> solidDependencies = new HashMap<Set<A>, Set<A>>(); | ||
99 | for (Entry<Set<A>, Set<A>> dependency : initialDependencies.entrySet()) { | ||
100 | Set<A> leftSet = dependency.getKey(); | ||
101 | Set<A> rightSet = dependency.getValue(); | ||
102 | boolean solid = true; | ||
103 | for (A skipped : leftSet) { // what if we skip one attribute from the left set? | ||
104 | Set<A> singleton = Collections.singleton(skipped); | ||
105 | Set<A> candidate = Sets.difference(leftSet, singleton); | ||
106 | Set<A> rightCandidate = initialDependencies.get(candidate); | ||
107 | if (rightCandidate != null) { | ||
108 | if (Sets.union(rightCandidate, singleton).containsAll(rightSet)) { | ||
109 | solid = false; | ||
110 | break; | ||
111 | } | ||
112 | } | ||
113 | } | ||
114 | if (solid) { | ||
115 | solidDependencies.put(leftSet, rightSet); | ||
116 | } | ||
117 | } | ||
118 | |||
119 | // TODO perform proper minimization, | ||
120 | // see e.g. page 45 in http://www.cs.ubc.ca/~hkhosrav/db/slides/03.design%20theory.pdf | ||
121 | |||
122 | return Collections.unmodifiableMap(solidDependencies); | ||
123 | } | ||
124 | |||
125 | /** | ||
126 | * Adds a given dependency to a mutable accumulator. | ||
127 | * @since 1.5 | ||
128 | */ | ||
129 | public static <A> void includeDependency(Map<Set<A>, Set<A>> accumulator, Set<A> left, Set<A> right) { | ||
130 | Set<A> accumulatorRights = accumulator.computeIfAbsent(left, l -> new HashSet<>()); | ||
131 | accumulatorRights.addAll(right); | ||
132 | } | ||
133 | |||
134 | /** | ||
135 | * Adds all given dependencies to a mutable accumulator. | ||
136 | * @since 1.5 | ||
137 | */ | ||
138 | public static <A> void includeDependencies(Map<Set<A>, Set<A>> accumulator, Map<Set<A>, Set<A>> additionalDependencies) { | ||
139 | for (Entry<Set<A>, Set<A>> entry : additionalDependencies.entrySet()) { | ||
140 | includeDependency(accumulator, entry.getKey(), entry.getValue()); | ||
141 | } | ||
142 | } | ||
143 | } | ||