Алгоритм получения отдельных записей из декартова продукта
У меня есть две таблицы (например, A и B). Моя задача - синхронизировать B с A, т. Е. Добавлять записи в B, если они присутствуют в A, но не в B; и удалять повторные записи из B, если они присутствуют в B, но не в A.
A и B могут иметь записи дубликатов, так что если записи дублируются в A, B также должны иметь дубликаты. Пример данных в A и B
**Table A** **Table B**
id identifier id identifier
100 capital 1001 bat
201 bat 1002 bat
202 bat 1003 bat
5010 keyboard
Для этого я взял записи из A и B, используя внешнее соединение, так что мой вывод выглядит так:
A.id B.id identifier
100 null capital
201 1001 bat
201 1002 bat
201 1003 bat
202 1001 bat
202 1002 bat
202 1003 bat
null 5010 keyboard
case, 100 и 5010 соответственно добавляют и удаляют кандидатов, что легко понять.
Проблема заключается в том, что 1003 также является кандидатом на удаление. Начиная с 201 и 202 отображаются соответственно 1001 и 1002.
Я могу сделать это в базе данных путем нумерации дубликатов в базе данных, как это сделано в MYSQL: избегать декартова произведения повторяющихся записей при самоподключении. Но из-за некоторые ограничения, я могу загружать только данные в формате выше, используя внешнее соединение. Поэтому мне нужен алгоритм в JAVA, чтобы сделать это. Спасибо заранее.
1 ответ
Я пришел к этому алгоритму, который не очень чист или умен, но, похоже, выполняет эту работу:
import java.util.ArrayList;
import java.util.HashMap;
import java.util.HashSet;
import java.util.List;
import java.util.Iterator;
import java.util.Map;
import java.util.Set;
class SyncAlgorithm {
static class JoinResult {
public final Integer aId;
public final Integer bId;
public final String identifier;
public JoinResult(Integer aId, Integer bId, String identifier) {
this.aId = aId;
this.bId = bId;
this.identifier = identifier;
}
}
public static void main(String[] args) {
List<JoinResult> table = makeTestTable();
System.out.println("Initial table:");
printTable(table);
System.out.println();
Iterator<JoinResult> iter = table.iterator();
// A.id values we have seen
Map<String, Set<Integer>> aSeen = new HashMap<String, Set<Integer>>();
// B.id values we have seen
Map<String, Set<Integer>> aUsed = new HashMap<String, Set<Integer>>();
// B.id values we have seen
Map<String, Set<Integer>> bUsed = new HashMap<String, Set<Integer>>();
// Loop over table to remove unnecessary rows
while (iter.hasNext()) {
JoinResult row = iter.next();
// Make sure sets exist for current identifier
if (!aSeen.containsKey(row.identifier)) {
aSeen.put(row.identifier, new HashSet<Integer>());
}
if (!aUsed.containsKey(row.identifier)) {
aUsed.put(row.identifier, new HashSet<Integer>());
}
if (!bUsed.containsKey(row.identifier)) {
bUsed.put(row.identifier, new HashSet<Integer>());
}
// If there is no match in A remove
if (row.aId == null) {
iter.remove();
// If both A.id and B.id are note null
} else if (row.bId != null) {
// Mark A.id as seen
aSeen.get(row.identifier).add(row.aId);
// If A.id or B.id were already used discard row
if (aUsed.get(row.identifier).contains(row.aId) || bUsed.get(row.identifier).contains(row.bId)) {
iter.remove();
// If both ids are new mark them as used and keep the row
} else {
aUsed.get(row.identifier).add(row.aId);
bUsed.get(row.identifier).add(row.bId);
}
// If A.id is not null but B.id is null save A.id and keep the row
} else {
aSeen.get(row.identifier).add(row.aId);
aUsed.get(row.identifier).add(row.aId);
}
}
// Add A.id values without that have been seen but not used
for (Map.Entry<String, Set<Integer>> aSeenEntry : aSeen.entrySet())
{
Set<Integer> aSeenId = aSeenEntry.getValue();
aSeenId.removeAll(aUsed.get(aSeenEntry.getKey()));
for (Integer aId : aSeenId) {
table.add(new JoinResult(aId, null, aSeenEntry.getKey()));
}
}
System.out.println("Result table:");
printTable(table);
}
static List<JoinResult> makeTestTable() {
List<JoinResult> table = new ArrayList<JoinResult>();
table.add(new JoinResult(100, null, "capital"));
table.add(new JoinResult(201, 1001, "bat"));
table.add(new JoinResult(201, 1002, "bat"));
table.add(new JoinResult(201, 1003, "bat"));
table.add(new JoinResult(202, 1001, "bat"));
table.add(new JoinResult(202, 1002, "bat"));
table.add(new JoinResult(202, 1003, "bat"));
table.add(new JoinResult(null, 5010, "keyboard"));
table.add(new JoinResult(501, 3001, "foo"));
table.add(new JoinResult(502, 3001, "foo"));
return table;
}
static void printTable(List<JoinResult> table) {
System.out.println("A.id B.id identifier");
for (JoinResult row : table) {
System.out.printf("%-8d%-8d%s\n", row.aId, row.bId, row.identifier);
}
}
}
Выход:
Initial table:
A.id B.id identifier
100 null capital
201 1001 bat
201 1002 bat
201 1003 bat
202 1001 bat
202 1002 bat
202 1003 bat
null 5010 keyboard
501 3001 foo
502 3001 foo
Result table:
A.id B.id identifier
100 null capital
201 1001 bat
202 1002 bat
501 3001 foo
502 null foo