RDBおける候補キーを求めるためのアルゴリズム

RDBにおける候補キーを  求めるためのアルゴリズム 

© 2022 for LANCERS, Inc. All Rights Reserved 2 2
久保路（くぼあゆむ）・ 2020.04 ~ 2021.12 BIチームに所属しSalesforce管理・開発・ 2022.01~ 現在 QAチームに所属しCakePHP２→４への　バージョンアッププロジェクトに参画中・クエリチューニングをきっかけに　RDBの勉強にハマる・クラフトビールが好き

今日持ち帰っていただきたいこと・候補キーとは一体何か・候補キーを見つけることはなぜ重要なのか・候補キーを求めるためのアルゴリズムはどのようなものか・なんか面白そうという気持ち

1 RDBにおける用語の整理 2 候補キーを求めるためのアルゴリズム 3 アルゴリズムの例 4 最後にアジェンダ

RDBにおける用語の整理 

© 2022 for LANCERS, Inc. All Rights Reserved 6 •
いくつかの集合の組み合わせ(の部分集合)を指す • 例名前の集合 D_1 = {太郎,花子,二郎}, 年齢の集合 D_2 = {20,25} の組み合わせから R = { (太郎,20), (花子,25), (二郎,20) }のようなリレーションができる • リレーションは表として実現することができるリレーションとは

例 ◦ D_1 = {太郎,花子,二郎}, D_2 = {20,25} の組み合わせから R = { (太郎,20), (花子,25), (二郎,20) }のようなリレーションができるリレーションとは名前年齢太郎 20 花子 25 二郎 20

例 ◦ D_1 = {太郎,花子,二郎}, D_2 = {20,25} の組み合わせから R = { (太郎,20), (花子,25), (二郎,20) }のようなリレーションができるリレーションとは名前年齢太郎 20 花子 25 二郎 20 列 / カラム

例 ◦ D_1 = {太郎,花子,二郎}, D_2 = {20,25} の組み合わせから R = { (太郎,20), (花子,25), (二郎,20) }のようなリレーションができるリレーションとは名前年齢太郎 20 花子 25 二郎 20 行 / タプル

例 ◦ D_1 = {太郎,花子,二郎}, D_2 = {20,25} の組み合わせから R = { (太郎,20), (花子,25), (二郎,20) }のようなリレーションができるリレーションとは名前年齢太郎 20 花子 25 二郎 20 属性名

リレーションの属性名の集合Kが候補キーであるとは次を満たすこと ◦ リレーションの任意の行 t と sに対して tのKの値とsのKの値が一致すれば、tとsは完全一致する ◦ Kの自身を除く部分集合に対しては、上記は成り立たない候補キーとは

リレーションの属性名の集合Kが候補キーであるとは次を満たすこと ◦ リレーションの任意の行 t と sに対して tのKの値とsのKの値が一致すれば、tとsは完全一致する → Kの値さえ決まれば、行が一意に定まる ◦ Kの自身を除く部分集合に対しては、上記は成り立たない → Kを分解してしまうと、行を一意に識別できなくなってしまう候補キーとは

© 2022 for LANCERS, Inc. All Rights Reserved 13 「日本人」というリレーション
を考えてみよう

© 2022 for LANCERS, Inc. All Rights Reserved 16 姓名
年齢生年月日住所個人番号星座性別郵便番号

© 2022 for LANCERS, Inc. All Rights Reserved 17 個人番号
姓名年齢住所生年月日性別郵便番号星座 00001 山田太郎 26 東京都墨田区押上１丁目１−２ 1996/01/01 男 1310045 山羊座 00002 田中花子 22 東京都港区芝公園４丁目２−８ 2000/01/01 女 1050011 山羊座各ドメインを組み合わせてリレーション「日本人」が作れる

年齢生年月日住所個人番号性別星座郵便番号

年齢生年月日住所個人番号性別行を特定できる＝候補キー

年齢住所星座性別郵便番号郵便番号を特定するのは住所だけで十分

年齢住所星座性別郵便番号郵便番号を特定するのは住所だけで十分 →郵便番号はこのリレーション　でわざわざ持つ必要がない

年齢住所星座性別郵便番号郵便番号を特定するのは住所だけで十分 →郵便番号はこのリレーション　でわざわざ持つ必要がない →別のリレーションに　情報を持たせる（正規化）

候補キーは行を一意に特定するキー • 正規化する上で候補キーを主軸に考慮する必要がある • そのため、候補キーが何であるかを特定することは重要

候補キーを求めるための  アルゴリズム 

リレーションの属性名の集合A,Bに対して関数従属性A→Bが存在するとは次を満たすことをいう ◦ リレーションの任意の行 t と sに対して tのAの値とsのAの値が一致すれば、 tのBの値とsのBの値が一致する関数従属性とは

リレーションの属性名の集合A,Bに対して関数従属性A→Bが存在するとは次を満たすことをいう ◦ リレーションの任意の行 t と sに対して tのAの値とsのAの値が一致すれば、 tのBの値とsのBの値が一致する → Aの値が決まれば、Bの値が一意に定まる関数従属性とは

リレーションの属性名の集合Xの閉包X+とは次のような集合である ◦ Xが決定項となる全ての関数従属性の被決定項からなる属性名の集合属性集合の閉包とは

リレーションの属性名の集合Xの閉包X+とは次のような集合である ◦ Xが決定項となる全ての関数従属性の被決定項からなる属性名の集合 → Xを決めれば一意に定まる全ての属性名の集合属性集合の閉包とは

年齢生年月日住所個人番号星座性別郵便番号 X

年齢生年月日住所個人番号星座性別郵便番号 X+

年齢生年月日住所個人番号星座性別郵便番号 X

年齢生年月日住所個人番号星座性別郵便番号 X+

© 2022 for LANCERS, Inc. All Rights Reserved 40 ここで候補キーを閉包を使った
書き方に直してみる

リレーションの属性名の集合Kが候補キーであるとは次を満たすこと ◦ K+ が全ての属性の集合と一致する → Kの値さえ決まれば、行が一意に定まる ◦ Kの自身を除く部分集合に対しては、上記は成り立たない → Kを分解してしまうと、行を一意に識別できなくなってしまう候補キーとは (閉包を用いた言い方)

© 2022 for LANCERS, Inc. All Rights Reserved 42 お待たせしました
アルゴリズムを紹介します

© 2022 for LANCERS, Inc. All Rights Reserved 43 1.
K を属性全体の集合とおく 2. Kの各属性Aに対して以下を実行する {K - A}+が属性全体の集合となればK を K - A で置き換えるそうでなければ、Kをそのままとする 3. 最終的に残ったKが候補キーとなる候補キーを１つ求めるためのアルゴリズム

アルゴリズムの例 

住所が分かれば、郵便番号が分かる • 生年月日が分かれば、年齢・星座が分かる • 姓名・住所が分かれば、個人番号が分かる • 個人番号が分かれば、生年月日・性別・姓名・住所が分かる以下を既知として、候補キーを見つける

K を属性全体の集合とおく 2. Kの各属性Aに対して以下を実行する {K - A}+が属性全体の集合となればK を K - A で置き換えるそうでなければ、Kをそのままとする 3. 最終的に残ったKが候補キーとなる候補キーを１つ求めるためのアルゴリズム（再掲）

年齢生年月日住所個人番号星座性別郵便番号 K

年齢生年月日住所個人番号星座性別郵便番号 A

年齢生年月日住所個人番号星座性別郵便番号 K-A

年齢生年月日住所個人番号星座性別郵便番号 {K-A}+

年齢生年月日住所個人番号星座性別郵便番号 K:=K-A

年齢生年月日住所個人番号星座性別郵便番号候補キー！

属性の選び方によって見つかる候補キーは異なる • 属性の数をN、関数従属性の数をPとすると、閉包を求める計算はN×Pのオーダーの時間計算量となる • 候補キーの計算は結局、各属性に対して閉包を求めることになるので、(N^2)×Pのオーダーの時間計算量となる

最後に 

今日持ち帰っていただきたいこと・候補キーとは一体何か　→行を一意に特定する極小のキー・候補キーを見つけることはなぜ重要なのか　→正規化において主軸となる要素のため・候補キーを求めるためのアルゴリズムはどのようなものか　→全属性集合から各属性を順に取り除いて閉包を計算し　　それが全属性集合と一致するかを判定する・なんか面白そうという気持ち→どうでしたか

参考文献・増永良文. リレーショナルデータベース入門[第3版] . サイエンス社, 2017 ・R. Elmasri and S. B. Navathe. Fundamentals of Database Systems. Addison-Wesley, 2000 ・C. Lucchesi and S. Osborn. Candidate keys for relations, Journal of Computer and System Sciences. 1978

X^0 = Xとおく 2. X^i = X^(i-1) U {X^(i-1)の要素が決定項となる全ての関数従属性の被決定項からなる属性名の集合} 3. X^i = X^(i-1)ならX^(i-1)がXの閉包。そうでなければ添字iの値を１つ足して、２を再度評価閉包X+を求めるためのアルゴリズム

リレーショナルデータベースの略 • リレーショナルデータモデルに基づいて実装されたDB それを管理するシステムがRDBMS • 例 ◦ MySQL ◦ SQL Server ◦ Oracle ◦ etc.. RDBとは

集合(重複のない要素の集まり)を指す • 例 ◦ 人名の集合 D_name = {太郎,花子,二郎,....} ◦ 自然数の集合 D_natural = {1,2,3,4,5,...} ◦ 都道府県の集合 D_pref = {北海道,青森県,...} ◦ etc.. ドメインとは

RDBおける候補キーを求めるためのアルゴリズム

RDBおける候補キーを求めるためのアルゴリズム

More Decks by kubo ayumu

Other Decks in Programming

Featured

Transcript