DEIM Forum 2023 2a-2-2

埋め込み順序従属性の検証アルゴリズム
ラモスアレハンドロ†

天方

大地†

隆浩†

原

† 大阪大学 〒 560–0085 大阪府吹田市山田丘 1-5
E-mail: †{ramos.alejandro,amagata.daichi,hara}@ist.osaka-u.ac.jp
あらまし 順序従属性（order dependencies）は，クエリ最適化，データ統合，およびデータクリーニング等の重要な応用例がある．多くの研究が順序従属性を発見する効率的なアルゴリズムを提案しているが，実世界データに通常現れる NULL に対応している順序従属性に関する研究は行われていない．本論文では，NULL がある場合の順序従属性に対応する，埋め込み順序従属性を新たに定義し，埋め込み順序従属性を検証する効率的なアルゴリズムを提案する．
実世界データを用いた実験を行い，提案アルゴリズムの有効性を示す．
キーワード 埋め込み順序従属性, 不完全データ，関係データベース
表 1: 社員リスト

1 はじめに
1. 1 動ID Rank Years Age Salary機

整合性制約は，データプロファイル，データクリーニング，ク
エリ最適化，およびスキーマデザイン等の関係データベースで用いられる機能における基本である [1–3,6,15,16,20,22]．整合

t1

1

1

20

15000

t2

2

1

⊥

20000

t3

3

2

22

25000

t4

4

3

25

30000

t5

5

4

30

35000

性制約の中でも，関数従属性 [4] および順序従属性 [7, 19] は最も重要な制約である．関数従属性とは，ある属性の値が決まると，ある別の属性の値も自ずと決まる制約である．つまり，関数従属性 X → Y は，属性の集合 X において各属性の値が決まると，Y における各属性の値が決まる．同様に，順序従属性
は，ある属性の順序（sort order）が決まると，ある別の属性の順序も自ずと決まる制約である．例えば，順序従属性 X 7→ Y
は，X における全ての値が昇（降）順でソートされている時，Y も同様に（昇順または降順で）ソートされる．関数従属性は
順序従属性の特別な場合に相当する [19, 20] ため，本論文では
順序従属性について考える．
順序従属性は特にクエリ最適化，制約違反検出，およびデー
タリペアに用いられており，これまでに順序従属性の発見に関する多くの研究が行われている [5, 10, 12, 17, 23]．また，エラーを含むデータに対応するため，順序従属性の亜種に関してもいくつかの提案がなされている [9, 11, 13, 14]．しかし，実世
界データにおいて NULL（missing value）を含むデータは一

表 1 において， 順序従属性 Rank 7→ Salary （Salary in-creases as Rank increases）を満たすか確認したとき，これは有効であることが分かる．しかし，既存の順序従属性において，Age 7→ Salary は有効でなく，これは t2 が NULL（⊥）を含
むためである．ここで，NULL を含まないデータのみを考えた
時（t2 を除外した場合），Age 7→ Salary は成り立つ．同様に，

Y ears 7→ Salary も既存の順序従属性は満たさないが，NULLを考慮すると成り立つ．この例から分かるように，埋め込みを利用することによって（既存の順序従属性の定義では見つからない）意味的に有効な順序従属性を発見できる．そのため，本研究では属性のリストのペアおよび埋め込み属性の集合が与えられた時に，この埋め込み順序従属性が成り立つかを計算し，成り立たない場合はその順序従属性が成り立つ埋め込み属性の集合を計算する問題に取り組む．

1. 2 課題

般的にも関わらず，このようなデータに対応する順序従属性に既存のアルゴリズムを用いれば，ある属性のリストのペアに関する研究は行われていない．そこで本研究では，NULL を含よる順序従属性が成り立つかを計算することは容易である．しむデータに対応する順序従属性について考え，埋め込み関数従かし，この順序従属性が成り立たない場合に，これを成り立た

属性（embedded functional dependencies）[21, 22] で提案させる埋め込み属性の集合を計算するのは自明ではない．素朴なれている概念を取り入れる．この概念は，埋め込み属性というアルゴリズムとして，属性のペアを順に列挙して，この埋め込アイデアを用いており，埋め込み属性において NULL がない

み上で順序従属性が成り立つか計算することを繰り返すものがデータだけを制約の対象にする（NULL を含むデータを無視す考えられる．しかし，このアルゴリズムは属性数に対して階乗る）．この概念を取り入れることにより，既存の順序従属性でのコストがかかり，大規模なリレーショナルテーブルにスケーは発見できないが意味的に有効な順序従属性を発見できる可能

ルしない．例えばクエリ最適化において埋め込み順序従属性を性がある．また，この方法で発見した順序従属性も整合性・完利用する際，上記のアルゴリズムを用いると埋め込みの計算が全性制約の定義に利用可能である．

ボトルネックとなり，クエリ最適化に対するゲインが失われる．

そのため，本問題を解くための高速アルゴリズムが重要となる．

1. 3 貢表 2: split，merge，および swap の例

献

本研究では，上記の課題を解決する効率的なアルゴリズムを提案する．有効な埋め込みを計算するには，順序従属性に反するタプルが NULL の属性を持っているかどうかに注目すれば

id A B

C

D

t1

1

3

1

2

t2

2

7

1

3

t3

3

4

3

4

t4

4

5

5

5

よく，そのような属性を埋め込みに加えることで，順序従属性に反するタプルを無視できる．このアイデアを利用することにより，属性数に対する階乗の計算コストを取り除く．本研究の入力：

貢献は以下の通りである．

か検証し，

E : X 7→<
Y が与えられた時，これが真である=

埋め込み順序従属性を提案する．この概念はこれまでに

出力： 真であれば，valid を返す．偽であれば，以下の提案されていない．また，本研究では，与えられた属性のリス

二つのいずれかを返す：(1) E′ : X 7→<
Y が真である E′=•トのペアおよび埋め込みがに対して順序従属性が成り立つか検証する問題に取り組む．

•

本問題に対して，行（タプル）数および列（属性）数に対する多項式時間アルゴリズムを提案する．

•

実世界データを用いて実験し，提案アルゴリズムの有効が存在する場合，valid with E′ を返す．(2) 存在しない
場合，not valid を返す．


上記の問題を解くにあたり，split ，swap [19]，および merge[12] と呼ばれる概念を紹介する．これらは，順序従属性が成り性を確認する．

立たない時のタプルのペアの関係性を定義したものである．

構成．以降では，2 章で問題を定義し，提案アルゴリズムを 3

定義 3. Split. s, t ∈ r および A, B ∈ R において，sA = tA

章で紹介する．4 章で実験結果を報告し，5 章で関連研究を紹だが sB =
| tB の場合，split していると呼ぶ．

介する．最後に，6 章で本論文をまとめる．

2 予備知識2. 1 定義

R をリレーショナルスキーマとし，r をリレーショナルデー
タベースのインスタンス（テーブル）とする．A および B を

定義 4. Merge. s, t ∈ r および A, B ∈ R において，sA =| tA
だが sB = tB の場合，merge していると呼ぶ．
定義 5. Swap. s, t ∈ r および A, B ∈ R において，sA < tA
だが sB > tB の場合，swap していると呼ぶ．
表 2 において，split，merge，および swap の例を紹介する．

R の一つの属性とし，X および Y を属性のリストとする．ま

例 1. A 7→<
B において，t2 および t3 は t3A > t2A だが=

た，s および t を r におけるタプル（行）とし，sA を s におけt3B < t2B であるため，swap している．A 7→< C において，t1

る属性 A の値とする．理解を容易にするため，まず順序従属性

および t2 は t2A > t1A だが t2C = t1C であるため，merge しを定義する．

ている．また，C 7→<
D において，t1 および t2 は t2C = t1C=

定義 1. 順序従属性 [19]．任意の s, t ∈ r に対して，sX <=tX ⇒ s Y <Y は成り立つ= tY であるとき，順序従属性 X 7→<=（X, Y ∈ R である）．
ここで，E を R の部分集合とし，埋め込みと呼ぶ．このとき，rE ∈ r は，r において E に NULL が無いタプルの集合を表す．次に，埋め込み順序従属性を定義する．

だが t2D > t1D であるため，split している．
上の定義から，（A, B ）上の split は，（B, A）上の merge に相当する（逆も成り立つ）．また，split は “<=” による演算での概念，merge は “<” による演算での概念，さらに，swap はどちらの演算でも用いられる概念である．この観測に基づき，“<=”および “<” における埋め込み順序従属性がどのような場合において成り立つか紹介する．以下の（補助）定理は，文献 [12]定義 2. 埋め込み順序従属性．任意の s, t ∈ rE に対して，で紹介された順序従属性における性質を埋め込み順序従属性に

sX <= tY で あ る と き ，埋 め 込 み 順 序 従 属 性= tX ⇒ s Y <E : X 7→<Yは成り立つ（X, Y ∈ E ⊆ R である）．
=

適応したものである．

2. 2 問 題 定 義

い場合に真である．

本論文では，以下の問題を解く．

補助定理 1. E : A 7→<
B は，A, B で split および swap が無=補助定理 2. E : A 7→< B は，A, B で merge および swap が無い場合に真である．
定理 1. E : A 7→< B は真である．⇔ E : B 7→<
A は真である．
=
この定理から，“<” の場合の検証を行うだけで良いことが分かる．

表 3: ValidEOD におけるメインアイデア（例 2 および 3）

Algorithm 1: Naı̈ve
Input: E : A 7→<
B=

id A B

C

D

F

G

H

1

S←∅

/* tuples that cause swaps */

t1

4

1

1

8

20

10

1

2

M←∅

/* tuples that cause merges */

t2

6

2

3

30

⊥

2

S, M ← FindErrors(S, M, A, B)

⊥

3

5

3

5

10

⊥

50

3

4

S, M ← CheckForErrorDeletion(S, M, E)

t3

7

4

5

12 40 100⊥

5

if (S = ∅) ∧ (M = ∅) thent4

6

return valid/* no swaps or merges */Algorithm 2: ValidEOD′′
7 for ∀E ∈ R such that E ⊂ E do
8

S′ ← ∅, M′ ← ∅9S′ , M′ ← FindErrors(S′ , M′ , A, B)

10S′ , M′ ← CheckForErrorDeletion(S′ , M′ , E′ )11

if (S′ = ∅) ∧ (M′ = ∅) thenreturn E′

1213return not valid

Input: E : A 7→<
B
=
1

S←∅

/* tuples that cause swaps */2

M←∅/* tuples that cause merges */3

N ← GetMissingValueColumns

4

S, M ← FindErrors(S, M, A, B)

5

S, M ← CheckForErrorDeletion(S, M, E)

6

if (S = ∅) ∧ (M = ∅) then

78

2. 3 素朴なアルゴリズム

9

return valid
else
return UpdateEmbedding(E, S, M, N)

ここで，本問題を解く素朴なアルゴリズム（Algorithm 1）を考える．定理 1 から，E : A 7→<
B が与えられた時，E : B 7→< A=
を検証すれば良い（“<” の際のエラーチェックの方が計算が容易である）．素朴なアルゴリズムは以下のステップで構成されている．
（ 1 ） B 7→< A に対する swap および merge を計算する．
（ 2 ） これらのエラーが rE で消える場合，valid を返す．
（ 3 ） 消えない場合，E ⊂ E′ である全ての E′ ∈ R に対して上のステップを繰り返す．E′ : B 7→ A が真の場合，E′ を返す．
（ 4 ） 上のような E′ が存在しなかった場合，not valid を返す．
このアルゴリズムは本問題を正確に解くが，E′ が存在しない
場合に，属性数に対して階乗の計算コストが発生する．そのため，本問題を効率的に解くアルゴリズムを設計する必要がある．

め，AB : B 7→< A は偽であり，AB : A 7→<
B も偽である．そ=のため，この順序従属性が成り立つ埋め込み E′ ⊃ E について，

NULL を持つ属性に着目すると，t2 .D =⊥ である．属性 D を埋め込み AB に加えれば，t2 が無視されるため，ABD : B 7→< Aが成り立つ．そのため，埋め込みを列挙することなく ABD を返すことができる．
例 3. 次に，CB : C 7→<
B ，つまり，CB : B 7→< C について=考える．このとき，t3 , t4 に merge があるため，CB : B 7→< C
は成り立たない．上の例と同様に，F を埋め込み CB に加えると，

t3 が無視される，つまり merge が消えるため，CBF : B 7→< Cが成り立つ．これにより，全ての埋め込みを列挙することなく，

C 7→<
B が成り立つ埋め込み（CBF ）を計算できる．
=
概要．ValidEOD は 2 フェーズにより構成されている．1 フェー
ズ目で与えられた埋め込み順序従属性が真か検証する．偽の場

3 提案アルゴリズム
本章では提案アルゴリズムである ValidEOD（Algorithm2）を紹介する．
メインアイデア．E : A 7→< B について考える．これが成り立たない場合，素朴なアルゴリズムは E ⊂ E′ である全てのE′ ∈ R を列挙しようとする．しかし，この順序従属性に反する swap または merge を起こしているタプルのペアが NULLを持っているかに着目すれば，考慮する必要がある属性のみを埋め込みに追加できる．
（例えば，これらのタプルが NULL を持っていない場合，いかなる E′ ⊃ E でも E′ : A 7→< B は成り立たない．
）このアイデアにより，属性数に対して線形時間のみ必要なアルゴリズムを設計できる．以下で，このアイデアの具体例を表 3 を用いて示す．
例 2. AB : A 7→<
B について考える．定理 1 から，AB :=B 7→< A を検証する，表 3 において，t2 , t3 が swap しているた合，順序従属性が真となる埋め込みが存在するか計算する．

3. 1 埋め込み順序従属性の検証ある埋め込み順序従属性が与えられた際，ValidEOD は以下によりこれが真であるか計算する．まず，NULL が含まれる属性の集合 N を計算する．次に，全ての swap と merge
を FindErrors [12] で計算し，それらをそれぞれリスト S
および M で管理する．
（FindErrors は行数に対して線形時間しか必要としない．
）その後，CheckForErrorDele-tion でこれらのエラーが埋め込み E 上で消えるか計算する．
（CheckForErrorDeletion の時間は |S| および |M| に対して線形である．
）エラーが無い場合，valid を返す．エラーが存在する場合，次のフェーズに進む．

3. 2 埋め込みの更新
次に，ValidEOD は UpdateEmbedding（Algorithm 3）
により E′ : A 7→<
B が成り立つ E′ ⊃ E を探す．メインアイ=

表 4: 各データの行数および列数

Algorithm 3: UpdateEmbedding
Input: E: a given embedding, S: a list of tuples thatデータ

cause swaps, M: a list of tuples that cause merges,
and N: a set of attributes with missing values.
1E′ ← E2for each s ∈ S do

3

for each A ∈ N do

4

F ← E′ + A

5

if s is removed on rF then

行（データ）数 列（属性）数

China Weather

262,000

18Adult

32,00015

Hepatitis

155

20

Echocardiogram

132

13

NCVoter

256,00019

6E′ ← Fに O(n2 ) である．そのため，ValidEOD の時間計算量は，

7

S←S−s

O(|N|n2 ) である．これにより，ValidEOD の時間計算量は

8

break

属性数に対して線形であり，素朴なアルゴリズムのような

9

if s ∈ S then

階乗コストは発生しないことが分かる．
（また，実践的にはreturn not valid

10

11

for each m ∈ M do

12

for each A ∈ N do

13

F ← E′ + A

14

if m is removed on rF then15E′ ← F

16

M←M−m

17

break

18

if m ∈ M thenreturn not valid

19′
20 return valid under E

デアで述べたように，swap または merge が起きているタプル
が NULL となる属性を持っているかだけ確認すれば良い．
（も|S| + |M|  O(n2 ) である．
）

4 実

験

本章では評価実験の結果を報告する．全ての実験は，Ubuntu

20.04.5 を搭載した Intel Core i9-12900@2.4GHz および 64GB
RAM の計算機を用いて行った．
4. 1 設定

データ．本実験では，以下の実データ 1 2 を用いた．

•

China Weather：中国における気象データ．

•

Adult：アメリカ合衆国における国勢調査データ．

•

Hepatitis: 肝炎患者に関するデータ.

•

Echocardiogram：心発作を起こした患者に関する分類

データ．

•

しそのような属性がなければ，順序従属性は成り立たない．
）こ

NCVoter：North Carolina 州の投票者の個人データ．

のアイデアを用いて，swap および merge が消えるように埋めアルゴリズム．本実験では，Algorithm 2 を Algorithm 1 と込み E を更新する．UpdateEmbedding は以下の手順で E を比較した．これらのアルゴリズムはシングルスレッドであり，更新する：

C++で実装され，g++ 9.4.0 および-O3 による最適化でコンパイルされている．

（ 1 ） 各 swap s ∈ S に対して，N に含まれる属性が s を消せ
るか確認する．消せるならば，該当の属性を E′ （初期はE）に追加し，s を S から取り除く．これを N に含まれる全ての属性に対してテストしても s が消えないならば，S=| ∅ である．この時，UpdateEmbedding は not validを返す．

パラメータ．性能評価のため，LHS および RHS のサイズを変えて実験を行った．X 7→<
Y において，X（Y ）が LHS=（RHS）である．デフォルトの LHS および RHS のサイズは 1とし，LHS と RHS は属性集合からランダムにサンプルした属性によるリストである．
各実験は，ランダムに作成した LHS と RHS 上でのアルゴ（ 2 ） 上のステップで not valid を返していなければ，同様の操作を各 merge m ∈ M に対して行う．
（ 3 ） 上のステップでエラーが消えれば，UpdateEmbedding
は valid with E′ を返す．

3. 3 分析

リズムの実行を 10 回繰り返している．実行時間はその平均である．

4. 2 結果

図 1 は，提案アルゴリズム（Algorithm 2）および素朴な（Naı̈ve）アルゴリズム（Algorithm 1）の各 LHS（RHS）のサ
イズに対する実行時間の平均と中央値を表している．また，

空間計算量．ValidEOD の空間計算量は，O(|S| + |M| + |N|)

China Weather および NCVoter において，素朴なアルゴリズ

である．

ムは 10 回の繰り返しに 2 時間以上要したため，実験を中断し，時間計算量．1 フェーズ目の計算量は，O(n + |S| + |M|) で
あ り，n は rE の 行 数 で あ る ．2 フェー ズ 目 の 計 算 量 は ，1：https://www.ncsbe.gov/

O(|N|(|S| + |M|)) である. また，|S| + |M| は最悪の場合

2：https://archive.ics.uci.edu/

(a) China Weather(b) Adult(c) Echocardiogram(d) Hepatitis(e) NCVoter

図 1: LHS および RHS のサイズの影響

結果を割愛している．

関係はない．図 2 に，|S| および |M| の平均を示す．図 1 におまず，提案アルゴリズムは素朴なアルゴリズムよりも何百倍ける提案アルゴリズムの平均実行時間と比較すると，|S| + |M|

以上も早いことが分かる．本実験で用いたデータは 10 以上のと提案アルゴリズムの平均実行時間は相関しており，理論分析

属性を持っているため，この数に対する階乗コストは非常に大通りの挙動であることが分かる．

きい．そのため，素朴なアルゴリズムは実行時間が膨大となるが，提案アルゴリズムには影響が小さい．

最 後 に ，い く つ か の デ ー タ（ 例 え ば China Weather やNCVoter）において，実行時間の平均と中央値に乖離があるこ

また，提案アルゴリズムは LHS（RHS）のサイズに対してとが分かる．これは，いくつかの LHS および RHS にペアは，線形な影響がないことも分かる．これは，3. 3 節における分析

大量の swap および merge を発生していることを示しており，から自明であり，LHS（RHS）のサイズと |S| + |M| に線形な

このようなペアによって平均時間が長くなる．中央値の結果に

(a) China Weather(b) Adult(d) Hepatitis(c) Echocardiogram(e) NCVoter

図 2: |S| および |M| の平均

着目すると，先述のようなペアとなる確率は高くなく，提案ア

換させることにより，属性数に対する最悪時間を階乗から指数ルゴリズムが高速に解を返す場合が多いことも分かる．

時間に削減できることを示した．
順序従属性は NULL の無いデータに対して有効であるが，5 関連研究
順序従属性という概念は，文献 [7] によって提唱され，順序従属性の計算複雑性について議論されている．文献 [19, 20] では，理論的な複雑性が証明されており，順序従属性の公理が示されている．また，順序従属性が関数従属性を包含していることも示された．

5. 1 厳密な順序従属性
文献 [12] では，与えられた関係表で成り立つ全ての順序従属性を列挙するアルゴリズムである ORDER が提案されている．

ORDER はいつくかのフィルタリング技術が組み込まれている
ものの，属性数に対して階乗のコストが生じる．文献 [17] は，
特定のソート方法における順序従属性を集合に基づく表現に変NULL が一つでも含まれるデータには使えず，潜在的な順序従属性を発見できない．
（埋め込み順序従属性はこれを見つける可能性を残している．
）また，順序従属性は埋め込み順序従属性のスペシャルケースであり，埋め込みが全属性の場合であることを記す．

5. 2 近似順序従属性
文献 [17, 18] では，近似順序従属性が提案されている．これは，いくつかの（順序従属性に反している）タプルのペアを除く場合に成り立つ順序従属性を計算する問題である．しかし，この問題は行数および列数に対して大きな計算コストがかかることが示されている．文献 [8, 9, 11] で，この課題に対応する
ヒューリスティックアルゴリズムが提案されている．
上記の研究において，全てのデータに NULL がないことを

想定しており，NULL がある場合の近似順序従属性は定義されていない．そのため，近似順序従属性は完全性制約に対応できないという欠点がある．

5. 3 埋め込み関数従属性
NULL ありデータに対応する関数従属性である埋め込み関数
従属性は，文献 [22] で提案された．また，文献 [21] において，埋め込み関数従属性を満たす属性集合のペアを高速に計算する
アルゴリズムが提案されている．埋め込み関数従属性も完全性
制約や整合性制約に使えるが，順序従属性には対応できない．
上記の通り，順序従属性は関数従属性を包含しており，埋め込
み順序従属性も埋め込み関数従属性を包含していることは自明である．

6 ま と め
本論文では，埋め込み順序従属性という新しい概念を提案し，

NULL ありデータに対する順序従属性，統合性，および完全性への対応を実現した．また，与えられた属性のリストのペア
および埋め込みが成り立つか検証する問題に取り組み，これを効率的に解くアルゴリズムを提案した．提案アルゴリズムは，
データ数および属性数に対して多項式時間で動作することを示した．実世界データを用いた実験により，提案アルゴリズムの有効性を示した．

謝辞

本 研 究 の 一 部 は ，JST さ き が け（JPMJPR1931），JST

CREST（JPMJCR21F2），および文部科学省科学研究費補助金・基盤研究 (A)(18H04095) の支援を受けたものである．
文

献[1] S. Abiteboul, R. Hull, and V. Vianu, Foundations of
databases, vol.8, 1995.
[2] P. Bohannon, W. Fan, F. Geerts, X. Jia, and A. Kementsietsidis, “Conditional functional dependencies for data cleaning,” In ICDE, pp.746–755, 2006.
[3] Q. Cheng, J. Gryz, F. Koo, T.C. Leung, L. Liu, X. Qian,
and B. Schiefer, “Implementation of two semantic query optimization techniques in db2 universal database,” In VLDB,
vol.99, pp.687–698, 1999.
[4] E.F. Codd, “Further normalization of the data base relational model,” Data base systems, vol.6, pp.33–64, 1972.
[5] C. Consonni, P. Sottovia, A. Montresor, Y. Velegrakis,
Z. Kaoudi, H. Galhardas, I. Fundulaki, B. Reinwald,
M. Herschel, C. Binnig, et al., “Discovering order dependencies through order compatibility,” In EDBT, 2019.
[6] W. Fan, F. Geerts, X. Jia, and A. Kementsietsidis, “Conditional functional dependencies for capturing data inconsistencies,” ACM Transactions on Database Systems, vol.33,
no.2, pp.1–48, 2008.
[7] S. Ginsburg and R. Hull, “Order dependency in the relational model,” Theoretical computer science, vol.26, no.1-2,
pp.149–195, 1983.
[8] Y. Jin, Z. Tan, J. Chen, and S. Ma, “Discovery of approximate lexicographical order dependencies,” IEEE Transactions on Knowledge and Data Engineering, 2021.
[9] Y. Jin, Z. Tan, W. Zeng, and S. Ma, “Approximate orderdependency discovery,” In ICDE, pp.25–36, 2021.

[10] Y. Jin, L. Zhu, and Z. Tan, “Eﬃcient bidirectional orderdependency discovery,” In ICDE, pp.61–72, 2020.
[11] R. Karegar, P. Godfrey, L. Golab, M. Kargar, D. Srivastava,
and J. Szlichta, “Eﬃcient discovery of approximate orderdependencies,” arXiv preprint arXiv:2101.02174, 2021.
[12] P. Langer and F. Naumann, “Eﬃcient order dependency
detection,” The VLDB Journal, vol.25, no.2, pp.223–241,
2016.
[13] P. Li, J. Szlichta, M. Bohlen, and D. Srivastava, “Discovering band order dependencies,” In ICDE, pp.1878–1881,
2020.
[14] P. Li, J. Szlichta, M. Böhlen, and D. Srivastava, “Abcof order dependencies,” The VLDB Journal, vol.31, no.5,
pp.825–849, 2022.
[15] F. Naumann, “Data proﬁling revisited,” ACM SIGMOD
Record, vol.42, no.4, pp.40–49, 2014.
[16] D. Simmen, E. Shekita, and T. Malkemus, “Fundamental
techniques for order optimization,” In SIGMOD, pp.57–67,
1996.
[17] J. Szlichta, P. Godfrey, L. Golab, M. Kargar, and D. Srivastava, “Eﬀective and complete discovery of order dependencies via set-based axiomatization,” arXiv preprint
arXiv:1608.06169, 2016.
[18] J. Szlichta, P. Godfrey, L. Golab, M. Kargar, and D. Srivastava, “Eﬀective and complete discovery of bidirectional
order dependencies via set-based axioms,” The VLDB Journal, vol.27, no.4, pp.573–591, 2018.
[19] J. Szlichta, P. Godfrey, and J. Gryz, “Fundamentals of order dependencies,” Proceedings of the VLDB Endowment,
vol.5, no.11, pp.1220–1231, 2012.
[20] J. Szlichta, P. Godfrey, J. Gryz, and C. Zuzarte, “Expressiveness and complexity of order dependencies,” Proceedings of the VLDB Endowment, vol.6, no.14, pp.1858–1869,
2013.
[21] Z. Wei, S. Hartmann, and S. Link, “Algorithms for the discovery of embedded functional dependencies,” The VLDB
Journal, vol.30, no.6, pp.1069–1093, 2021.
[22] Z. Wei and S. Link, “Embedded functional dependencies
and data-completeness tailored database design,” Proceedings of the VLDB Endowment, vol.12, no.11, pp.1458–1470,
2019.
[23] L. Zhu, X. Sun, Z. Tan, K. Yang, W. Yang, X. Zhou, andY. Tian, “Incremental discovery of order dependencies ontuple insertions,” In DASFAA, pp.157–174, 2019.