조인 질의를 위한 효율적인 무작위 순서 열거 알고리즘을 제안하고, 이론적 보장과 실험적 성능 향상을 위한 최적화 기법을 제시한다.
pchen.research@gmail.com Harbin Institute of Technology Harbin, China
zguo.research@gmail.com Harbin Institute of Technology Zhengzhou Advanced Research Institute Zhengzhou, China
yangjianwei006@cnpc.com.cn Harbin Institute of Technology Harbin, China
miaodongjing@hit.edu.cn Harbin Institute of Technology Harbin, China
많은 데이터 분석 파이프라인에서 기본적이면서도 시간이 많이 드는 과정은 조인 결과를 생성하여 이를 다운스트림 작업에 전달하는 것이다. 이를 위해 수많은 열거 알고리즘이 개발되어 왔다. 전체 조인 결과를 통계적으로 의미 있게 대표하려면, 결과 튜플은 균등한 무작위 순서로 열거되어야 한다. 그러나 기존 연구에는 (순환) 조인 질의에 대해 최악의 경우 실행 시간 보장을 갖는 효율적인 무작위 순서 열거 알고리즘이 부족하다. 본 논문에서는 복잡도에 큰 숨은 상수가 없는 효율적인 조인 질의용 무작위 순서 열거 알고리즘을 개발하여, $$ 𝑂 ( AGM (𝑄 )|𝑅𝑒𝑠 (𝑄 ) | log 2 |𝑄 |)
기댓값 지연과, $$ 𝑂 (AGM (𝑄 ) log |𝑄 |)총 실행 시간, 그리고 $$ 𝑂 (| 𝑄 | log |𝑄 |)
시간의 인덱스 구축 후 성능을 달성한다. 여기서 |𝑄 |는 입력 크기, AGM (𝑄 )는 AGM 경계, |𝑅𝑒𝑠 (𝑄 )|는 조인 결과의 크기이다. 또한 조합적 𝑘 -clique 가설 하에서, 우리의 알고리즘이 최악의 경우 거의 최적임을 증명한다. 우리의 알고리즘은 질의별 전처리를 필요로 하지 않으며, 작은 수정만으로 많은 일반적인 데이터베이스 인덱스에 유연하게 적용될 수 있다. 또한 열거를 가속하고 메모리 사용량을 줄이기 위한 비자명한 기법도 고안하고, 이들이 알고리즘에 미치는 영향을 실험적으로 연구한다. 실험 결과, 제안한 기법으로 강화된 우리의 알고리즘은 기존 최신 기법들을 크게 능가함을 보인다. PVLDB 참고 형식: Pengyu Chen, Zizheng Guo, Jianwei Yang, and Dongjing Miao. Towards Efficient Random-Order Enumeration for Join Queries. PVLDB, 19(5): 889 -901, 2026. doi:10.14778/3796195.3796203 PVLDB 아티팩트 가용성: 소스 코드, 데이터 및/또는 기타 아티팩트는 https://github.com/Chen-Py/JoinREnum 에서 제공된다. > 이 저작물은 Creative Commons BY-NC-ND 4.0 International License에 따라 사용이 허가된다. 이 라이선스 사본은 https://creativecommons.org/licenses/by-nc-nd/4.0/ 에서 확인할 수 있다. 이 라이선스가 허용하는 범위를 넘어서는 사용을 위해서는 info@vldb.org 로 이메일을 보내 허가를 받아야 한다. 저작권은 소유자/저자에게 있다. 출판 권리는 VLDB Endowment에 허락되었다. Proceedings of the VLDB Endowment, Vol. 19, No. 5 ISSN 2150-8097. doi:10.14778/3796195.3796203 ## 1 서론 데이터베이스 시스템에서 가장 기초적인 질의 유형 중 하나로서, 조인 질의 1 는 동등성 조건에 기반하여 하나 이상의 테이블의 열을 새로운 테이블로 결합한다. 조인 질의의 효율적인 평가 알고리즘은 데이터베이스 커뮤니티에서 이론적으로도 실무적으로도 광범위하게 연구되어 왔다. 이러한 알고리즘들 [ 1, 15 , 18 – 22 , 25 ] 가운데 다수는 최악의 경우 조건에서 점근적으로 최적의 성능을 달성할 수 있다. 그러나 최악의 경우 최적 알고리즘을 구현하더라도 조인은 여전히 계산 비용이 높다. 그 주된 이유는 조인 결과의 크기 때문이다. 조인 질의 𝑄 는 AGM 경계 [ 2]만큼 많은 튜플을 생성할 수 있는데, 이는 보통 𝑄 의 관계 테이블 크기보다 훨씬 크다. 따라서 조인 결과의 모든 튜플을 나열하는 것만으로도 최악의 경우 많은 시간이 필요하다. 이는 데이터베이스 시스템과 데이터 분석 파이프라인 [13]에서 중요한 도전 과제를 제기한다. 앞서 언급한 문제를 해결하기 위해, 모든 조인 결과가 미리 생성되기를 기다리지 않고 결과 튜플을 연속적으로 생성하여 다운스트림 작업에 출력하는 수많은 알고리즘이 제안되었다 [ 3–5 , 7, 8]. 이러한 알고리즘, 즉 열거 알고리즘은 중간 결과의 수가 처리 시간에 비례한다는 장점을 제공한다. 이는 질의가 더 큰 데이터 분석 파이프라인의 일부이고, 질의 결과가 다운스트림 처리로 전달되는 경우 [ 9 ]에 유용하다. 예를 들어, 머신러닝 파이프라인에서는 질의 결과를 모델 학습 작업의 훈련 데이터나 특징으로 사용할 수 있다 [ 14 , 17 , 24 ]. 이러한 파이프라인에서는 전체 결과 구체화가 끝날 때까지 기다리지 않고 중간 결과를 다음 단계 프로세스에 전달할 수 있다. 이는 스트리밍 학습 알고리즘 [ 24 ]에서 볼 수 있다. 또한 사용자는 학습 과정이 안정 상태에 도달하면 학습을 중단할 수 있다. 더 나아가 무작위 순서 열거가 요구되는데, 즉 각 질의 결과 튜플은 아직 열거되지 않은 결과 튜플 집합에서 균등 무작위로 열거되어야 한다 [ 9]. 이런 방식으로 알고리즘은 언제든지 모든 조인 결과에 대한 통계적으로 의미 있는 표현을 출력한다. 완전한 질의 결과가 반드시 필요하지 않은 많은 다운스트림 작업은 무작위 표본으로부터 큰 이점을 얻을 수 있으며, 표본의 크기가 클수록 그 이점은 증가한다. 이를 위해 Carmeli 등 [ 9 ]은 자유-연결 비순환 conjunctive query에 대해 선형 시간 전처리 후 다항로그 지연을 갖는 무작위 순서 열거 알고리즘을 도입했다. > 1이 논문에서 다루는 조인 질의는 보다 정확히는 equi-join으로 알려져 있다. 889 또한 그들은 (복잡도 가정 하에서) 비자유-연결 conjunctive query, 즉 순환 조인 질의와 같은 경우에 대해 선형 전처리와 다항로그 지연을 갖는 무작위 순서 열거 알고리즘이 존재하지 않음을 증명하고, 비자유-연결 질의의 결과를 무작위 순서로 열거하는 데 필요한 시간(열거 지연과 전처리 시간 모두)의 정확한 이해가 흥미로운 문제라고 주장한다. 일반적인 조인 질의에 대해, 직관적인 방법 [ 6, 13 ]은 균등 표본추출(복원 추출) 알고리즘 [ 12 , 13 , 23 , 27 ]을 복원 없는 표본추출 과정으로 변환하는 단순한 방식을 개발하는 것이다. 이는 보통 표본추출 알고리즘을 균등하게 후보 결과를 생성하는 블랙박스로 취급하고, 이미 본 중복 결과를 버리는 방식으로 이루어진다. (순환) 조인 결과를 표본추출하기 위해 초기 연구 [ 23 , 27 ]는 원래의 순환 질의를 비순환 조인 질의(소위 골격 질의)와 잔여 구성요소로 분해했다. 그런 다음 골격 질의에 비순환 조인 표본추출 알고리즘을 적용하고, 골격 질의의 표본과 잔여 구성요소 사이의 조인 결과를 표본추출하기 위해 단순한 절차를 사용했다. 이러한 방법들은 실용적 동기를 갖지만, 거의 최적의 실행 시간을 달성하지 못하며, 표본추출 전에 각 질의마다 최소 선형 시간 전처리를 요구한다. 보다 최근의 연구 [ 13 , 16 , 26 ]는 분해를 피하고 순환 조인에서 직접 표본추출을 수행한다. 이러한 알고리즘은 질의별 전처리 없이 복잡도 가정 하에서 거의 최적의 기댓값 표본추출 시간을 달성한다. 그러나 그 실행 시간의 상수 및 다항로그 인자는 일반적으로 크며, 질의 크기에 대해 지수적으로 증가한다(예를 들어 [ 13 ]의 기댓값 실행 시간은 실제로 $$ 𝑂 ( AGM (𝑄 ) max {1,|𝑅𝑒𝑠 (𝑄 ) | } log 𝑑 +1 |𝑄 |)이며, 여기서
𝑅𝑒𝑠 (𝑄 )는 조인 결과 집합이고 𝑑는 관계의 최대 차수이다). 또한 우리가 아는 한, 이러한 알고리즘들은 아직 구현되어 실험적으로 평가되지 않았다. 그러나 표본추출 기반 열거 방식은 실제로 많은 생성된 결과 튜플이 버려지기 때문에 시간을 크게 낭비한다. 또한 총 실행 시간에 대한 최악의 경우 보장이 없고, 알고리즘이 종료될 때 모든 결과 튜플을 출력할 수 있다는 엄밀한 보장도 없다. 엄밀히 말하면, 질의 결과 수에 대해 부분선형 지연을 갖는 열거 알고리즘으로조차 간주되지 않을 수 있다 [ 9]. 더 나쁘게도, 표본추출 기반 무작위 순서 열거는 기존 조인 표본추출 알고리즘의 앞서 언급한 약점을 그대로 물려받는다. 본 논문에서는 총 실행 시간에 대한 최악의 경우 보장을 제공하는 효율적인 조인 질의용 무작위 순서 열거 알고리즘을 제시한다. 이론적으로 우리의 알고리즘은 조인 결과 튜플을 기댓값 $$ 𝑂 ( AGM (𝑄 )|𝑅𝑒𝑠 (𝑄 ) |+ 1 log 2 |𝑄 |)
𝑂 (AGM (𝑄 ) log |𝑄 |)
총 실행 시간으로 열거하며, 그 전에 $$ 𝑂 (| 𝑄 | log |𝑄 |)시간의 인덱스 구축 단계를 수행한다. 또한 이 알고리즘은 거의 최악의 경우 최적임이 증명되며, Generic Join [ 22 ]과 같은 몇몇 최악의 경우 최적 조인 알고리즘과 동일한 총 실행 시간 복잡도를 달성한다. 실용적으로는 열거를 가속하고 메모리 사용을 줄이기 위한 기법들을 개발했으며, 특히 AGM (𝑄 ) ≫ | 𝑅𝑒𝑠 (𝑄 )| 인 경우 실험에서 성능 향상을 크게 이끌어냈다. 우리의 알고리즘은 열거 지연과 총 실행 시간에 큰 상수나 다항로그 인자가 없는 거의 최적의 무작위 순서 열거 알고리즘일 뿐 아니라, 전처리 없는 효율적인 조인 표본추출 알고리즘으로도 사용될 수 있다. 즉, 관계 테이블 위에 구축한 인덱스는 서로 다른 조인 질의에서 재사용할 수 있으며, 각 질의마다 선형 시간 전처리를 다시 할 필요가 없다. 더욱이 우리의 알고리즘은 관계 테이블에 대해 복잡한 인덱스 구조를 요구하지 않는다. 균형 트리, B-tree, skip list, trie와 같이 데이터베이스 시스템에서 널리 사용되는 다양한 계층적 인덱싱 구조를 지원한다. 갱신이 필요하지 않은 경우에는 튜플을 사전식 순서로 정렬하는 것만으로도 가벼운 인덱싱 메커니즘으로 충분하다. 이러한 유연성 덕분에 우리의 알고리즘은 최소한의 개발 오버헤드로 다양한 데이터베이스 시스템에 통합될 수 있다. 구체적으로, 우리의 기여는 다음과 같다. 첫째, 새로운 개념인 RRAccess (Relaxed Random-Access 알고리즘)와 잘 조직된 자료구조인 Ban-Pick tree를 기반으로 조인 질의를 위한 효율적인 무작위 순서 열거 알고리즘 프레임워크를 개발한다. 이 두 개념은 본 논문에서 처음 제안된다. 구체적으로 RRAccess는 정수 집합 𝑆 (반드시 연속일 필요는 없음)에서 조인 결과 튜플 집합 𝑅𝑒𝑠 (𝑄 )로의 전단사 𝛼를 계산하도록 정의되며,
𝐼 ∩ 𝑆 = ∅ 를 만족하는 자명한 구간 𝐼 를 𝑆 에 속하지 않는 정수를 입력했을 때 반환한다. Ban-Pick tree는 금지 구간이라 불리는 서로소 구간들의 모음을 유지하며, 남아 있는(금지되지 않은) 구간들에서 균등 무작위로 정수를 뽑는 연산을 지원한다. Ban-Pick tree를 기반으로, 만약 $$ 𝑂 (log 2 |𝑄 |)
최악 시간과 $$ 𝑂 (log |𝑄 |)상각 시간에 동작하고 ∀𝑠 ∈ 𝑆, 𝑠 ≤ AGM (𝑄 )를 만족하는 RRAccess 알고리즘이 있다면, 우리의 알고리즘은 𝑅𝑒𝑠 (𝑄 )의 결과 튜플을 기댓값 $$ 𝑂 ( AGM (𝑄 )|𝑅𝑒𝑠 (𝑄 ) |+ 1 log 2 |𝑄 |)
𝑂 (AGM (𝑄 ) log |𝑄 |)
총 실행 시간으로 열거함을 보인다. 그리고 그 기댓값 열거 지연과 총 실행 시간이 이론적 하한보다 다항로그 인자만큼만 크므로 거의 최악의 경우 최적 알고리즘임이 증명된다. 또한 우리의 프레임워크는 실제 환경에서 열거 효율을 크게 향상시키는 실용적인 가속 기법도 가능하게 한다. 둘째, relaxed random-access tree (RRATree)라 부르는 논리적 트리 구조에 기반한 RRAccess 알고리즘을 설계한다. RRATree의 각 노드는 하나의 필터에 대응하고, 부모 노드의 필터를 만족하는 결과 튜플 집합은 그 자식들의 필터에 대응하는 부분집합으로 재귀적으로 분할된다. RRATree의 필터 성질을 최대한 활용하여 효율적인 자료구조를 구축하고, 상한 추정 알고리즘과 자식 탐색 알고리즘을 개발하는데, 이 둘은 모두 $$ 𝑂 (log |𝑄 |)시간에 동작한다. 이러한 구성 요소 덕분에 RRAccess는 $$ 𝑂 (log 2 |𝑄 |)
최악 시간과 $$ 𝑂 (log |𝑄 |)상각 시간을 달성하고, 그 결과 거의 최악의 경우 최적 REnum을 얻는다. 또한 REnum의 메모리 사용을 분석하고, 실제 메모리 오버헤드를 줄이기 위한 세 가지 기법을 도입한다. 셋째, 우리의 알고리즘 프레임워크를 바탕으로 열거를 가속하기 위한 두 가지 비자명한 기법을 개발한다. 첫 번째는
larger trivial interval discovery (LTI)이다. N[1, AGM (𝑄 )] \ 𝛼 −1 (𝑅𝑒𝑠 (𝑄 )) 안의 자명 정수들은 종종 연속적이며 구간(자명 구간)으로 묶일 수 있다. LTI는 RRAccess 실행 중에 큰 자명 구간을 발견하여 후속 단계에서 더 많은 자명 정수를 뽑지 않도록 한다. 그 결과 RRAccess가 ⊥를 반환할 확률이 줄어들어 총 실행 시간과 열거 지연이 감소한다. RRAccess가 𝑝𝑒𝑟𝑝 를 반환할 확률을 더 줄이기 위해, tighter upper-bound estimation (TU)이라 부르는 두 번째 기법을 개발한다. TU는
890 RRATree의 각 필터에 대해 필터링된 조인 결과 수의 더 타이트한 상한 추정을 제공하므로, 더 많고 더 큰 자명 구간이 더 이른 시점에 발견되고 금지된다. 결과적으로 LTI의 효과가 향상된다. 마지막으로, 우리는 최적화 기법과 함께 우리 알고리즘의 효율성, 메모리 사용량, 확장성을 실험적으로 평가한다. 결과는 이러한 기법을 적용한 우리의 알고리즘이 표본추출 기반 방법 [13, 23]보다 현저히 우수함을 보여준다. 논문의 나머지 구성은 다음과 같다. 기본 표기와 필요한 몇 가지 기법은 Section 2에서 소개한다. Section 3에서는 우리의 핵심 무작위 순서 열거 알고리즘 프레임워크를 소개한다. Section 4에서는 RRATree와 RRAccess 알고리즘을 자세히 설명하고, 열거 지연과 총 실행 시간의 경계를 수립하며, 메모리 절감 기법을 제시한다. Section 5에서는 실제로 열거를 크게 가속하는 비자명한 기법들을 논의한다. Section 6에서는 실험 연구를 제시한다. 지면 제약으로 인해 일부 증명과 세부 사항은 생략하며 기술 보고서 [11]에 제공한다.
본 논문에서 모든 정수의 집합은 Z로, 모든 자연수의 집합은 N으로 표기한다. 임의의 자연수 𝑖 와 𝑗 에 대하여
𝑖 ≤ 𝑗 이면, N[𝑖, 𝑗 ] = [𝑖, 𝑗 ] ∩ N으로 정의한다.
유한한 속성 집합 Att와 𝑈 ⊆ Att가 주어졌을 때, 𝑈 위의 튜플은 함수 𝑡 : 𝑈 → Z이고, 튜플 𝑡 의 𝑉 ⊆
𝑈 에 대한 사영, 즉 𝑡 [𝑉 ]는 각 𝑣 ∈
𝑉 에 대해 𝑡 [𝑉 ] ( 𝑣 ) = 𝑡 (𝑣 )를 만족하는 튜플이다. 관계 𝑅 은 동일한 속성 집합
𝑈 위의 튜플들의 집합이며, att (𝑅 ) = 𝑈 라고 하자. 그러면 조인 질의 𝑄 는 관계들의 집합 {𝑅 1, . . . , 𝑅 𝑚 }로 정의되며, 𝑄 = 𝑅 1⋈︁ · · · ⋈︁ 𝑅 𝑚 로 표현할 수 있다. 그리고 |𝑄 | =∑︁ 𝑚 𝑖 =1 |𝑅 𝑖 |를 𝑄 안 관계들의 크기 합으로 둔다
(즉 입력의 크기). 질의 𝑄 의 결과는
Res (𝑄 ) := {𝑡 over att (𝑄 )|∀ 𝑅 ∈ 𝑄 : 𝑡 [att (𝑅 )] ∈ 𝑅 }, where att (𝑄 ) =⋃︁
𝑅 ∈𝑄
att (𝑅 ) 로 정의된다. 속성
𝑣 의 활성 도메인을 dom 𝑄 (𝑣 )로 두면,
즉, dom 𝑄 (𝑣 ) =⋃︁ 𝑅 ∈𝑄 ⋃︁ 𝑣 ∈att (𝑅 ) {𝑡 (𝑣 )| 𝑡 ∈ 𝑅 } 이고, 따라서
Res (𝑄 ) ⊆ ∏︁ 𝑣 ∈att (𝑄 ) dom 𝑄 (𝑣 ) 이다.
직관적으로 AGM 경계는 실제 데이터 값을 알 필요 없이 입력 관계들의 기수만으로 조인 결과가 얼마나 커질 수 있는지에 대한 상한을 제공한다. 이는 조인 결과의 “최악의 경우” 크기를 특징짓고, 질의 평가의 잠재적 비용을 추정하고 효율적인 조인 알고리즘을 설계하는 데 널리 사용된다. 형식적으로, 조인 질의 𝑄 가 주어졌을 때, 𝑄 의 스키마 그래프는 hypergraph 𝐺 𝑄 =
(𝑉 , 𝐸 )로 정의되며, 여기서 𝑉 = att (𝑄 )이고 𝐸 = {att (𝑅 )| 𝑅 ∈ 𝑄 }이다. 𝑐 : 𝐸 → ( 0, 1)
를 𝐺 𝑄 의 분수 간선 덮개라고 하자. 즉, ∀𝑣 ∈ 𝑉 ,∑︁ 𝑣 ∈𝑒 𝑐 (𝑒 ) ≥ 1. 그러면
|Res (𝑄 )| ≤ AGM 𝑐 (𝑄 ) [2], where AGM 𝑐 (𝑄 ) :=∏︁ 𝑅 ∈𝑄 |𝑅 |𝑐 (att (𝑅 ) ) .또한 𝐸𝐶 (𝐺 𝑄 )를 𝐺 𝑄 의 모든 분수 간선 덮개의 집합이라 하면, 𝑄 의 최소화된 AGM 경계, 즉 AGM (𝑄 ) =
min 𝑐 ∈𝐸𝐶 (𝐺 𝑄 ) AGM 𝑐 (𝑄 ), 는 타이트하다. 즉 |Res (𝑄 ∗)| = Ω(AGM (𝑄 ∗))를 만족하는 조인 질의 𝑄 ∗가 존재한다 [ 2]. AGM 경계는 관계 테이블의 크기만으로도 효율적으로 계산할 수 있으며, 최소화된 AGM 경계는 데이터 복잡도 하에서 선형계획법을 풀어 $$ 𝑂 (1)
시간에 계산할 수 있다는 점에 유의하라. 𝑥 𝑦 𝑧 𝑆 𝑅 𝑇 > (a) 𝐺 𝑄 Δ 𝑥 𝑦 1 22 33 44 1 > (b) 𝑅 𝑦 𝑧 1 33 44 44 1 > (c) 𝑆 𝑥 𝑧 2 43 13 44 2 > (d) 𝑇 𝑥 𝑦 𝑧 2 3 43 4 13 4 4 > (e) 𝑅𝑒𝑠 (𝑄 Δ) Table 1: 𝑄 Δ := 𝑅 ⋈︁ 𝑆 ⋈︁ 𝑇 ## 2.3 균등 표본추출 조인 표본추출 알고리즘은 각 조인 결과 튜플을 동일한 확률로 출력한다. 형식적으로, 조인 표본추출 알고리즘은 입력으로 조인 질의 𝑄 를 받고 𝑅𝑒𝑠 (𝑄 ) 안의 튜플을 출력하는 무작위화 알고리즘 G이며, ∀𝑡 ∈ Res (𝑄 )에 대해 Pr (G( 𝑄 ) outputs 𝑡 ) = 1 > |Res (𝑄 ) | 를 만족한다. Deng 등 [ 13 ]에 따르면, (복잡도 가설 하에서) 거의 최악의 경우 최적인 조인 표본추출 알고리즘이 존재한다. Theorem 1 ([ 13 ]). There is a uniform join sampling algorithm running in expected $$ 𝑂 ˜ ( AGM (𝑄 ) > max {1,|𝑅𝑒𝑠 (𝑄 ) | } )time after a $$ 𝑂 ˜ (| 𝑄 |)
-time index construction phase. Moreover, under the combinatorial 𝑘 -clique hypothesis, for any 𝜀 > 0, there is no uniform sampling algorithm for join queries that runs in $$ 𝑂 ˜ (| 𝑄 | + |𝑄 |𝜌 ∗ −𝜀 > |Res (𝑄 ) | )time with high probability, where 𝜌 ∗ is the fractional edge cover number of 𝐺 𝑄 .
조인 질의를 위한 무작위 순서 열거 알고리즘은 조인 질의 𝑄 를 입력으로 받아 Res (𝑄 )의 모든 튜플을 무작위 순서로 출력하는 무작위 알고리즘이다. 다시 말해, 각 1 ≤ 𝑖 <
|Res (𝑄 )| 에 대해, 처음 𝑖 개의 결과 튜플 𝑡 1, . . . , 𝑡 𝑖 가 출력된 후, (𝑖 + 1)번째 출력 결과 튜플은 Res (𝑄 ) \ {𝑡 1, . . . , 𝑡 𝑖 }의 균등 표본이다. 모든 결과 튜플이 출력된 뒤에도 알고리즘은 더 이상의 튜플이 남아 있지 않음을 확인하기 위해 추가 계산이 필요할 수 있다는 점에 유의하라. 무작위 순서 열거 알고리즘의 (기댓값) 열거 지연은 다음 시간 구간들의 최대 (기댓값) 길이로 정의된다: (1) 알고리즘 시작부터 첫 번째 결과 튜플이 출력될 때까지의 시간, (2) 임의의 결과 튜플 출력부터 다음 결과 튜플 출력까지의 시간, (3) 마지막 결과 튜플 출력부터 알고리즘 종료까지의 시간.
이 절에서는 효율적인 무작위 순서 열거 알고리즘 프레임워크를 개발한다. 알고리즘을 직관적으로 설명하기 위해, 먼저 대표적인 순환 조인 질의 𝑄 Δ를 정의하고, 이를 이후 논의 전반에서 예시로 사용할 것이다.
Example 1 ( 𝑄 Δ). Let 𝑄 △ := 𝑅 ⋈︁ 𝑆 ⋈︁ 𝑇 , in which att (𝑅 ) =
{𝑥, 𝑦 }, att (𝑆 ) = {𝑦, 𝑧 } and att (𝑇 ) = {𝑥, 𝑧 }. The schema graph, rela-tion tables, and join results of 𝑄 Δ are shown in Table 1.
무작위 순서 열거를 위한 자연스러운 아이디어는 연속된 자연수 집합 N[1, |Res (𝑄 Δ)|]
과 결과 튜플 집합 Res (𝑄 Δ) 사이의 전단사를 구축하는 것이다. 예를 들어, Res (𝑄 Δ)𝜋 (𝑖 )를 사전식 순서 𝜋 에서 Res (𝑄 Δ) 의 𝑖 번째 튜플이라 하자. 그러면 𝑅𝑒𝑠 (𝑄 Δ)의 무작위 순서 열거는
891 𝑖 = 1, . . . , |Res (𝑄 Δ)| 에 대해 Res (𝑄 Δ)𝜋 (𝜎 (𝑖 ))를 나열함으로써 얻을 수 있으며, 여기서 𝜎는 1부터 |Res (𝑄 Δ)| 까지의 정수에 대한 무작위 순열이다. 예를 들어 Example 1에서 정수의 무작위 순열이 2, 3, 1이면, 열거되는 튜플은 (3, 4, 1), (3, 4, 4), (2, 3, 4)가 된다. 이 접근은 [ 9]에서 보이듯 비순환 조인 질의에는 작동하며, 거기서는 선형 시간 전처리 후 다항로그 시간에 계산 가능한 그러한 전단사를 제시한다. 그러나 일반적인 조인 질의, 특히 순환 조인 질의의 경우, 특정 복잡도 가설 하에서는 이렇게 효율적으로 계산 가능한 전단사가 존재하지 않는다 [9]. 우리의 접근에서는 전단사 구성 요구를 완화한다. 대신 정의역의 일부 정수는 어떤 결과 튜플에도 대응하지 않도록 허용하고, 이를 “ ⊥”에 매핑한다. 우리는 이러한 정수를 “자명 정수”라 하고, 나머지를 “비자명 정수”라 부른다. 주어진 정수가 자명한지 여부는 효율적으로 검사할 수 있다. 주목할 점은 모든 비자명 정수와 결과 튜플 사이의 대응은 전단사라는 것이다. 따라서 복원 없이 정수를 균등 무작위로 표본추출하고, 표본추출된 순서대로 비자명 정수에 대응하는 튜플을 출력하면, 조인 결과의 올바른 무작위 순서 열거를 얻는다. 효율을 더 높이기 위해, 자명 정수를 만나면 그 정수가 속한 자명 구간을 식별하고 기록한다. 자명 구간이 발견되어 기록되면, 그 안의 정수들은 후속 단계에서 더 이상 표본추출되지 않는다. 이 절의 나머지 부분에서는 (1) 정수와 조인 결과 사이의 매핑에 대한 형식적 정의와 이를 계산하는 알고리즘(즉 relaxed random-access 알고리즘), (2) 온라인 구간 금지와 금지되지 않은 정수의 균등 표본추출을 지원하는 새로운 자료구조(즉 Ban-Pick tree), (3) (1)과 (2)에 기반한 효율적인 무작위 순서 열거 알고리즘 프레임워크를 소개한다.
함수족 𝜑 ={︁ 𝜑 𝑄 |𝑄 ∈ Q }︁ 와 조인 질의 𝑄 가 주어졌다고 하자.
𝜑 𝑄 : N+ → Res (𝑄 ) ∪ {⊥} 는 각 튜플 𝑡 ∈ Res (𝑄 )
에 대해 오직 하나의 𝑖 ∈ N+, 𝜑 𝑄 (𝑖 ) = 𝑡 가 존재하는 성질을 만족한다. 또한 𝑁 을
|Res (𝑄 )| 의 상한으로 두고, ∀𝑖 > 𝑁 , 𝜑 𝑄 (𝑖 ) =⊥를 만족한다고 하자. 우리는 {𝑖 |𝜑 ∗ (𝑖 ) =⊥} 안의 정수들, 즉 자명 정수들이 종종 연속적이며 구간(자명 구간)으로 묶일 수 있음을 관찰했다. 특히 AGM (𝑄 ) ≫ | 𝑅𝑒𝑠 (𝑄 )| 인 경우 그러하다. 가능한 한 많은 자명 정수가 선택되는 것을 방지하기 위해, relaxed random-access 알고리즘은 자명 구간을 보고한다. 형식적으로 RRAccess 𝑄,𝜑 를 정수 𝑖 를 입력받아 다음과 같이 동작하는 알고리즘으로 정의한다: (1) 𝜑 𝑄 (𝑖 ) ≠⊥이면 𝜑 𝑄 (𝑖 )를 반환하고, (2) 그렇지 않으면 𝑎 ≤
𝑖 ≤ 𝑏 를 만족하는, 자명 정수만 포함하는 자명 구간 [𝑎, 𝑏 ] ⊆ N+ 를 반환한다. Section 4에서 우리는 $$ 𝑂 (log 2 |𝑄 |)
𝑂 (log |𝑄 |)
상각 시간에 동작하는 relaxed random-access 알고리즘의 구현을 소개할 것이다. ## 3.2 Ban-Pick Tree 이미 선택되었거나 어떤 조인 결과에도 대응하지 않는 정수를 반복해서 선택하지 않기 위해, 그러한 정수를 나타내는 구간들의 모음을 동적으로 유지하고, 이를 이후 선택에서 제외한다. 구체적으로 우리는 두 종류의 정수를 정의한다: (1) 어떤 조인 결과에도 대응하지 않는 자명 정수, (2) 이전 단계에서 이미 선택된 선택 정수. 우리는 이러한 구간들이 서로소인 집합 𝐵 를 Ban-Pick tree라 부르는 자료구조를 사용해 유지한다. 이 구조와 두 연산은 새로 선택된 정수가 𝐵 의 어떤 구간에도 속하지 않음을 보장한다. 형식적으로 Ban-Pick tree는 다음 두 연산을 가능하게 한다: (1) 금지 연산 𝑩.𝒃𝒂𝒏 은 𝐵 의 모든 구간과 서로소인 구간을 입력받아 이를 𝐵 에 삽입한다. (2) 선택 연산 𝑩.𝒑𝒊𝒄𝒌 은 ∀𝐼 ∈ 𝐵, 𝐼 ⊆ [ 1, 𝐻 ]를 만족하는 정수 𝐻 를 입력받아 𝑖 ∈ [ 1, 𝐻 ] \ ∪ 𝐼 ∈𝐵 𝐼 를 균등 무작위로 반환한다. Ban-Pick tree를 기반으로 하면 𝐵 의 금지 구간 안에 있는 자명 정수와 선택 정수는 다시 선택되지 않게 된다. 일반적으로 N[1, 𝑁 ] \ ⋃︁ 𝐼 ∈𝐵 𝐼 는 연속 구간이 아니다. 이 때문에 하나의 구간에서 동작하는 단순 생성기는 실패한다. 따라서 우리는 서로소 구간들의 합집합 위에서 동작하는 pick 연산을 제공해야 한다. 𝐵 = {𝐼 𝑖 = [𝑙 𝑖 , ℎ 𝑖 ]| 𝑖 ∈ N[1, |𝐵 |]} 를 이미 금지된 서로소 구간들의 집합이라 하자. 일반성을 잃지 않고 ℎ𝑖 < 𝑙 𝑖 +1 가 모든 𝑖 ∈ N[1, |𝐵 | − 1]에 대해 성립한다고 하자. 𝐿 = |N[1, 𝑁 ] \ ∪ |𝐵 | > 𝑖 =1 𝐼 𝑖 |, 즉 𝐿 = 𝑁 −∑︁ |𝐵 | > 𝑖 =1 |𝐼 𝑖 | 라 하자. 우리의 pick 연산은 다음과 같이 동작한다: (1) 정수 𝑦 ∈ N[1, 𝐿 ]를 균등 무작위로 표본추출하고, (2) 오프셋 𝑏 =∑︁ 𝑘 ∗ > 𝑖 =1 |𝐼 𝑖 | 를 계산하되, ℎ𝑘 ∗ < 𝑦 + 𝑏 이고 𝑦 + 𝑏 < 𝑙 𝑘 ∗+1 (if 𝑘 ∗ < |𝐵 |)를 만족하게 하며, (3) 𝑦 + 𝑏 를 반환한다. Step (2)에서 오프셋을 효율적으로 계산하기 위해, Ban-Pick tree를 균형 트리 𝑇 𝐵 로 정의한다. 이 트리는 (1) 각 노드 𝑢 ∈ 𝑇 𝐵 가 하나의 구간 𝐼 𝑢 = [𝑢.𝑙, 𝑢.ℎ ] ∈ 𝐵 와 전단사로 대응하고, 𝑢.𝑙 과 𝑢.ℎ 를 통해 이를 저장한다. (2) 각 노드 𝑢 ∈ 𝑇 𝐵 는 왼쪽 자식과 오른쪽 자식을 가리키는 𝑢. left 와 𝑢. right 를 유지하며, 𝑣 가 𝑢 의 왼쪽(오른쪽) 자식이면 𝑣.ℎ < 𝑢.𝑙 (𝑣.𝑙 > 𝑢.ℎ ) 이다. (3) 각 노드 𝑢 ∈ 𝑇 𝐵 는 𝑢. take 를 유지하는데, 이는 𝑢 를 루트로 하는 부분트리에 있는 구간 길이들의 합을 나타낸다. (4) 𝑇 𝐵 의 높이는 $$ 𝑂 (log |𝐵 |)이다.
Algorithm 1: 𝐵.𝑝𝑖𝑐𝑘
Input: 𝐻
Output: a uniform sample from N[1, 𝐻 ] \ ∪ 𝐼 ∈𝐵 𝐼
1
𝑢 ← the root of 𝑇 𝐵 ;
2
sample an integer 𝑦 ∈ N[1, 𝐻 − 𝑢.𝑡𝑎𝑘𝑒 ] uniformly;
3
𝑏 ← 0, temp ← 0;
4
while 𝑢 ≠ nil do
5
if 𝑢. left = nil then temp ← 0;
6
else temp ← 𝑢. left .take ;
7
if (𝑦 + 𝑏 ) + temp < 𝑢.𝑙 then 𝑢 ← 𝑢. left ;
8
else 𝑏 ← 𝑏 + temp + ( 𝑢.ℎ − 𝑢.𝑙 + 1), 𝑢 ← 𝑢. right ;
9
return 𝑦 + 𝑏
그러면 ban 연산은 각 구간 삽입에 대해 $$ 𝑂 (log |𝐵 |)
시간이 걸린다. 또한 우리는 Algorithm 1과 같이 𝐵.𝑝𝑖𝑐𝑘 의 효율적 구현을 설계한다. 알고리즘은 개념적으로 N[1, 𝐻 ]의 금지되지 않은 원소들을 하나의 “압축된 가용 공간” N[1, 𝐻 − 𝑟 .𝑡𝑎𝑘𝑒 ]로 이어붙인 것으로 본다. 여기서 𝑟 는 𝑇 𝐵 의 루트이다. 먼저 N[1, 𝐻 − 𝑟 .𝑡𝑎𝑘𝑒 ]에서 무작위 정수 𝑦 를 균등하게 표본추출한 다음, 892 𝑇 𝐵 를 순회하여 위치 𝑦 에 대응하는 금지되지 않은 구간을 찾고, 그 앞선 모든 금지 구간 길이의 총합과 같은 오프셋 𝑏 를 계산한다. 마지막으로 알고리즘은 𝑦 +𝑏 를 반환하는데, 이는 원래 공간 N[1, 𝐻 ]\∪ 𝐼 ∈𝐵 𝐼 에서의 매핑된 값이다. 예를 들어 𝐻 = 8이고 𝐵 = {[ 2, 3], [6, 6]} 라고 하자. 금지되지 않은 구간은 [1, 2], [4, 5], [7, 8]이고, 이들의 이어붙임은 압축된 가용 공간 N[1, 5]를 이룬다. 만약 N[1, 5]에서 𝑦 = 4가 표본추출되면, 이는 세 번째 금지되지 않은 구간 [7, 8]에 대응한다. 따라서 알고리즘은 𝑦 + 𝑏 = 4 + (|[ 2, 3]| + |[ 6, 6]|) = 7 을 반환한다. 𝑇 𝐵 의 높이는 최대 $$ 𝑂 (log |𝐵 |)이므로, Algorithm 1은
시간에 동작한다. 또한 𝑦 는 압축된 가용 공간에서 균등하게 표본추출되므로, 특정 금지되지 않은 구간에 대응할 확률은 그 크기에 비례하고, 𝑦 + 𝑏 는 그 구간 내에서 균등 분포를 따른다. 따라서 Algorithm 1은 집합 N[1, 𝐻 ] \ ⋃︁ 𝐼 ∈𝐵 𝐼 로부터 균등 표본을 생성한다.
비고. Ban-Pick tree는 기본 데이터 저장 및 접근 메커니즘과 독립적이므로, 코드 수정 없이 다양한 데이터베이스 시스템에 통합될 수 있다.
임의의 조인 질의 𝑄 가 주어졌을 때, ∀𝑖 > 𝑁 , 𝜑 𝑄 (𝑖 ) =⊥를 만족하는 |Res (𝑄 )|의 상한 𝑁 을 두자. Algorithm 2는 [1, 𝑁 ] \ 𝐵 에서 정수를 균등 무작위로 반복 선택함으로써 Res (𝑄 )의 모든 튜플을 열거한다.
여기서 𝐵 는 자명 정수와 선택 정수를 포함하는 금지 구간들의 집합이다. 선택된 각 정수 𝑖 는 RRAccess 𝑄,𝜑 에 전달된다. 만약 𝜑 𝑄 (𝑖 ) ≠⊥이면, 즉 RRAccess 𝑄,𝜑 가 유효한 결과 튜플을 반환하면, 알고리즘은 그 튜플을 출력하고 중복을 피하기 위해 [𝑖, 𝑖 ]를 𝐵 에 삽입한다. 반대로 𝜑 𝑄 (𝑖 ) =⊥이면, 즉 𝑖 가 RRAccess 𝑄,𝜑 가 반환한 자명 구간 𝐼 안에 있음을 뜻하면, 알고리즘은 그 전체 구간 𝐼 를 𝐵 에 삽입한다. 이 과정은 각 결과 튜플이 정확히 한 번만 출력됨을 보장한다. 또한 각 단계에서 출력되는 튜플(존재한다면)은 아직 열거되지 않은 조인 결과의 집합에서 균등하게 표본추출된다.
Algorithm 2: REnum
Input: 𝑄
Output: Res (𝑄 ) in a random order
1
𝐵 ← ∅ , 𝑁 ban ← 0;
2
while 𝑁 ban < 𝑁 do
3
𝑖 ← 𝐵.𝑝𝑖𝑐𝑘 (𝑁 );
4
𝑟𝑒𝑠 ← RRAccess 𝑄,𝜑 ∗ (𝑖 );
5
if 𝑟𝑒𝑠 is a tuple in Res (𝑄 ) then
6
output 𝑟𝑒𝑠 ;
7
𝐵.𝑏𝑎𝑛 ([ 𝑖, 𝑖 ]) , 𝑁 ban ← 𝑁 ban + 1;
8
else 𝐵.𝑏𝑎𝑛 (𝑟𝑒𝑠 ), 𝑁 ban ← 𝑁 ban + | 𝑟𝑒𝑠 |;
Lemma 1. For any 𝑄 ∈ Q, if log 𝑁 ≤ $$ 𝑂 (log |𝑄 |)
𝑂 (log 2 |𝑄 |)
worst-case time and $$ 𝑂 (log |𝑄 |)amortized time, then Al-gorithm 2 enumerates the tuples in Res (𝑄 ) in random order with expected $$ 𝑂 ( 𝑁
|Res (𝑄 ) |+ 1
log 2 |𝑄 |)
delay and $$ 𝑂 (𝑁 log |𝑄 |)total time.
𝑁 ≤ AGM (𝑄 )인 경우, 즉 Lemma 1의 RRAccess 𝑄,𝜑 가 ∀𝑖 > AGM (𝑄 ), 𝜑 (𝑖 ) =⊥를 만족하는 경우, Algorithm 2는 조인 결과를 기댓값 $$ 𝑂 ( AGM (𝑄 )|Res (𝑄 ) |+ 1 log 2 |𝑄 |)
지연과 $$ 𝑂 (AGM (𝑄 ) log |𝑄 |)총 실행 시간으로 무작위 순서 열거한다. 여기서 𝜌 ∗는 𝐺 𝑄 의 분수 간선 덮개 수이다. 또한 [ 13 ]에 의해 $$ 𝑂 (AGM (𝑄 ) log |𝑄 |)
총 실행 시간은 조합적 𝑘 -clique 가설이 거짓이 아닌 한 최악의 경우 거의 최적이다. 더 나아가, 처음 열거된 결과 튜플은 𝑅𝑒𝑠 (𝑄 )에서의 균등 표본이므로, 조인 표본추출 알고리즘의 기댓값 실행 시간 하한은 무작위 순서 열거 알고리즘의 기댓값 지연 하한이기도 하다. 형식적으로 다음 정리가 성립한다. Theorem 2. Under the combinatorial 𝑘 -clique hypothesis, for any 𝜀 > 0, there is no random-order enumeration algorithm for join queries with expected $$ 𝑂 ˜ ( |𝑄 |𝜌 ∗ −𝜀 > |Res (𝑄 ) |+ 1 )delay after a $$ 𝑂 ˜ (| 𝑄 |)
-time preprocessing, where 𝜌 ∗ is the minimal fractional edge cover number of 𝐺 𝑄 . 이 정리는 $$ 𝑂 ˜ (| 𝑄 |)시간 전처리 후, 기댓값 $$ 𝑂 ( AGM (𝑄 )|Res (𝑄 ) |+ 1 log 2 |𝑄 |) ≤ 𝑂 ( |𝑄 |𝜌 ∗
|Res (𝑄 ) |+ 1
log 2 |𝑄 |)
인 지연이 거의 최적임을 뜻한다. ## 4 RELAXED RANDOM-ACCESS 이 절에서는 $$ 𝑂 (log 2 |𝑄 |)최악 시간과 $$ 𝑂 (log |𝑄 |)
상각 시간을 달성하는 RRAccess 의 효율적인 구현을 제시한다. 이어서 결과로 얻어지는 REnum 알고리즘을 분석하고, 공간 사용량을 줄이는 기법들을 소개한다. 이러한 보장을 달성하기 위해 RRAccess 는 relaxed random-access tree (RRATree) 라 부르는 개념적 트리 구조, 즉 𝑇 ˜ 𝑄 를 기반으로 구축된다. ## 4.1 RRATree와 RRAccess 개요 직관적으로 RRATree는 조인 질의의 활성 도메인을 재귀적으로 분할하는 개념적 트리이다. 루트는 전체 활성 도메인을 나타내고, 각 노드는 필터로 특징지어지는 도메인의 부분집합에 대응하며, 각 조인 결과는 하나의 리프에 대응한다. 형식적으로 RRATree는 다음과 같이 정의된다. Definition 1 (RRATree). Let 𝑄 be an arbitrary join query. The RRATree of 𝑄 , denoted by 𝑇 ˜ 𝑄 , is a rooted tree that satisfies: (1) each node 𝑢 ∈ 𝑇 ˜ 𝑄 corresponds to a filter 𝜓 𝑢 ,(2) let 𝑟 be the root node of 𝑇 ˜ 𝑄 , then the filter 𝜓 𝑟 can be computed in $$ 𝑂 (| 𝑄 |)time and satisfies 𝑄 = 𝑄 |𝜓 𝑟 ,(3) there is an upper-bound algorithm 𝑢𝑝𝑝 which takes a filter
𝜓 𝑢 with 𝑢 ∈ 𝑇 ˜ 𝑄 as input and returns a positive integer in
time, such that (a) ∀𝑢 ∈ 𝑇 ˜ 𝑄 , 𝑢𝑝𝑝 (𝜓 𝑢 ) ≥ | Res (𝑄 |𝜓 𝑢 )| ,(b) for any filter 𝜓 𝑢 with 𝑢 ∈ 𝑇 ˜ 𝑄 and 𝑢𝑝𝑝 (𝜓 𝑢 ) ≤ 1, Res (𝑄 |𝜓 𝑢 )
can be computed in $$ 𝑂 (log |𝑄 |)
time, (4) there is a children exploration algorithm 𝑐ℎ𝑖𝑙𝑑𝑟𝑒𝑛 , such that for each node 𝑢 ∈ 𝑇 ˜ 𝑄 , 𝑐ℎ𝑖𝑙𝑑𝑟𝑒𝑛 (𝜓 𝑢 ) returns at most a con-stant number of filters 𝜓 𝑣 1 , . . . ,𝜓 𝑣 𝑘 in $$ 𝑂 (log |𝑄 |)time, such that (a) ∀𝑢 ∈ 𝑇 ˜ 𝑄 , 𝑐ℎ𝑖𝑙𝑑𝑟𝑒𝑛 (𝜓 𝑢 ) = ∅ iff 𝑢𝑝𝑝 (𝜓 𝑢 ) ≤ 1,(b) ⋃︁ 𝑘 𝑖 =1 Res (𝑄 |𝜓 𝑣 𝑖 ) = Res (𝑄 |𝜓 𝑢 ),(c) ∀1 ≤ 𝑖 < 𝑗 ≤ 𝑘, Res (𝑄 |𝜓 𝑣 𝑖 ) ∩ Res (𝑄 |𝜓 𝑣 𝑗 ) = ∅,(d) ∑︁ 𝑘 𝑖 =1 𝑢𝑝𝑝 (𝜓 𝑣 𝑖 ) ≤ 𝑢𝑝𝑝 (𝜓 𝑢 ),(e) ∀1 ≤ 𝑖 ≤ 𝑘, 𝑢𝑝𝑝 (𝜓 𝑣 𝑖 ) ≤ 12𝑢𝑝𝑝 (𝜓 𝑢 ).
893 1,4 , 1,4 , 1,4
𝑢𝑝𝑝 =8 1,2,1,4,1,4 𝑢𝑝𝑝 =2 3,3,4,4,1,3 𝑢𝑝𝑝 =1 3,3,4,4,4,4 𝑢𝑝𝑝 =1 4,4,1,4,1,4 𝑢𝑝𝑝 =2 2,2,1,3,1,4 𝑢𝑝𝑝 =1 4,4,1,3,1,4 𝑢𝑝𝑝 =1 (2,3,4) (3,4,1)(3,4,4) ∅ 12345678
Figure 1은 𝑄 Δ의 RRATree를 보여주는데, 루트 노드는 𝑄 Δ의 전체 활성 도메인을 나타내고, 그 네 개의 자식은 각각 필터로 정의되는 도메인의 네 개의 서로소 부분집합을 나타낸다. RRATree를 바탕으로 우리는 함수족 𝜑 ∗를
𝑢𝑝𝑝 와 함께 정의하고 RRAccess 알고리즘을 개발한다. 직관적으로 Figure 1에서 루트 노드의 상한은 8이므로 구간 N[1, 8]에 대응된다. 그리고 그 네 자식은 각자의 상한에 해당하는 길이를 갖는 네 개의 서로소 부분구간에 대응되며, 그림에서는 색으로 구분되어 있다. 이 접근은 각 결과 튜플이 하나의 유일한 정수에 할당될 때까지 재귀되며, 그 정수는 다시 𝜑 ∗
𝑄 Δ
에서 해당 튜플로 매핑된다. 남은 정수들은 ⊥로 매핑된다. 형식적으로 조인 질의 𝑄 와 필터 집합 위의 부분순서 관계 ≺를 고정하자. 각 정수 𝑖 > 0에 대해, 만약 𝑡 ∈ Res (𝑄 )인 튜플이 존재하여
𝑖 =
ℎ−1
∑︂
𝑗 =1
∑︂ 𝜓 ∈𝑆 𝑗
𝑢𝑝𝑝 (𝜓 ) + 1, (1) where 𝑆 𝑗 = {𝜓 ∈ children (𝜓 𝑢 𝑗 ) | 𝜓 ≺ 𝜓 𝑢 𝑗 +1 }, 𝑢 1, . . . , 𝑢 ℎ is the path from the root 𝑟 to the leaf 𝑢 𝑡 (𝑢 1 = 𝑟 and 𝑢 ℎ = 𝑢 𝑡 ), and 𝑢 𝑡 ∈ 𝑇 ˜ 𝑄 is the leaf node such that 𝑡 ∈ Res (𝑄 |𝜓 𝑢𝑡 ), then 𝜑 ∗
𝑄
(𝑖 ) = 𝑡 . 그렇지 않고 그러한 튜플이 존재하지 않으면, 𝜑 ∗
𝑄
(𝑖 ) =⊥로 정의한다. 그러면 다음 보조정리가 성립한다.
Lemma 2. ∀𝑖 > 𝑢𝑝𝑝 (𝜓 𝑟 ), 𝜑 ∗
𝑄
(𝑖 ) =⊥.
우리의 relaxed random-access 알고리즘은 Algorithm 3으로 구현된다. 알고리즘은 𝜓 𝑟 에서 시작하는데, 이는 $$ 𝑂 (| 𝑄 | log |𝑄 |)
시간의 인덱스 구축 후 $$ 𝑂 (1)시간에 계산할 수 있다. 그 다음 3-8행에서 알고리즘은 위에서 아래로 𝑇 ˜ 𝑄 를 순회하며 𝜑 ∗
𝑄
(𝑖 )를 포함할 수 있는 필터들의 경로를 찾는다. 각 필터 𝜓 와 그 자식들 𝑐ℎ𝑖𝑙𝑑𝑟𝑒𝑛 (𝜓 ) = 𝜓 1, . . . ,𝜓 𝑘 에 대해
𝑢𝑝𝑝 (𝜓 𝑖 ) ≤ 12𝑢𝑝𝑝 (𝜓 ) 가 모든 1 ≤ 𝑖 ≤ 𝑘 에 대해 성립하므로, 𝑇 ˜ 𝑄 의 깊이는 최대 $$ 𝑂 (log 𝑢𝑝𝑝 (𝜓 𝑟 ))
이고 노드 수는 𝑂 (𝑢𝑝𝑝 (𝜓 𝑟 )) 이다. 또한 𝑇 ˜ 𝑄 에서 순회된 모든 노드의 필터, 상한, 자식을 저장하는 캐싱 메커니즘을 사용하면(즉 중복 계산을 피하면), 𝑢𝑝𝑝 (𝜓 𝑟 ) ≤ AGM (𝑄 )인 경우 다음 보조정리가 성립한다. Lemma 3. If 𝜓 𝑟 can be computed in $$ 𝑂 (1)time, and there exist an algorithm 𝑢𝑝𝑝 and an algorithm 𝑐ℎ𝑖𝑙𝑑𝑟𝑒𝑛 satisfying the properties in Definition 1 and running in $$ 𝑂 (log |𝑄 |)
time, then if 𝑢𝑝𝑝 (𝜓 𝑟 ) ≤ AGM (𝑄 ), Algorithm 3 is a relaxed random-access algorithm running in $$ 𝑂 (log 2 |𝑄 |)worst-case time and $$ 𝑂 (log |𝑄 |)
amortized time. Algorithm 3: RRAccess 𝑄,𝜑 ∗ Input: 𝑖 Output: 𝜑 ∗ > 𝑄 (𝑖 ) if 𝜑 ∗ > 𝑄 (𝑖 ) ≠⊥, otherwise a trivial interval containing 𝑖 > 1 offset ← 0; > 2 𝜓 ← 𝜓 𝑟 where 𝑟 is the root node of 𝑇 ˜ 𝑄 ; > 3 while 𝑢𝑝𝑝 (𝜓 ) ≥ 2 do > 4 𝜓 1, . . . ,𝜓 𝑘 ← 𝑐ℎ𝑖𝑙𝑑𝑟𝑒𝑛 (𝜓 ); > 5 if offset +∑︁ 𝑘 𝑗 =1 𝑢𝑝𝑝 (𝜓 𝑘 ) < 𝑖 then return [𝑖, 𝑖 ]; > 6 𝑟 ∗ ← min {𝑟 ∈ N[1, 𝑘 ]| offset +∑︁ 𝑟 𝑗 =1 𝑢𝑝𝑝 (𝜓 𝑗 ) ≥ 𝑖 }; > 7 offset ← offset +∑︁ 𝑟 ∗ −1 > 𝑗 =1 𝑢𝑝𝑝 (𝜓 𝑗 ); > 8 𝜓 ← 𝜓 𝑟 ∗ ; > 9 if Res (𝑄 |𝜓 ) ≠ ∅ then > 10 return the tuple in Res (𝑄 |𝜓 ) > 11 else return [𝑖, 𝑖 ]; 비고. 단순화를 위해, 이 절의 RRAccess 알고리즘은 나이브한 방법의 자명 구간 발견만 구현한다. 구체적으로 𝜑 𝑄 (𝑖 ) =⊥이면 알고리즘은 singleton 구간 [𝑖, 𝑖 ]만 반환한다. Section 5에서는 RRAccess 실행 중 더 큰 자명 구간을 효율적으로 발견하는 기법을 소개하여, 실제 열거 효율을 향상시킬 것이다. 이하에서는 트리 노드의 적절한 필터, $$ 𝑂 (log |𝑄 |)시간 상한 알고리즘, 그리고 $$ 𝑂 (log |𝑄 |)
시간 자식 탐색 알고리즘을 소개한다. ## 4.2 트리 노드의 필터 본 논문에서 𝑇 ˜ 𝑄 의 노드들에 대응하는 모든 필터는 구간 필터(range filter)로 정의된다. 형식적으로 임의의 노드 𝑢 ∈ 𝑇 ˜ 𝑄 에 대해, 필터 𝜓 𝑢 는 구간들의 목록으로 표현될 수 있다: 𝜓 𝑢 = [[ 𝑙 𝑢, 1, ℎ 𝑢, 1], . . . , [𝑙 𝑢,𝑛 , ℎ 𝑢,𝑛 ]] .또한 𝜓 𝑢 가 empty range filter(또는 줄여서 empty range)라고 말하는 것은 오직 1 ≤ 𝑖 ≤ 𝑛 인 어떤 𝑖 에 대해 𝑙 𝑢,𝑖 > ℎ𝑢,𝑖 가 성립할 때뿐이다. 튜플 𝑡 ∈ 𝑅 이 𝜓 𝑢 를 만족하는 것은 각 𝑥 𝑖 ∈ att (𝑅 )에 대해 𝑥 𝑖 ∈ [ 𝑙 𝑢,𝑖 , ℎ 𝑢,𝑖 ] 가 성립하는 경우이다. Example 1에서 𝜓 = [[ 1, 2], [1, 4], [1, 4]] 라 두면, 𝑅 |𝜓 = {( 1, 2), (2, 3)} , 𝑆 |𝜓 = 𝑆 , 𝑇 |𝜓 = {( 4, 2)} 이고, 따라서 Res (𝑄 Δ |𝜓 ) = {( 2, 3, 4)} 이다. 또한 루트 노드 𝑟 의 필터는 𝜓 𝑟 =[︁ [min 𝑄 (𝑥 1), max 𝑄 (𝑥 1)] , . . . , [min 𝑄 (𝑥 𝑛 ), max 𝑄 (𝑥 𝑛 )] ]︁ 이며, 여기서 max 𝑄 (𝑥 𝑖 ) = max dom 𝑄 (𝑥 𝑖 ) 이고 min 𝑄 (𝑥 𝑖 ) = min dom 𝑄 (𝑥 𝑖 ) 이다. 1 ≤ 𝑖 ≤ 𝑛 에 대해 이러한 경계는 인덱스 구축 중 $$ 𝑂 (| 𝑄 |)시간에 계산된다. 인덱스가 구축되면 𝜓 𝑟 는 $$ 𝑂 (1)
시간에 얻을 수 있고, ⋃︁ 𝑅 ∈𝑄 𝑅 의 모든 튜플이 𝜓 𝑟 를 만족하므로 𝑄 |𝜓 𝑟 = 𝑄 이다. 또한 우리는 upper-bound 알고리즘과 children exploration 알고리즘이 효율적으로 계산될 수 있는 중요한 구간 필터 클래스인 “prefix range filters”를 정의한다. Definition 2. For any range filter 𝜓 = [[ 𝑙 1, ℎ 1], . . . , [𝑙 𝑛 , ℎ 𝑛 ]] , if there exists an integer 1 ≤ 𝑠 ≤ 𝑛 such that 𝜓 satisfies (1) ∀1 ≤ 𝑖 < 𝑠 , 𝑙 𝑖 = ℎ𝑖 , (2) 𝑙 𝑠 ≤ ℎ𝑠 , and (3) ∀𝑠 ≤ 𝑖 ≤ 𝑛 , 𝑙 𝑖 = min 𝑄 (𝑥 𝑖 ), ℎ 𝑖 = max 𝑄 (𝑥 𝑖 ), then 𝜓 is a prefix range filter with a split position 𝑠 .Moreover, if 𝑠 + 1 is not a split position of 𝜓 , then 𝑠 is the maximum split position of 𝜓 . 𝜓 𝑟 는 분할 위치 1을 갖는 prefix range filter임이 자명하다. 이후에 prefix range filter의 유리한 성질을 논의하고, RRATree의 모든 필터가 prefix range filter임을 증명할 것이다. 894 4.3 상한 알고리즘 𝐺 𝑄 를 𝑄 의 스키마 그래프라 하자. 분수 간선 덮개 𝑐 ∈ 𝐸𝐶 (𝐺 𝑄 )가 주어졌을 때, 이론 분석의 편의를 위해 우선 임의의 구간 필터 𝜓 에 대해 𝑢𝑝𝑝 (𝜓 ) = ⌊AGM 𝑐 (𝑄 |𝜓 )⌋ 로 정의한다. 모든 관계 크기는 정수이므로 AGM 경계의 바닥 함수 값도 여전히 조인 결과 크기의 상한 역할을 한다. 따라서 즉시 𝑢𝑝𝑝 (𝜓 ) ≥ | Res (𝑄 |𝜓 )| 가 성립한다. Section 5에서는 조인 결과 크기에 대한 다른 상한도 소개한다. 더 타이트한 상한은 실제 알고리즘 효율, 즉 열거 지연과 총 실행 시간을 모두 줄여준다. Deng 등 [ 13 ]은 |att (𝑅 )| = 𝑑 인 각 관계 𝑅 에 대해 인덱스 구축 단계에서 $$ 𝑂 (| 𝑅 | log 𝑑 −1 |𝑅 |)시간에 range tree를 구축하고, 임의의 구간 필터 𝜓 에 대해 |𝑅 |𝜓 |를
시간에 계산할 수 있음을 보였다. 이제 우리는 임의의 prefix range filter 𝜓 에 대해, 필터링된 질의 𝑄 |𝜓 의 AGM 경계를 $$ 𝑂 (log |𝑄 |)
시간에 계산할 수 있음을 보인다. AGM 경계는 각 𝑅 ∈ 𝑄 에 대한 기수 |𝑅 |𝜓 | 를 얻고 나면 $$ 𝑂 (1)시간에 계산할 수 있으므로, 이 기수들을 명시된 시간 안에 계산할 수 있음을 보이면 충분하다. 각 𝑅 ∈ 𝑄 에 대해 att (𝑅 ) = {𝑥 𝑟 1 , . . . , 𝑥 𝑟 𝑑 }라 하자. 여기서
𝑑 = |att (𝑅 )| 이고 𝑟 1, . . . , 𝑟 𝑑 ∈ N[1, 𝑛 ]이다. 𝑅 의 모든 튜플이 사전식으로 정렬되어 있다고 가정하자. 특히 ∀𝑡, 𝑡 ′ ∈ 𝑅에 대해, 𝑡 ≺ 𝑡 ′ iff (︁
𝑡 (𝑥 𝑟 1 ), . . . , 𝑡 (𝑥 𝑟 𝑑 ))︁ ≺(︁ 𝑡 ′ (𝑥 𝑟 1 ), . . . , 𝑡 ′ (𝑥 𝑟 𝑑 ))︁ 가 사전식 순서에서 성립한다고 하자. 그러면 함수 𝑅.𝑙𝑜𝑤𝑒𝑟 : Z𝑑 → N 과 𝑅.𝑢𝑝𝑝𝑒𝑟 :
Z𝑑 → N를 정의한다. 임의의 𝑑 -항 튜플 𝑡 에 대해(반드시 𝑅 의 원소일 필요는 없음), 𝑅.𝑙𝑜𝑤𝑒𝑟 (𝑡 )는 𝑡 ′ ≥ 𝑡 인 첫 번째 튜플 𝑡 ′ ∈ 𝑅 의 인덱스를 반환하고, 𝑅.𝑢𝑝𝑝𝑒𝑟 (𝑡 )는 𝑡 ′ > 𝑡 인 첫 번째 튜플
𝑡 ′ ∈ 𝑅 의 인덱스를 반환한다. 𝑅 [𝑡 𝑙 , 𝑡 ℎ ] = {𝑡 ∈ 𝑅 |𝑡 𝑙 ⪯ 𝑡 ⪯ 𝑡 ℎ } 와
𝑅.𝑐𝑛𝑡 (𝜓 ) = |𝑅 [𝑡 𝜓 𝑙 , 𝑡 𝜓 ℎ ]| = 𝑅.𝑢𝑝𝑝𝑒𝑟 (𝑡 𝜓 ℎ ) − 𝑅.𝑙𝑜𝑤𝑒𝑟 (𝑡 𝜓 𝑙 ) 로 정의하자. 여기서 𝜓 =
[[ 𝑙 1, ℎ 1], . . . , [𝑙 𝑛 , ℎ 𝑛 ]] , 𝑡 𝜓 𝑙 = (𝑙 𝑟 1 , . . . , 𝑙 𝑟 𝑑 ) 이고 𝑡 𝜓 ℎ = (ℎ𝑟 1 , . . . , ℎ 𝑟 𝑑 )이다. 그러면 다음 보조정리가 성립한다.
Lemma 4. For any prefix range filter 𝜓 , |𝑅 |𝜓 | = 𝑅.𝑐𝑛𝑡 (𝜓 ).
이제 각 𝑅 ∈ 𝑄 에 대해 $$ 𝑂 (log |𝑅 |)
시간 𝑅.𝑐𝑛𝑡 계산을 지원하는 인덱스를 제시한다. 𝑅.𝑐𝑛𝑡 를 계산하는 가장 단순한 방법은 𝑅 의 모든 튜플을 사전식으로 정렬한 배열을 유지하는 것이다. 이 배열이 있으면, 임의의 prefix range filter 𝜓 에 대해 𝑅.𝑙𝑜𝑤𝑒𝑟 (𝑡 𝜓 𝑙 ) 과 𝑅.𝑢𝑝𝑝𝑒𝑟 (𝑡 𝜓 ℎ ) 를 모두 이진 탐색을 통해 $$ 𝑂 (log |𝑅 |)시간에 계산할 수 있고, 따라서 𝑅.𝑐𝑛𝑡 (𝜓 )도 $$ 𝑂 (log |𝑅 |)
시간에 계산된다. 하지만 이 방법은 갱신에는 비효율적이다. 각 삽입이나 삭제마다 $$ 𝑂 (| 𝑅 |)개의 원소 이동이 필요할 수 있기 때문이다. 질의와 갱신을 모두 효율적으로 지원하기 위해, 우리는 자기 균형 이진 탐색 트리(BST), 예를 들어 AVL tree를 기본 인덱스 구조로 채택한다. 트리의 각 노드는 관계 테이블의 하나의 튜플과 일대일 대응하며, 각 노드의 튜플은 존재하는 경우 왼쪽(오른쪽) 자식의 튜플보다 사전식으로 크다(작다)는 이진 탐색 성질을 유지한다. 더 나아가 각 노드
𝑢 는 자신을 루트로 하는 부분트리의 크기인 𝑢.𝑠𝑖𝑧𝑒 를 저장하여, 관계 내 특정 범위에 있는 튜플 수를 효율적으로 셀 수 있게 한다. 트리 균형 유지와 부분트리 크기 유지 모두 삽입 또는 삭제당 $$ 𝑂 (log |𝑅 |)
시간에 수행할 수 있으므로, 이 인덱스 구조는 로그 오버헤드로 동적 갱신을 효율적으로 지원한다. BST 구조와 저장된 크기를 사용하면, 임의의 튜플 𝑡 ∈ Z𝑑 에 대해 𝑅.𝑙𝑜𝑤𝑒𝑟 (𝑡 ) 와 𝑅.𝑢𝑝𝑝𝑒𝑟 (𝑡 ) 를 루트에서 리프까지의 순회를 통해 $$ 𝑂 (log |𝑅 |)시간에 계산할 수 있다. 즉, 임의의 prefix range filter 𝜓 에 대해 𝑅.𝑐𝑛𝑡 (𝜓 ) = 𝑅.𝑢𝑝𝑝𝑒𝑟 (𝑡 𝜓 ℎ ) − 𝑅.𝑙𝑜𝑤𝑒𝑟 (𝑡 𝜓 𝑙 )
를 $$ 𝑂 (log |𝑅 |)
시간에 계산할 수 있다. 그러면 Lemma 5. For any prefix range filter 𝜓 and any fractional edge cover 𝑐 ∈ 𝐸𝐶 (𝐺 𝑄 ), both AGM 𝑐 (𝑄 |𝜓 ) and AGM (𝑄 |𝜓 ) can be calcu-lated in $$ 𝑂 (log |𝑄 |)time.
따라서 임의의 prefix range filter 𝜓 에 대해 𝑢𝑝𝑝 (𝜓 ) = ⌊AGM 𝑐 (𝑄 |𝜓 )⌋
를 $$ 𝑂 (log |𝑄 |)
시간에 계산할 수 있다. 이제 우리는 𝑢𝑝𝑝 (𝜓 ) ≤ 1일 때 조인 결과 𝑅𝑒𝑠 (𝑄 |𝜓 )를 $$ 𝑂 (log |𝑄 |)시간에 계산할 수 있음을 보이고자 한다. 이를 위해 먼저 𝑢𝑝𝑝 의 성질 하나를 정의하는데, 이를 super-additivity라 하고, 𝑢𝑝𝑝 가 이 성질을 만족하면 𝑢𝑝𝑝 (𝜓 ) ≤ 1인 임의의 𝜓 에 대해 𝑅𝑒𝑠 (𝑄 |𝜓 )를 $$ 𝑂 (log |𝑄 |)
시간에 계산할 수 있음을 증명한다. Property 1 (super-additivity). Given any range filter 𝜓 = [[ 𝑙 1, ℎ 1], . . . , [𝑙 𝑛 , ℎ 𝑛 ]] and 1 ≤ 𝑝 ≤ 𝑛 , for any partition of the inter-val [𝑙 𝑝 , ℎ 𝑝 ] into 𝑘 disjoint sub-intervals 𝐼 1, . . . , 𝐼 𝑘 such that [𝑙 𝑝 , ℎ 𝑝 ] =⋃︁ > 𝑘 𝑖 =1 𝐼 𝑖 and 𝐼 𝑖 ∩𝐼 𝑗 = ∅ for 𝑖 ≠ 𝑗 , the inequality ∑︁ 𝑘 𝑖 =1 𝑢𝑝𝑝 ([[ 𝑙 1, ℎ 1], . . . , 𝐼 𝑖 , . . . , [𝑙 𝑛 , ℎ 𝑛 ]]) ≤ 𝑢𝑝𝑝 (𝜓 ) holds. 상한 알고리즘이 Property 1을 만족하면 이를 super-additive라고 부른다. 그러면 다음 보조정리가 성립한다. Lemma 6. If 𝑢𝑝𝑝 is super-additive, then for any prefix range filter 𝜓 = [[ 𝑙 1, ℎ 1], . . . , [𝑙 𝑛 , ℎ 𝑛 ]] such that 𝑢𝑝𝑝 (𝜓 ) ≤ 1, Res (𝑄 |𝜓 ) can be computed in $$ 𝑂 (log |𝑄 |)time.
또한 이 절에서 제안한 상한 알고리즘은 super-additive이다. 이는 AGM split theorem [ 13 ]으로부터 쉽게 도출될 수 있다. 따라서 𝑢𝑝𝑝 (𝜓 ) ≤ 1인 임의의 prefix range filter 𝜓 에 대해,
Res (𝑄 |𝜓 )를 $$ 𝑂 (log |𝑄 |)
시간에 계산할 수 있다. ## 4.4 자식 탐색 알고리즘 RRAccess 의 경로 탐색 과정에서, 방문한 각 노드의 자식을 $$ 𝑂 (log |𝑄 |)시간에 계산하기 위해, 우리는 효율적인 자식 탐색 알고리즘을 개발한다. 이 알고리즘은 prefix range filter 𝜓 를 입력으로 받아 Definition 1에서 요구하는 자식 필터들 𝜓 1, . . . ,𝜓 𝑘 를 출력한다. 우리의 접근은 Deng 등 [ 13 ]이 제안한 활성 도메인 분할 전략을 따른다. 우리는 새로운 분할 알고리즘과 더 효율적인 자료구조를 도입함으로써 그들의 방법을 개선하며, 이로써 계산 복잡도를 관계의 최대 차수인 𝑑 = max 𝑅 ∈𝑄 att (𝑅 )에 대해 $$ 𝑂 (log 𝑑 |𝑄 |)
에서 $$ 𝑂 (log |𝑄 |)로 줄인다.
divide 연산. 구체적으로 “di-vide” 연산을 정의한다. 이 연산은 𝑠 =
min {𝑖 |𝑙 𝑖 ≠ ℎ𝑖 } 인 구간 필터 𝜓 = [[ 𝑙 1, ℎ 1], . . . , [𝑙 𝑛 , ℎ 𝑛 ]] 를 입력으로 받아, 세 개의 구간 필터 𝜓 left ,𝜓 mid ,𝜓 right 를 출력한다. 이들의 형태는 [[ 𝑙 1, ℎ 1], . . . , [𝑙 ′
𝑠
, 𝑟 ′
𝑠
], . . . , [𝑙 𝑛 , ℎ 𝑛 ]] 이며, 여기서 [𝑙 ′
𝑠
, 𝑟 ′
𝑠
]
는 각각 [𝑙 𝑠 , 𝑝 − 1], [𝑝, 𝑝 ] 및 [𝑝 + 1, ℎ 𝑠 ] 이다. 그리고 (1) 𝑢𝑝𝑝 (𝜓 left ) + 𝑢𝑝𝑝 (𝜓 mid ) + 𝑢𝑝𝑝 (𝜓 right ) ≤ 𝑢𝑝𝑝 (𝜓 ),(2) 𝑢𝑝𝑝 (𝜓 left ) ≤ 12𝑢𝑝𝑝 (𝜓 ), 𝑢𝑝𝑝 (𝜓 right ) ≤ 12𝑢𝑝𝑝 (𝜓 ) 를 만족한다. 상한 알고리즘이 super-additive라고 가정하면, (1)은 임의의 𝑝 ∈ N[𝑙 𝑠 , ℎ 𝑠 ]에 대해 성립한다. Deng 등 [ 13 ]은 𝑢𝑝𝑝 (𝜓 left ) ≥ 12𝑢𝑝𝑝 (𝜓 ) 를 만족하는 [𝑙 𝑠 , ℎ 𝑠 ] 안의 최소 정수를 이진 탐색으로 찾음으로써 (2)를 만족하는 적절한 분할점 𝑝 를 계산한다. 이들의 이진 탐색 과정 각 반복에서는 range tree로 구현된 count oracle을 사용해 각 필터링된 관계의 기수를 계산한다. 이로 인해 divide 연산의 시간 복잡도는 𝑑 = max 𝑅 ∈𝑄 |att (𝑅 )| 에 대해 $$ 𝑂 (log 𝑑 |𝑄 |)
가 된다. 반면 우리는 prefix range filter를 나눌 때 분할점 𝑝 를 $$ 𝑂 (log |𝑄 |)시간에 계산할 수 있음을 보인다. 이를 위해 먼저 𝑠 가 𝜓 의 유효한 분할 위치임을 보이고, 문제를 동등한 최적화 문제로 환원한 다음, 이를 푸는 효율적인 $$ 𝑂 (log |𝑄 |)
시간 알고리즘을 설계한다. Lemma 7. Let 𝜓 = [[ 𝑙 1, ℎ 1], . . . , [𝑙 𝑛 , ℎ 𝑛 ]] be a prefix range filter, then 𝑠 = min {𝑖 |𝑙 𝑖 ≠ ℎ𝑖 } is a split position of 𝜓 . 𝑥 𝑠 ∈ att (𝑅 𝑖 )를 만족하는 각 관계 𝑅 𝑖 ∈ 𝑄 에 대해, 𝐴 𝑖 =[︁ 𝑡 1 (𝑥 𝑠 ), . . . , 𝑡 𝑛 𝑖 (𝑥 𝑠 )]︁ 로 정의하자. 여기서 𝑛 𝑖 = |𝑅 𝑖 |𝜓 | 이고, 𝑅 |𝜓 = {𝑡 1, . . . , 𝑡 𝑛 𝑖 } 및 𝑡 1 ⪯ · · · ⪯ 𝑡 𝑛 𝑖 이다. 우리는 divide 연산에서 “분할점 𝑝 를 계산하는 작업”이 다음 최적화 문제의 한 인스턴스로 볼 수 있음을 관찰한다. Input: a constant number of sorted integer arrays 𝐴 1, . . . , 𝐴 𝑘 and an integer 𝑇 , Output: the maximum integer 𝑝 ∗ such that 𝐹 (𝑝 ∗) ≤ 𝑇 ,where 𝑁 𝑖 (𝑝 ) = |{ 𝑥 ∈ 𝐴 𝑖 |𝑥 < 𝑝 }| , and 𝐹 : N𝑘 → N is an 𝑘 -ary non-decreasing function (For simplicity, we use 𝐹 (𝑝 ) as the shorthand for 𝐹 (𝑁 1 (𝑝 ), . . . , 𝑁 𝑘 (𝑝 )) ). The reduction is obvious since 𝑢𝑝𝑝 can be viewed as a non-decreasing function over the cardinalities of the filtered relations 𝑅 left for each relation 𝑅 ∈ 𝑄 with 𝑥 𝑠 ∈ att (𝑅 ). Algorithm 4: Multi Head Binary Search (MHBS) Input: 𝐴 1, . . . , 𝐴 𝑘 , 𝑇 Output: maximum 𝑝 ∗ such that 𝐹 (𝑝 ∗) ≤ 𝑇 > 1 if 𝐹 (| 𝐴 1 |, . . . , |𝐴 𝑘 |) ≤ 𝑇 then return +∞ ; > 2 for 1 ≤ 𝑖 ≤ 𝑘 do > 3 if 𝑟 𝑖 − 𝑙 𝑖 ≤ 1 then > 4 if 𝐹 (𝐴 𝑖 [𝑙 𝑖 ] + 1) > 𝑇 then return 𝐴 𝑖 [𝑙 𝑖 ]; > 5 else 𝑚 𝑖 ← 𝑟 𝑖 ; > 6 else 𝑙 𝑖 ← 0, 𝑟 𝑖 ← | 𝐴 𝑖 |, 𝑚 𝑖 ← ⌊ 𝑙 𝑖 +𝑟 𝑖 > 2 ⌋; > 7 while ∃𝑖, 𝑟 𝑖 − 𝑙 𝑖 > 1 do > 8 𝑖 min ← arg min > 𝑟 𝑖 −𝑙 𝑖 >1 𝐴 𝑖 [𝑚 𝑖 ], 𝑖 max ← arg max > 𝑟 𝑖 −𝑙 𝑖 >1 𝐴 𝑖 [𝑚 𝑖 ]; > 9 if 𝐹 (𝑚 1, . . . , 𝑚 𝑘 ) ≤ 𝑇 then 𝑙 𝑖 min ← 𝑚 𝑖 min ; > 10 else 𝑟 𝑖 max ← 𝑚 𝑖 max ; > 11 for 𝑖 ∈ { 𝑖 min , 𝑖 max } do 𝑚 𝑖 ← ⌊ 𝑙 𝑖 +𝑟 𝑖 > 2 ⌋; > 12 if ∃𝑖 ∈ { 𝑖 min , 𝑖 max }, 𝑟 𝑖 − 𝑙 𝑖 ≤ 1 then > 13 if 𝐹 (𝐴 𝑖 [𝑙 𝑖 ] + 1) > 𝑇 then return 𝐴 𝑖 [𝑙 𝑖 ]; > 14 else 𝑚 𝑖 ← 𝑟 𝑖 ; > 15 return min > 1≤𝑖 ≤𝑘 𝐴 𝑖 [𝑟 𝑖 ];각 관계 테이블 𝑅 ∈ 𝑄 에서 모든 튜플이 사전식으로 정렬되어 있다고 가정하고, 우리는 위 문제를 $$ 𝑂 (log ∑︁ 𝑘 𝑖 =1 |𝐴 𝑖 |)시간에 해결하는 Multi -Head Binary Search (MHBS) 알고리즘(Algorithm 4 참조)을 제안한다. 직관적으로 MHBS 알고리즘은 각 배열에 대해 하나의 이진 탐색 구간을 유지하고, 선택 기준에 따라 선택된 한 배열의 구간을 반복적으로 절반으로 줄인다. 이 과정은 모든 구간이 최적해로 수렴할 때까지 계속된다.
Lemma 8. Algorithm 4 returns the maximum integer 𝑝 ∗ such that
𝐹 (𝑝 ∗) ≤ 𝑇 in $$ 𝑂 (log ∑︁ 𝑘 𝑖 =1 |𝐴 𝑖 |)
time. ∑︁ 𝑘 𝑖 =1 |𝐴 𝑖 | ≤ ∑︁ 𝑘 𝑖 =1 |𝑅 𝑖 | ≤ | 𝑄 | 이므로, 즉시 Corollary 1. The divide operation on any prefix range filter can be performed in $$ 𝑂 (log |𝑄 |)time.
x y
z
𝜓
children
x y
z
𝜓 1
𝜓 2
𝜓 3
𝜓 4
𝜓 5
𝜓 6 𝜓 7
Figure 2: 𝜓 의 𝑄 Δ에서의 분할.
비고. 각 관계 테이블의 모든 튜플이 사전식으로 정렬되어 있다는 가정은 분석의 편의를 위한 것이며, 일반성을 잃지 않는다. 균형 트리, B-tree, skip list, trie와 같은 다른 계층적 인덱싱 구조들도 Section 4.3에서 논의한 것과 유사한 방식으로 약간의 구현 수정만으로 지원할 수 있기 때문이다.
Algorithm 5: 𝑐ℎ𝑖𝑙𝑑𝑟𝑒𝑛
Input: 𝜓
Output: a list of filters
1
if 𝑢𝑝𝑝 (𝜓 ) ≤ 1 then return ∅;
2
𝑟𝑒𝑠 ← ∅ ;
3
divide 𝜓 into 𝜓 left ,𝜓 mid ,𝜓 right ;
4
if 𝑢𝑝𝑝 (𝜓 left ) > 0 and 𝜓 left is not empty then
5
𝑟𝑒𝑠 ← 𝑟𝑒𝑠 ∪ { 𝜓 left }
6
if 𝑢𝑝𝑝 (𝜓 mid ) = 1 then 𝑟𝑒𝑠 ← 𝑟𝑒𝑠 ∪ { 𝜓 mid };
7
else 𝑟𝑒𝑠 ← 𝑟𝑒𝑠 ∪ 𝑐ℎ𝑖𝑙𝑑𝑟𝑒𝑛 (𝜓 mid );
8
if 𝑢𝑝𝑝 (𝜓 right ) > 0 and 𝜓 right is not empty then
9
𝑟𝑒𝑠 ← 𝑟𝑒𝑠 ∪ { 𝜓 right }
10
return res; 그러면 임의의 prefix range filter 𝜓 에 대해, 𝑐ℎ𝑖𝑙𝑑𝑟𝑒𝑛 (𝜓 )는 Algorithm 5와 같이 재귀 방식으로 $$ 𝑂 (log |𝑄 |)
시간에 계산할 수 있다. 재귀 깊이는 최대 𝑑 이므로, Algorithm 5는 최대 2𝑑 + 1 ≤ $$ 𝑂 (1)개의 필터를 반환한다. Example 1에서 하나의 prefix range filter 𝜓 는 Figure 2에 보인 것처럼 최대 7개의 필터로 분할될 수 있다. 임의의 필터 𝜓 에 대해 𝑢𝑝𝑝 (𝜓 ) =
⌊AGM 𝑐 ∗ (𝑄 |𝜓 )⌋ 이고 𝑐 ∗ (𝑅 ) = 𝑐 ∗ (𝑆 ) = 𝑐 ∗ (𝑇 ) = 12 라고 하자.
𝑇 ˜ 𝑄 Δ 는 최종적으로 Figure 1과 같이 구성된다. 또한 분할 연산의 정의와 Property 1에 의해, 반환된 필터들이 Definition 1의 성질을 만족함은 쉽게 증명할 수 있다. 마지막으로 𝑇 ˜ 𝑄 의 모든 필터가 prefix range filter임을 확립한다.
Lemma 9. For any prefix range filter 𝜓 , let 𝜓 left , 𝜓 mid and 𝜓 right
d denote the three filters obtained by dividing 𝜓 , then all non - empty ranges among these filters are prefix range filters.
루트 노드의 필터(즉 𝜓 𝑟 )가 prefix range filter이므로, 귀납적으로 다음이 따른다.
Corollary 2. For any node 𝑢 ∈ 𝑇 ˜ 𝑄 , 𝜓 𝑢 is a prefix range filter.
위 구현들은 REnum 성능에 대한 이론적 보장을 제공한다. 다음 정리는 𝑁 = 𝑢𝑝𝑝 (𝜓 𝑟 )
이고 임의의 구간 필터 𝜓 에 대해 𝑢𝑝𝑝 (𝜓 ) =⌊︁ AGM 𝑐 ∗ (𝑄 |𝜓 )⌋︁ 로 두었을 때 Algorithm 2를 분석함으로써 증명할 수 있다.
896 Theorem 3. There exists a constructive random-order enumeration algorithm for join queries with expected $$ 𝑂 ( AGM (𝑄 )|Res (𝑄 ) |+ 1 log 2 |𝑄 |)
delay and $$ 𝑂 (AGM (𝑄 ) log |𝑄 |)total running time, after an $$ 𝑂 (| 𝑄 | log |𝑄 |)
-time index construction phase. Theorem 2와 [ 13 ]의 결과는 조합적 𝑘 -clique 가설 하에서, $$ 𝑂 (| 𝑄 | log |𝑄 |)시간 인덱스 구축 단계 후 Algorithm 2의 기댓값 지연과 총 실행 시간이 모두 거의 최악의 경우 최적임을 보여준다.
비고. 우리의 알고리즘은 정적 관계에만 적용되는 것이 아니라, 데이터가 자주 삽입, 삭제, 갱신되는 진화하는 환경도 효율적으로 지원한다. Section 4.3과 4.4에서 논의했듯, 우리 프레임워크의 인덱스 구성 요소는 균형 트리, B-tree, skip list, trie와 같은 동적 자료구조를 이용해 구현할 수 있다. 이러한 동적 인덱스를 사용하면 제안한 알고리즘은 로그 시간 갱신을 지원하므로, 혼합 워크로드를 갖는 현대 데이터 시스템에 매우 적합하다.
우리 알고리즘의 공간 복잡도는 두 구성요소가 지배한다: (1) ban-pick tree, (2) 캐시된 RRATree 구조. ban-pick tree와 RRATree 모두 최대
𝑂 (AGM (𝑄 )) 개의 노드를 포함하고, 각 노드는 평균적으로 $$ 𝑂 (1)
공간을 차지하므로, 전체 공간 복잡도는 $$ 𝑂 (AGM (𝑄 ))이다. 실제 환경에서는 캐싱 메커니즘의 성능 이점을 대체로 유지하면서 공간 오버헤드를 줄이기 위한 세 가지 기법을 제안한다. 이 모든 기법은 Section 6에서 구현 및 평가된다.
금지 구간 병합. 새로운 구간 𝐼 를 금지할 때,
𝐵.𝑏𝑎𝑛 은 ban-pick tree를 루트에서 리프까지 순회하며 그 위치를 찾는다. 이 과정에서 𝐼 가 기존 노드의 구간과 병합될 수 있으면, 그 노드를 병합된 구간으로 갱신하여 𝐼 를 위한 새 노드를 만들 필요를 없앤다. 이 전략은 트리의 정확성을 유지하면서 공간 사용량을 줄인다.
필터의 온디맨드 해제. RRATree 노드가 자식 탐색 알고리즘에 의해 처리되고 나면, 그에 연관된 필터는 이후 과정에서 더 이상 필요하지 않다. 따라서 이러한 필터가 차지하는 메모리를 해제하여 전체 공간 오버헤드를 줄일 수 있다.
깊이 제한 캐싱. 열거 과정에서 RRATree의 깊이가 작은 노드일수록 훨씬 자주 접근되며, 노드 수는 깊이에 따라 급격히 증가한다. 따라서 메모리 예산이 제한될 때는 특정 깊이 임계값 이내의 노드만 캐싱하여, 자주 접근되는 노드를 저장하는 데 메모리를 가장 효과적으로 활용하고, 중복 재계산을 가능한 한 많이 줄인다.
명백하게도 큰 AGM (𝑄 )와 AGM (𝑄 )|𝑅𝑒𝑠 (𝑄 ) |+ 1 은 REnum 의 열거 지연과 총 실행 시간을 길게 만든다. 이 병목을 해결하기 위해, 우리의 열거 프레임워크를 바탕으로 실제에서 효율을 크게 향상시키는 두 가지 가속 기법을 제안한다.
우리는 자명 구간이 종종 연속적인 시퀀스로 나타나므로 더 큰 구간으로 묶을 수 있음을 관찰했다. 특히 AGM (𝑄 ) ≫ | 𝑅𝑒𝑠 (𝑄 )| 인 경우 그렇다. 열거 중 이러한 자명 정수들이 자주 선택되는 것을 피하기 위해 Larger Triv-ial Interval discovery (LTI) 기법을 제안한다. 이전 RRAccess 구현이 𝜑 𝑄 (𝑖 ) =⊥일 때 단일 점 구간 [𝑖, 𝑖 ]만 반환했던 것과 달리, LTI는 더 큰 자명 구간을 발견하여 더 많은 자명 정수가 후속 단계에서 선택되지 않도록 함으로써 열거를 가속한다.
필터의 자명 구간. 𝜑 ∗
𝑄
(𝑖 ) =⊥일 때, Algorithm 3은 오직 5행이나 11행에서만 자명 구간을 반환할 수 있음을 관찰하라. 𝑇 ˜ 𝑄 의 정의에 의해, 각 필터 𝜓 가 𝑐ℎ𝑖𝑙𝑑𝑟𝑒𝑛 (𝜓 ) =
𝜓 1, . . . ,𝜓 𝑘 를 만족하면 𝑢𝑝𝑝 (𝜓 ) ≥ ∑︁ 𝑘 𝑖 =1 𝑢𝑝𝑝 (𝜓 𝑖 ) 이다. 따라서 어떤 정수 𝑖 가
(오프셋 제거 후) (∑︁ 𝑘 𝑖 =1 𝑢𝑝𝑝 (𝜓 𝑖 ), 𝑢𝑝𝑝 (𝜓 )] 안에 들어가면, 𝜑 ∗
𝑄
(𝑖 ) =⊥가 된다. 즉, 이러한 구간은 발견되어 후속 단계에서 금지되어야 한다. 그러면 5행의 경우, 임의의 정수 offset +∑︁ 𝑘 𝑗 =1 𝑢𝑝𝑝 (𝜓 𝑘 ) < 𝑡 ≤ offset + 𝑢𝑝𝑝 (𝜓 ) 에 대해
𝜑 ∗
𝑄
(𝑡 ) =⊥ 이므로, 필터 𝜓 의 자명 구간을
𝐼 𝜓 =
⎡⎢⎢⎢⎢⎣
offset +
𝑘
∑︂
𝑗 =1
𝑢𝑝𝑝 (𝜓 𝑘 ) + 1, offset + 𝑢𝑝𝑝 (𝜓 )
⎤⎥⎥⎥⎥⎦
, (2) 로 정의하고, RRAccess 𝑄,𝜑 ∗ 가 [𝑖, 𝑖 ] 대신 𝐼 𝜓 를 반환하게 한다. 11행의 경우 알고리즘은 이미 𝑇 ˜ 𝑄 의 리프 노드에 도달한 상태이며(즉 𝑢𝑝𝑝 (𝜓 ) = 1), 그 리프 노드는 어떤 결과 튜플에도 대응하지 않는다. 따라서 𝜓 의 자명 구간을 𝐼 𝜓 = [𝑖, 𝑖 ] 로 정의하고 RRAccess 𝑄,𝜑 ∗ 가 이를 반환하게 한다. Example 1에서 열거 과정 중 RRAccess 𝑄 Δ,𝜑 ∗ (7)을 호출하면, 알고리즘은 먼저 𝐶 𝑟 ← 𝑐ℎ𝑖𝑙𝑑𝑟𝑒𝑛 (𝜓 𝑟 )를 계산한다. Figure 1에 보인 것처럼 ∑︁ 𝜓 ∈𝐶 𝑟 𝑢𝑝𝑝 (𝜓 ) = 6 < 7 이므로,
𝐼 𝜓 𝑟 =[︁∑︁ 𝜓 ∈𝐶 𝑟 𝑢𝑝𝑝 (𝜓 ) + 1, 𝑢𝑝𝑝 (𝜓 𝑟 )]︁ = [7, 8] 을 반환한다. 그러면 Ban-Pick tree는 [7, 8]을 금지하고 후속 단계에서 그 안의 정수를 더 이상 선택하지 않으므로, RRAccess 𝑄 Δ,𝜑 ∗ (8)을 호출할 필요가 없어진다. 각 자명 구간 [𝑙, ℎ ]은 열거 과정 중 RRAc-cess 𝑄,𝜑 ∗ 에 의해 최대 한 번만 생성된다는 점에 주목하라. 그렇지 않다면 [𝑙, ℎ ]이 금지된 뒤에도 그 안의 어떤 정수 𝑖 ∈ [ 𝑙, ℎ ]가 선택되어야 하는데, 이는 모순이다. 또한 𝑇 ˜ 𝑄 와 𝜑 ∗의 정의에 의해, 𝑇 ˜ 𝑄 의 필터들에 대한 자명 구간들은 서로 서로소이다. 이 기본 LTI 기법은 Section 6에서 평가한다.
연속 자명 구간 병합. 우리는 많은 자명 구간이 서로 이어져 있으며 더 큰 구간으로 병합될 수 있음을 관찰했다. 구체적으로 𝑇 ˜ 𝑄 와 𝜑 ∗의 정의에 의해, 𝑇 ˜ 𝑄 안의 임의의 필터 𝜓
에 대해, 𝜓 ′ ∈ 𝑐ℎ𝑖𝑙𝑑𝑟𝑒𝑛 (𝜓 ) 를 𝜓 의 마지막 자식이라 하자. 그러면 구간
𝐼 𝜓 와 𝐼 𝜓 ′ 는 서로 연속된다. 예를 들어 𝑇 ˜ 𝑄 Δ (Figure 1)에서 루트 필터 𝜓 𝑟 의 마지막 자식은 𝜓 ′
𝑟
= [[ 4, 4], [1, 4], [1, 4]] 이고, 따라서 자명 구간 𝐼 𝜓 ′
𝑟
= [6, 6] 은 𝐼 𝜓 𝑟 = [7, 8] 과 연속된다. 더 나아가 RRAccess 의 재귀 과정에서 필터 𝜓 의 자명 구간 𝐼 𝜓 를 얻고 나면, 𝐼 𝜓 와 병합 가능한 연속 자명 구간들을 계산하기 위해 현재 필터의 마지막 자식을 재귀적으로 방문하고, 재귀 복귀 시 부모의 자명 구간과 병합 가능한지를 판별할 수 있다(예를 들어 𝜓 가 부모 𝜓 ∗의 마지막 자식이라면, 자명 구간 𝐼 𝜓 ∗ 는 𝐼 𝜓 와 병합될 수 있다). 그러면 RRAccess 를 너무 많이 호출하지 않고도 $$ 𝑂 (log |𝑄 |)
시간에 병합된 자명 구간을 얻을 수 있다. 그 결과 열거 과정 중 RRAccess 호출 횟수가 줄어 실제 성능이 향상된다. 또한 열거 과정 중 병합된 두 개의 897 자명 구간이 서로 겹치지 않음을 증명할 수 있다. 우리는 기본 LTI의 이 변형(merging trivial intervals, MTI)을 Section 6에서 평가한다. 배치 자명 구간 발견. RRAccess 호출 수를 더 줄이기 위해, 우리는 MTI 기법을 강화하여 한 번의 RRAccess 실행 안에서 여러 개의 자명 구간을 발견하고 보고하도록 한다. 구체적으로 RRATree의 위에서 아래로의 순회 경로를 따라, 방문한 각 노드의 자명 구간을 계산하고 그 마지막 자식의 사슬을 재귀적으로 탐색한다. 이 경로를 따라 발견된 모든 자명 구간은 가능할 때 병합되어 Ban-Pick Tree에 보고된다. 이 방식으로, 열거 지연은 $$ 𝑂 ( AGM (Q)|𝑅𝑒𝑠 (𝑄 ) | log 3 |𝑄 |)로 증가하지만, 총 실행 시간은 여전히
이며, 열거 과정 중 RRAccess 호출 횟수는 줄어든다. 우리는 MTI의 이 변형(batch trivial interval discovery, BTI)을 Section 6에서 평가한다.
이 절에서는 Tighter Upper-bound estimation (TU) 기법을 소개하며, 이는 LTI의 효과를 강화한다. 먼저 동기 부여 예시를 통해 그 영향을 설명한다. 임의의 𝜓 에 대해 𝑢𝑝𝑝 (𝜓 ) = ⌊AGM (𝑄 |𝜓 )⌋ 를 ⌊AGM 𝑐 ∗ (𝑄 |𝜓 )⌋ 대신 사용한다고 하자. 그러면 𝑇 ˜ 𝑄 Δ 는 Figure 3과 같다. 𝜓 = [[ 4, 4], [1, 4], [1, 4]] 에 대해,
|𝑅 |𝜓 | = |𝑇 |𝜓 | = 1 이고 |𝑆 |𝜓 | = 4 이다. 그러면 𝑢𝑝𝑝 (𝜓 ) = ⌊AGM (𝑄 Δ |𝜓 )⌋ =
1 < ⌊AGM 𝑐 ∗ (𝑄 Δ |𝜓 )⌋ = 2 이다. 이 더 타이트한 상한은 𝜓 𝑟 의 자명 구간 크기를 증가시켜, 𝐼 𝜓 𝑟 = [6, 8] 을 얻게 하며, 이는 [7, 8] 대신이다. 즉 TU는 RRATree의 더 낮은 레벨에 있는 필터들의 자명 구간을 확장하여, 더 많은 자명 정수가 더 이른 시점에 발견되고 금지되도록 하고, 그 결과 LTI의 효과를 강화한다. 이 절에서는 두 가지 서로 다른 상한 알고리즘을 소개한다. 둘 다 Definition 1의 성질을 만족하고 super-additive임을 확인할 수 있다. 실제 구현에서는 각 prefix range filter 𝜓 에 대해, 이 상한 알고리즘들 가운데 최소값을 |𝑅𝑒𝑠 (𝑄 |𝜓 )| 의 추정 상한으로 사용하며, 이를
𝑢𝑝𝑝 ∗ (𝜓 )라고 한다. 이 방식이면 𝑢𝑝𝑝 ∗ 가 Definition 1에서 정의한 성질을 만족함은 분명하다. 또한 다음 보조정리에서 형식화하듯이 super-additive이다.
Lemma 10. If the upper-bound algorithms 𝑢𝑝𝑝 1, . . . , 𝑢𝑝𝑝 𝑐 are super-additive, then the upper-bound algorithm 𝑢𝑝𝑝 ∗, where ∀𝜓 ,
𝑢𝑝𝑝 ∗ (𝜓 ) = min 𝑐 𝑖 =1 𝑢𝑝𝑝 𝑖 (𝜓 ), is also super-additive.
따라서 𝑢𝑝𝑝 ∗ 를 Section 4에서 제시한 상한 알고리즘의 대체물로 사용할 수 있다.
최소화된 AGM 경계 기반 상한. 임의의 조인 질의 𝑄 ∈ Q 에 대해, |𝑅𝑒𝑠 (𝑄 )| ≤ ⌊ AGM (𝑄 )⌋ 이다. 열거 과정에서, 최소 AGM 경계 AGM (𝑄 |𝜓 )는 관계들의 크기 {| 𝑅 |𝜓 || 𝑅 ∈ 𝑄 }를 $$ 𝑂 (log |𝑄 |)
시간에 계산한 뒤 선형계획법을 풀어 $$ 𝑂 (1)시간에 계산할 수 있다. 그러나 이 선형계획법을 푸는 데는 상당한 계산 오버헤드가 든다. 절충안으로, 우리는 소수의 대표적인 분수 간선 덮개를 휴리스틱하게 선택하고, 그에 해당하는 AGM 경계들의 최소값을 계산한다. 이 접근은 선형계획법을 반복적으로 푸는 비용을 피하면서도 효과적으로 더 타이트한 상한을 제공한다. Example 1에서 𝑇 ˜ 𝑄 Δ 의 위에서 아래로 순회 동안, 각 속성의 활성 도메인은 순서대로 𝑥 ,
𝑦 , 𝑧 순으로 점차 축소된다. 𝑥 가 가장 먼저 제약되는 속성이므로, 𝑥 를 포함하는 필터링된 관계들의 기수(즉 𝑅 과 𝑇 )는 𝑇 ˜ 𝑄 Δ 의 각 루트-리프 경로에서 더 빠르게 감소할 것이다. 따라서 𝑅 과 𝑇 에 더 큰 분수 간선 덮개 가중치를 부여하면 더 작은 AGM 경계를 얻게 된다. 예를 들어 prefix range filter
𝜓 = [[ 4, 4], [1, 4], [1, 4]] 를 보자. 𝑐 ∈ 𝐸𝐶 (𝑄 Δ) 이고 𝑐 (𝑅 ) = 𝑐 (𝑇 ) = 1 및
𝑐 (𝑆 ) = 0 이라고 하면, AGM 𝑐 (𝑄 Δ |𝜓 ) = 1 < AGM 𝑐 ∗ (𝑄 Δ |𝜓 ) = 2 이다. 이 예시는 도메인 축소 순서에서 더 일찍 나타나는 속성을 포함하는 관계에 더 큰 분수 간선 덮개 가중치를 할당하면 RRATree의 낮은 레벨에서 더 타이트한 AGM 경계를 얻을 수 있음을 보여준다. 실제로는 이 원칙에 기반해 상수 개수의 분수 간선 덮개를 휴리스틱하게 선택하고, 모든 관계 𝑅 ∈ 𝑄 에 대해 선택된 덮개들 중 적어도 하나의 𝑐 ∈ 𝐸𝐶 (𝑄 )가 𝑐 (𝑅 ) > 0 을 만족하도록 보장한다.
비순환 골격 질의 기반 상한. AGM 경계는 최악의 경우에 타이트하지만, 실제로는 매우 클 수 있으며 실제 결과 크기보다 훨씬 큰 경우가 많다. 이를 해결하기 위해, 우리는 추가적인 테이블 정보를 사용하여 실제에서 더 타이트할 수 있는 또 다른 상한을 제안한다. [ 27 ]에 따르면, 임의의 순환 조인 질의는 관계들의 부분집합을 제거하여 비순환 질의로 변환할 수 있다. 구체적으로 임의의 순환 조인 질의 𝑄 는 두 개의 부분질의 𝑄 𝑠
와 𝑄 𝑟 로 분해될 수 있으며, 𝑄 = 𝑄 𝑠 ⋈︁ 𝑄 𝑟 이다. 여기서 𝑄 𝑠 는 비순환 질의(골격 질의)이고, 𝑄 𝑟 는 남은 관계들로 이루어진 질의(잔여 질의)이다. Example 1에서 삼각형 질의 𝑄 Δ 는 비순환 골격 부분질의
𝑄 Δ𝑠 = 𝑅 (𝑥, 𝑦 )⋈︁ 𝑆 (𝑦, 𝑧 ) 와 잔여 부분질의 𝑄 Δ𝑟 = 𝑇 (𝑥, 𝑧 ) 로 분해될 수 있다. 위 분해를 바탕으로 다음 보조정리가 성립한다.
Lemma 11. For any join query 𝑄 and filter 𝜓 , if att (𝑄 𝑠 ) = att (𝑄 ),then |𝑅𝑒𝑠 (𝑄 |𝜓 )| ≤ | 𝑅𝑒𝑠 (𝑄 𝑠 |𝜓 )| . Otherwise, if att (𝑄 𝑠 ) ⊊ att (𝑄 ), for any fractional edge cover 𝑐 ∈ 𝐸𝐶 (𝐺 𝑄 𝑟 \𝑄 𝑠 ), |𝑅𝑒𝑠 (𝑄 |𝜓 )| ≤ | 𝑅𝑒𝑠 (𝑄 𝑠 |𝜓 )|·
AGM 𝑐 (𝑄 ∗
𝑟
|𝜓 ), where 𝑄 ∗
𝑟
= {𝑅 [att (𝑄 𝑟 ) \ att (𝑄 𝑠 )]| 𝑅 ∈ 𝑄 𝑟 }, and for any attribute set 𝑉 ⊆ att (𝑅 ), 𝑅 [𝑉 ] = {𝑡 [𝑉 ]| 𝑡 ∈ 𝑅 }.
열거 전에 𝑄 ∗
𝑟
에 대해 Section 4에서 설명한 인덱스를 구축하므로, 임의의 𝜓 에 대해 AGM 𝑐 (𝑄 ∗
𝑟
|𝜓 )를 $$ 𝑂 (log |𝑄 |)
시간에 계산할 수 있다. |𝑅𝑒𝑠 (𝑄 𝑠 |𝜓 )| 에 대해서는 각 관계 𝑅 = {𝑡 1, . . . , 𝑡 |𝑅 | }가 사전식으로 정렬되어 있다고 가정하고, 각 𝑅 ∈ 𝑄 𝑠 에 대해 배열 𝐴 𝑅 및 그 prefix-sum 배열을 계산한다. 모든 1 ≤ 𝑖 ≤ | 𝑅 | 에 대해, 𝐴 𝑅 [𝑖 ] = |⋈︁ 𝑅 ′ ∈𝑇 𝑅 𝑅 ′ ⋉ 𝑡 𝑖 | 이며, 여기서 𝑇 𝑅 는 𝑄 𝑠 의 조인 트리에서 𝑅 를 루트로 하는 부분트리를 뜻한다. 이러한 배열은 [ 27 ]에서 설명한 것과 유사한 동적 계획법으로 계산할 수 있으며, 시간은 $$ 𝑂 (| 𝑄 | log |𝑄 |)이다. 그러면 각 테이블 𝑅 과 임의의 prefix range filter 𝜓 에 대해, prefix-sum 배열을 이용해 |( ⋈︁ 𝑅 ′ ∈𝑇 𝑅 𝑅 ′)⋈︁ 𝑅 |𝜓 | 를 $$ 𝑂 (log |𝑅 |)
시간에 효율적으로 계산할 수 있다. 이어서 |𝑅𝑒𝑠 (𝑄 𝑠 |𝜓 )| 는 𝑄 의 모든 𝑅 ∈ 𝑄 에 대한 이러한 기수를 사용해 $$ 𝑂 (1)시간에 계산할 수 있다. 이 방법은
898 질의별 전처리로 $$ 𝑂 (| 𝑄 | log |𝑄 |)
시간을 요구하지만, 실제로는 많은 질의에서, 특히 열거 초기 단계에서 열거 지연을 효과적으로 줄일 수 있다. 우리는 이 상한 알고리즘들을 각각 A (최소화된 AGM 기반)와 S (골격 기반)이라 부르고, Section 6에서 이들이 열거 가속에 얼마나 효과적인지 평가한다. ## 6 실험 이 절에서는 조인 질의를 위한 우리의 무작위 순서 열거 알고리즘과 최적화 기법들에 대한 실험 평가를 제시한다. Section 3에서 소개한 기본 무작위 순서 열거 알고리즘을 REnum 이라 부른다. 우리는 Section 5.1의 LTI 기법과 Section 5.2의 TU 기법을 각각 결합한 최적화된 REnum 변형들을 평가한다. 이 변형들은 통일되게 REnum X-Y 로 표기하며, 여기서 X ∈ { L, M, B} 는 기본 LIT, MTI 또는 BTI의 사용을 나타내고, 𝑌 ∈ { A, AS } 는 사용된 상한 알고리즘을 나타낸다. 별도 언급이 없으면, 모든 최적화된 REnum 변형은 RRATree 전체 캐싱으로 실행된다. ## 6.1 실험 설정 이제 실험 설정을 설명한다. 알고리즘. 우리는 두 조인 표본추출 알고리즘에서 파생된 표본추출 기반 방법들과 우리의 알고리즘을 비교한다: (1) PGMJoin [ 23 ]: 현재 구현된 기존 알고리즘 중 최신 상태이며(전처리 포함), 각 질의마다 Ω(| 𝑄 |) 시간 전처리를 요구한다. (2) NWCO [13 ]: 질의별 전처리 없이 이론적으로 거의 최악의 경우 최적인 조인 표본추출 알고리즘. 우리는 PGMJoin의 구현을 그들의 공개 저장소에서 사용했다. NWCO는 공개 구현이 없기 때문에 실험을 위해 직접 구현했다. 이 알고리즘들은 복원 추출로 균등 표본을 생성한다. 우리는 이미 본 중복 결과를 단순히 버리는 방식으로 이를 복원 없는 표본추출(SWOR) 과정에 맞게 변형했다. 그 결과 변형들을 각각 SWOR PGM 과 SWOR NWCO 라고 부른다. 데이터셋. 실험에서는 두 데이터셋을 사용한다: TPC-DS+ 와 Twitter . TPC-DS+는 표준 TPC-DS 벤치마크(scale factor 5)의 확장판으로, 소셜 네트워크의 팔로우 관계를 모델링하는 3 × 10 5 개 튜플의 고객-대-고객 관계 테이블을 추가한 것이다. 각 튜플의 source node는 균등하게 표본추출하고, target node는 정규분포에서 뽑는다. 생성된 팔로우 그래프는 상호 간선을 추가하여 무방향으로 취급한다. Twitter 는 twitter 사용자들의 팔로워 링크와 프로필을 포함한 실제 데이터셋으로, [ 10 , 23 , 27 ]에서도 사용되었으며, 여기서도 팔로우 그래프를 무방향으로 취급한다. 이 데이터셋들의 모든 관계 테이블은 메모리에 적재되며, 필요한 인덱스는 미리 구축된다. 질의. 우리는 세 가지 질의에 걸쳐 알고리즘과 최적화 기법을 평가한다. TPC-DS+ 데이터셋에서는 𝑄 𝐴 를 평가하는데, 이 질의는 소셜 네트워크에서 연결된 두 고객이 모두 구매한 2개의 상품과 함께 그 고객 쌍으로 이루어진 튜플을 반환한다. Twitter 데이터셋에서는 모든 삼각형( 𝑄 Δ)과 4-clique ( 𝑄 𝑆 )를 반환하는 질의를 평가한다. 전체 성능 평가 중 과도한 실행 시간을 피하기 위해, 노드 부분집합을 균등하게 표본추출하고, 그 유도 부분그래프에서 질의를 수행한다. 별도 언급이 없으면 𝑄 Δ 와 𝑄 𝑆 에 대해 각각 2M과 1M 노드를 사용한다. 이 질의들은 실용적 관련성(예: 소셜 네트워크 및 전자상거래 분석)뿐 아니라 구조적 대표성 때문에 선택되었는데, 이는 복잡한 순환 조인 질의의 핵심 구성 요소를 이루기 때문이다. SQL 문은 기술 보고서 [11]에 제공된다. 플랫폼 및 하드웨어. 모든 실험은 64-bit Ubuntu22.04 LTS가 실행되는 워크스테이션에서 수행되었으며, 하드웨어는 Intel Xeon E7-8860@2.2GHz 1개, 384GB DDR4 RAM, 2TB SSD를 갖추고 있다. ## 6.2 실험 결과 총 열거 시간. 알고리즘의 총 열거 시간을 특성화하기 위해, 이 질의들에 대해 SWOR PGM 및 SWOR NWCO 와 비교한다. 총 결과 크기의 1%에서 100%를 나타내는 𝑘 에 대해, 시작 시점부터 𝑘 번째 조인 결과가 열거된 직후까지의 경과 시간을 기록한다. 실험 결과는 질의별 차트로 Figure 4 (a)-(c)에 제시한다. SWOR NWCO 와 기본 REnum 은 조인 결과의 1%조차 생성하는 데 지나치게 오랜 시간이 걸리므로, 이들의 성능은 열거 초기 단계의 𝑄 Δ 에 대해서만 기록했으며, Figure 4 (d)에 제시한다. 결과는 가속 기법을 적용한 우리의 알고리즘이 SWOR PGM 과 SWOR NWCO 보다 현저히 우수함을 보여준다. 소거 연구로서 Figure 4(a)–(c)는 REnum B-AS 가 REnum M-AS 보다 더 빠르게 열거하고, 이는 다시 REnum L-AS 보다 우수하며, 이들 모두가 기본 알고-rithm REnum 을 크게 능가함을 보여준다. 이는 기본 LTI, MTI, BTI의 효과를 입증한다. 마찬가지로 REnum B 와 REnum B-AS 의 결과는 TU의 효과를 검증한다. 열거 초기 단계에서는, 첫 150개의 열거된 튜플의 총 열거 시간을 기록했으며, Figure 4 (d)에 제시했다. 주목할 점은 이러한 튜플들(SWOR NWCO 의 경우 제외)은 모두 SWOR PGM 이 전처리를 완료하고 첫 결과 튜플을 생성하기 전에 열거된다는 것이다. 결과는 많은 자명 구간을 발견하고 병합하는 데 따르는 오버헤드 때문에, MTI 또는 BTI 없이 우리의 알고리즘이 초기 단계에서는 더 빠르게 열거함을 보여준다. 열거 지연. 성능이 좋지 않기 때문에 SWOR NWCO 는 지연 분석에서 제외되었고, REnum 의 지연은 𝑄 Δ 의 열거 초기 단계(첫 150개 튜플)에서만 평가되었다. 각 결과 튜플의 열거 지연을 기록하고, 첫 5% 및 전체 결과( SWOR PGM 은 첫 5%만)에 대한 지연을 계산하여 지연 분포를 분석했으며, 그 결과는 Figure 5 (a)-(c)의 box plot으로 제시한다. 𝑄 Δ 의 초기 단계 지연은 Figure 5 (d)에 보인다. whisker 바깥의 outlier는 일부가 중앙값보다 여러 자릿수 더 크기 때문에 표시하지 않았다. 이 결과는 가속 기법을 적용한 우리의 알고리즘들의 열거 지연이 SWOR PGM 및 SWOR NWCO 보다 훨씬 작음을 보여준다. 또한 MTI와 BTI는 전체적인 열거 지연을 줄이는 반면, 자명 구간 발견과 병합의 오버헤드로 인해 초기 단계 지연은 증가시키는 경향이 있다. 반대로 TU는 주로 초기 단계의 열거 지연을 줄인다. 이러한 발견은 앞서 제시한 총 실행 시간에 관한 실험 결과와 일관된다. 공간 사용량. 우리 알고리즘의 메모리 효율을 평가하기 위해, Section 4.6에서 소개한 기법들을 구현하고 RRATree에서 캐시 계층 수를 제한하는 효과를 조사한다. 899 0 25 50 75 100 Enumerated Tuples (%) > 0 > 20 > 40 > 60 > 80 > 100 > Execution Time (s) > RE NUM > RE NUM L-A > RE NUM M-A > RE NUM B-A > RE NUM B > RE NUM B-AS > RE NUM M-AS > RE NUM L-AS > SWOR PGM > SWOR NWCO (a) 𝑄 𝐴 0 25 50 75 100 Enumerated Tuples (%) > 0 > 250 > 500 > 750 > 1000 > 1250 > Execution Time (s) (b) 𝑄 Δ0 25 50 75 100 Enumerated Tuples (%) > 0 > 500 > 1000 > 1500 > 2000 > 2500 > Execution Time (s) (c) 𝑄 𝑆 0 50 100 150 # Enumerated Tuples > 1.0 > 1.5 > 2.0 > 2.5 > 3.0 > Execution Time (s) 4.7 (OOR) 49.2 (OOR) (d) 𝑄 Δ (early stages) Figure 4: 총 열거 시간 5% > 0 > 10000 > 20000 > 30000 > 40000 > 50000 > 60000 > Enumeration Delay ( μs) > RE NUM > RE NUM L-A RE NUM M-A RE NUM B-A RE NUM BRE NUM B-AS RE NUM M-AS RE NUM L-AS SWOR PGM > 100% > 0 > 10 > 20 > 30 > 40 > 50 > 60 > 70 (a) 𝑄 𝐴 5% > 0 > 1000 > 2000 > 3000 > 4000 > 5000 > 6000 > Enumeration Delay ( μs)100% > 0 > 25 > 50 > 75 > 100 > 125 > 150 > 175 (b) 𝑄 Δ5% > 0 > 500 > 1000 > 1500 > 2000 > Enumeration Delay ( μs)100% > 0 > 20 > 40 > 60 > 80 > 100 > 120 > 140 (c) 𝑄 𝑆 150 tuples > 0 > 10000 > 20000 > 30000 > 40000 (d) 𝑄 Δ (early stages) Figure 5: 열거 지연 12 14 16 18 20 22 24 26 28 # Cached Layers > 0 > 10 > 20 > 30 > 40 > 50 > Execution Time (min) 5% (Time) > 100% (Time) > 5% (Space) > 100% (Space) > 0 > 5 > 10 > 15 > 20 > Memory Usage (GB) Figure 6: 시간-공간 절충 5% (Delay) 100% (Delay) 5% (Space) 100% (Space) > 025 50 75 100 125 > # Tuples ( ×10 6) > 0 > 20 > 40 > 60 > 80 > 100 > 120 > Average Delay ( μs) > 0246 > Memory Usage (GB) Figure 7: 확장성 구체적으로 캐시된 계층 수를 바꾸어 가며 𝑄 Δ 의 첫 5%와 전체 결과를 열거할 때의 메모리 사용량 2 과 실행 시간을 모두 측정한다. Figure 6은 공간 사용량과 실행 시간 사이에 명확한 절충 관계가 있음을 보여준다. 상위 몇 개 계층의 노드만 캐싱하는 것만으로도(예: 12–20 계층까지) 메모리 사용량을 크게 줄이면서 알고리즘 효율은 유지할 수 있으며, 특히 초기 단계(첫 5% )에서 그러하다. 주목할 점은 더 엄격한 메모리 제약 아래에서도 우리의 알고리즘이 표본추출 기반 방법을 능가한다는 것이다. 12개 계층을 캐싱했을 때, 5%와 100%의 𝑅𝑒𝑠 (𝑄 Δ) 를 각각 46MB와 1002MB 메모리로 열거한다. 반면 표본추출 기반 방법들은 중복 제거를 위해 unordered_set<vector> 에 튜플을 저장하는 데 적어도 84MB와 1690MB를 필요로 하며 실행도 훨씬 느리다. 이러한 결과는 우리의 알고리즘이 다양한 메모리 예산에 유연하게 적응할 수 있고, 높은 성능을 달성하기 위해 메모리를 효율적으로 사용함을 보여준다. 확장성. 또한 20개 계층을 캐싱한 상태에서 우리 알고리즘의 시간 및 공간 확장성을 평가한다. 구체적으로, 노드를 반복적으로 표본추출하고 그 유도 부분그래프를 추출하여 다양한 크기의 데이터셋을 생성한다. 이 데이터셋들에서 𝑄 Δ 를 실행하고 > 2 이 논문에서 보고하는 메모리 사용량은 열거 단계만을 고려한다. 인덱싱과 전처리에 필요한 공간은 포함하지 않는다. 첫 5%와 전체 결과 튜플을 열거할 때의 평균 지연과 메모리 사용량을 측정한다. Figure 7에서 보이듯, 평균 열거 지연은 데이터베이스 크기에 따라 로그적으로 증가한다. 공간 사용량은 데이터베이스 크기에 대해 대략 선형적으로 증가하지만, 일반적으로 데이터베이스 크기에 대해 초선형적으로 증가하는 총 결과 수의 증가보다는 훨씬 느리다. ## 7 결론 본 논문은 표본추출 기반 무작위 순서 열거가 이야기의 끝이 아님을 보여준다. 우리는 조인 질의에 대해 총 실행 시간에 대한 최악의 경우 보장을 갖는 보다 효율적인 무작위 순서 열거 알고리즘과, 열거를 가속하기 위한 두 가지 기법을 제시했다. 우리의 알고리즘은 효율적이고 유연하며, 조합적 𝑘 -clique 가설 하에서 큰 숨은 상수나 질의별 전처리 없이도 최악의 경우 거의 최적인 기댓값 지연과 총 실행 시간을 달성한다. 실험에서 최적화 기법을 적용한 우리의 알고리즘은 최신 표본추출 기반 방법들을 크게 능가했다. 이를 통해 데이터 분석 파이프라인 안에서 조인 결과를 무작위 순서로 더 빠르게 생성할 수 있다. 흥미로운 미래 연구 방향은 대규모 데이터 분석에서의 질의를 지원하기 위해 이러한 알고리즘을 외부 메모리 및 분산 데이터베이스 시스템에서 구현하고 추가 최적화하는 것이다. ## 8 감사의 글 익명의 리뷰어들의 소중한 제안에 감사드린다. 이 연구는 부분적으로 중국 헤이룽장성 자연과학재단 보조금 HSF20230095 및 2024ZXJ01A04, 중국 국가자연과학재단 보조금 62372138, 그리고 China Railway Rolling Stock Corporation의 지원을 받았다. 900 참고문헌 [1] Kaleb Alway, Eric Blais, and Semih Salihoglu. 2021. Box Covers and Domain Orderings for Beyond Worst-Case Join Processing. In 24th International Con-ference on Database Theory (ICDT 2021) (Leibniz International Proceedings in Informatics (LIPIcs)) , Ke Yi and Zhewei Wei (Eds.), Vol. 186. Schloss Dagstuhl – Leibniz-Zentrum für Informatik, Dagstuhl, Germany, 3:1–3:23. https://doi.org/ 10.4230/LIPIcs.ICDT.2021.3 [2] Albert Atserias, Martin Grohe, and Dániel Marx. 2013. Size Bounds and Query Plans for Relational Joins. SIAM J. Comput. 42, 4 (jan 2013), 1737–1767. https: //doi.org/10.1137/110859440 [3] Guillaume Bagan, Arnaud Durand, and Etienne Grandjean. 2007. On acyclic conjunctive queries and constant delay enumeration. In Proceedings of the 21st International Conference, and Proceedings of the 16th Annuall Conference on Com-puter Science Logic (Lausanne, Switzerland) (CSL’07/EACSL’07) . Springer-Verlag, Berlin, Heidelberg, 208–222. [4] Christoph Berkholz, Jens Keppeler, and Nicole Schweikardt. 2018. Answering UCQs under Updates and in the Presence of Integrity Constraints. In 21st In-ternational Conference on Database Theory (ICDT 2018) (Leibniz International Proceedings in Informatics (LIPIcs)) , Benny Kimelfeld and Yael Amsterdamer (Eds.), Vol. 98. Schloss Dagstuhl – Leibniz-Zentrum für Informatik, Dagstuhl, Germany, 8:1–8:19. https://doi.org/10.4230/LIPIcs.ICDT.2018.8 [5] Johann Brault-Baron. 2013. De la pertinence de l’énumération : complexité en logiques propositionnelle et du premier ordre . Theses. Université de Caen. https: //hal.science/tel-01081392 [6] Florent Capelli and Yann Strozecki. 2019. Incremental delay enumeration: Space and time. Discrete Applied Mathematics 268 (2019), 179–190. https://doi.org/10. 1016/j.dam.2018.06.038 [7] Nofar Carmeli and Markus Kröll. 2019. On the Enumeration Complexity of Unions of Conjunctive Queries. In Proceedings of the 38th ACM SIGMOD-SIGACT-SIGAI Symposium on Principles of Database Systems (Amsterdam, Netherlands) (PODS ’19) . Association for Computing Machinery, New York, NY, USA, 134–148. https://doi.org/10.1145/3294052.3319700 [8] Nofar Carmeli and Markus Kröll. 2020. Enumeration complexity of conjunctive queries with functional dependencies. Theory of Computing Systems 64, 5 (2020), 828–860. [9] Nofar Carmeli, Shai Zeevi, Christoph Berkholz, Alessio Conte, Benny Kimelfeld, and Nicole Schweikardt. 2022. Answering (Unions of) Conjunctive Queries using Random Access and Random-Order Enumeration. ACM Trans. Database Syst. 47, 3, Article 9 (Aug. 2022), 49 pages. https://doi.org/10.1145/3531055 [10] Meeyoung Cha, Hamed Haddadi, Fabricio Benevenuto, and Krishna Gummadi. 2010. Measuring User Influence in Twitter: The Million Follower Fallacy. Pro-ceedings of the International AAAI Conference on Web and Social Media 4, 1 (May 2010), 10–17. https://doi.org/10.1609/icwsm.v4i1.14033 [11] Pengyu Chen, Zizheng Guo, Jianwei Yang, and Dongjing Miao. 2025. Towards Efficient Random-Order Enumeration for Join Queries . Technical Report. Harbin Institute of Technology. https://github.com/Chen-Py/JoinREnum/blob/main/ TechnicalReport.pdf [12] Yu Chen and Ke Yi. 2020. Random Sampling and Size Estimation Over Cyclic Joins. In 23rd International Conference on Database Theory (ICDT 2020) (Leibniz Interna-tional Proceedings in Informatics (LIPIcs)) , Carsten Lutz and Jean Christoph Jung (Eds.), Vol. 155. Schloss Dagstuhl – Leibniz-Zentrum für Informatik, Dagstuhl, Germany, 7:1–7:18. https://doi.org/10.4230/LIPIcs.ICDT.2020.7 [13] Shiyuan Deng, Shangqi Lu, and Yufei Tao. 2023. On Join Sampling and the Hardness of Combinatorial Output-Sensitive Join Algorithms. In Proceedings of the 42nd ACM SIGMOD-SIGACT-SIGAI Symposium on Principles of Database Systems (Seattle, WA, USA) (PODS ’23) . Association for Computing Machinery, New York, NY, USA, 99–111. https://doi.org/10.1145/3584372.3588666 [14] Mahmoud Abo Khamis, Hung Q. Ngo, Xuanlong Nguyen, Dan Olteanu, and Maximilian Schleich. 2020. Learning Models over Relational Data Using Sparse Tensors and Functional Dependencies. ACM Trans. Database Syst. 45, 2, Article 7 (June 2020), 66 pages. https://doi.org/10.1145/3375661 [15] Mahmoud Abo Khamis, Hung Q. Ngo, Christopher Ré, and Atri Rudra. 2016. Joins via Geometric Resolutions: Worst Case and Beyond. ACM Trans. Database Syst. 41, 4, Article 22 (Nov. 2016), 45 pages. https://doi.org/10.1145/2967101 [16] Kyoungmin Kim, Jaehyun Ha, George Fletcher, and Wook-Shin Han. 2023. Guar-anteeing the Õ(AGM/OUT) Runtime for Uniform Sampling and Size Estima-tion over Joins. In Proceedings of the 42nd ACM SIGMOD-SIGACT-SIGAI Sym-posium on Principles of Database Systems (Seattle, WA, USA) (PODS ’23) . As-sociation for Computing Machinery, New York, NY, USA, 113–125. https: //doi.org/10.1145/3584372.3588676 [17] Benny Kimelfeld and Christopher Ré. 2018. A Relational Framework for Classifier Engineering. ACM Trans. Database Syst. 43, 3, Article 11 (Oct. 2018), 36 pages. https://doi.org/10.1145/3268931 [18] Gonzalo Navarro, Juan L. Reutter, and Javiel Rojas-Ledesma. 2020. Optimal Joins Using Compact Data Structures. In 23rd International Conference on Database Theory (ICDT 2020) (Leibniz International Proceedings in Informatics (LIPIcs)) ,Carsten Lutz and Jean Christoph Jung (Eds.), Vol. 155. Schloss Dagstuhl – Leibniz-Zentrum für Informatik, Dagstuhl, Germany, 21:1–21:21. https://doi.org/10.4230/ LIPIcs.ICDT.2020.21 [19] Hung Q. Ngo, Dung T. Nguyen, Christopher Re, and Atri Rudra. 2014. Beyond worst-case analysis for joins with minesweeper. In Proceedings of the 33rd ACM SIGMOD-SIGACT-SIGART Symposium on Principles of Database Systems (Snow-bird, Utah, USA) (PODS ’14) . Association for Computing Machinery, New York, NY, USA, 234–245. https://doi.org/10.1145/2594538.2594547 [20] Hung Q. Ngo, Ely Porat, Christopher Ré, and Atri Rudra. 2012. Worst-case optimal join algorithms: [extended abstract]. In Proceedings of the 31st ACM SIGMOD-SIGACT-SIGAI Symposium on Principles of Database Systems (Scottsdale, Arizona, USA) (PODS ’12) . Association for Computing Machinery, New York, NY, USA, 37–48. https://doi.org/10.1145/2213556.2213565 [21] Hung Q. Ngo, Ely Porat, Christopher Ré, and Atri Rudra. 2018. Worst-case Optimal Join Algorithms. J. ACM 65, 3, Article 16 (March 2018), 40 pages. https://doi.org/10.1145/3180143 [22] Hung Q Ngo, Christopher Ré, and Atri Rudra. 2014. Skew strikes back: new developments in the theory of join algorithms. SIGMOD Rec. 42, 4 (Feb. 2014), 5–16. https://doi.org/10.1145/2590989.2590991 [23] Ali Mohammadi Shanghooshabad, Meghdad Kurmanji, Qingzhi Ma, Michael Shekelyan, Mehrdad Almasi, and Peter Triantafillou. 2021. PGMJoins: Ran-dom Join Sampling with Graphical Models. In Proceedings of the 2021 Inter-national Conference on Management of Data (Virtual Event, China) (SIGMOD ’21) . Association for Computing Machinery, New York, NY, USA, 1610–1622. https://doi.org/10.1145/3448016.3457302 [24] W. Nick Street and YongSeog Kim. 2001. A Streaming Ensemble Algorithm (SEA) for Large-Scale Classification. In Proceedings of the Seventh ACM SIGKDD International Conference on Knowledge Discovery and Data Mining (San Francisco, California) (KDD ’01) . Association for Computing Machinery, New York, NY, USA, 377–382. https://doi.org/10.1145/502512.502568 [25] Todd L Veldhuizen. 2014. Leapfrog triejoin: A simple, worst-case optimal join algorithm. In Proc. International Conference on Database Theory .[26] Ru Wang and Yufei Tao. 2024. Join Sampling Under Acyclic Degree Constraints and (Cyclic) Subgraph Sampling. In 27th International Conference on Database Theory (ICDT 2024) (Leibniz International Proceedings in Informatics (LIPIcs)) ,Graham Cormode and Michael Shekelyan (Eds.), Vol. 290. Schloss Dagstuhl – Leibniz-Zentrum für Informatik, Dagstuhl, Germany, 23:1–23:20. https://doi. org/10.4230/LIPIcs.ICDT.2024.23 [27] Zhuoyue Zhao, Robert Christensen, Feifei Li, Xiao Hu, and Ke Yi. 2018. Random Sampling over Joins Revisited. In Proceedings of the 2018 International Conference on Management of Data (Houston, TX, USA) (SIGMOD ’18) . Association for Computing Machinery, New York, NY, USA, 1525–1539. https://doi.org/10.1145/ 3183713.3183739 901