나는 임의의 두 세트의 데카르트 곱을 효율적으로 계산하는 방법을 연구했지만 세트의 크기가 커지면 솔루션이 항상 비효율적이라는 것을 발견했습니다. 내 질문은, MySQL과 같은 데이터베이스 언어가 어떻게이 작업을 효율적으로 수행 할 수 있는가, 알고리즘이나 데이타베이스 언어의 방식으로 데카르트 제품을 에뮬레이트하는 방법이 있습니까?DBMS처럼 빠른 데카르트 계산 곱하기
PD : 자바를 사용하고 있습니다.
기본적으로, 아니요 - 두 세트의 크기의 직교 제품을 원할 경우 n,m - 직교 제품의 크기는 n*m이고 생성하려면 O(nm) 알고리즘이 필요합니다.
그러나 데이터베이스 언어의 경우 'join'과 같은 작업을 할 때 응답을 얻기 위해 전체 조인을 생성 할 필요가없는 경우가 있습니다. 나중에 수행 할 작업이 항목 수를 계산하거나 합집합. 의 COGROUP 연산자로 표시 할 수 있습니다.이 연산자는 암시 적 조인만으로 나중에 크기 나 합계를 사용하기 때문에 실제 카티 션 제품은 사용할 수 없습니다. 올바른 상황에서 적절히 사용된다면 훨씬 더 효율적 일 수 있습니다.
가능한 속담은 http://stackoverflow.com/questions/1741364/efficient-cartesian-product-algorithm?rq=1입니다. – StilesCrisis