Предположим, у вас есть таблица с 3 ключами (A, B, C) и 1 значением (D), которые вы хотели бы получить. Мы всегда будем следить за тем, чтобы не было повторяющихся строк с одинаковым набором ключей и разным значением. Что-то в этом роде
A | B | C | D
========================
a1 | b1 | c1 | d1
a1 | b1 | c2 | d1
a3 | b2 | c3 | d1
a2 | b3 | c2 | d2
a2 | b1 | c2 | d2
a2 | b2 | c3 | d3
(у нас никогда не было бы «a1, b1, c1, d1» и «a1, b1, c1, d2» одновременно в таблице, поскольку это противоречит)
В настоящее время 6 записей. Теперь предположим, что мы начинаем поддерживать использование «звездочки» (или «ВСЕ») в ключах. Когда мы пытаемся извлечь значение D для набора ключей запроса, выбирается строка максимального соответствия (максимальное соответствие в том смысле, что строка, в которой максимальное количество ключей в A, B, C точно совпадает, а остальные совпадают с "звезда")
Пример таблицы результатов (это всего лишь один вариант, также есть много других решений)
A | B | C | D
========================
* | * | * | d1
a2 | * | * | d2
a2 | b2 | c3 | d3
В нем всего 3 записи, что составляет половину начальной таблицы. Сжатие будет только увеличиваться, если мы начнем увеличивать объем данных в таблице и количество ключей и т. Д.
Есть ли какой-нибудь алгоритм, который мы можем использовать для выполнения такого рода оптимизации? Даже грубое / субоптимальное решение ценится, так как в настоящее время я не знаю, как это можно сделать.
Спасибо!