Я исследовал, как эффективно вычислить декартово произведение двух произвольных наборов, но обнаружил, что решения всегда весьма неэффективны, если размер наборов становится огромным. Мой вопрос заключается в том, как языки баз данных, такие как MySQL, эффективно справляются с этой задачей, существует ли алгоритм или способ эмулировать декартово произведение так, как это делают языки баз данных?
ПД: Я использую Java.
В принципе, нет - если вы хотите декартово произведение двух наборов размеров n,m - размер декартова произведения равен n*m - и вам нужен алгоритм O(nm) для его генерации.
Однако для языков баз данных, когда вы делаете что-то вроде 'join', вы иногда не нужно генерировать все соединение, чтобы получить ответ - если все, что вы собираетесь сделать позже, это просто подсчитать количество элементов или сумму.
Это можно показать в Pig Latin в COGROUP, который только создает неявное соединение, чтобы позже просто использовать размеры или суммы, а не настоящее декартово произведение. Это потенциально может быть намного более эффективным, если использовать его правильно в правильной ситуации.
