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