計算笛卡兒積像DBMS一樣快

Question

我已經研究過如何有效計算兩個任意集合的笛卡爾乘積，但是我發現如果集合的大小變得非常大，那麼解決方案總是非常低效。我的問題是，像MySQL這樣的數據庫語言如何有效地完成這項任務，有沒有一種算法或一種方法來模擬數據庫語言所做的笛卡爾產品？

PD：我正在使用java。

Answer 1

基本上沒有 - 如果你想要兩套尺寸的笛卡爾積n,m - 笛卡爾積的尺寸是n*m - 你需要O(nm)算法來生成它。

但是，對於數據庫語言，當您執行諸如'join'之類的操作時，您有時不需要生成整個聯接來獲取答案 - 如果稍後您要做的只是計數項數，或者和。
這可以顯示在Pig Latin的COGROUP運營商，它只創建一個隱式聯接，以便稍後使用大小或總和 - 而不是真正的笛卡兒積。如果在正確的情況下正確使用，這可能會更有效率。