データベース論

データベース論
朝日大学大学院
経営学研究科
奥山徹
[email protected]
2006/04/17
データベース論（1回目）
1
講義日程
•
•
•
•
•
•
•
•
•
•
•
4月17日
4月24日
5月01日
5月08日
5月15日
5月22日
5月29日
6月05日
6月12日
6月16日
6月26日
2006/04/17
ガイダンスおよび集合論の基礎
リレーショナルデータベースの基礎
データ操作言語
データベースの論理設計
SQL（データベース操作言語）の基礎
データベース管理システム
データベースの内部スキーマ
質問処理とその最適化
トランザクション処理
分散データベース序説
定期試験
データベース論（1回目）
2
ガイダンス資料（１）
• 内容
– データベース全般についてのお話
– 今日、特によく利用されているリレーショナル（関係）
モデルとそのDBMS（データベース管理システム）つ
いて詳述
– トランザクション処理やデータベースの内部構造に
ついても解説
– 時間があれば分散データベースシステムについても
解説
• 評価
– 定期試験（50%）、レポートなど（50%）で総合評価
2006/04/17
データベース論（1回目）
3
ガイダンス資料（２）
• 教科書
– 増永良文、「リレーショナルデータベース入門[改訂版]」、サイ
エンス社
• 参考図書
– 増永良文、「リレーショナルデータベースの基礎」、オーム社
– 鶴保征城監修、「未来ねっと技術シリーズ９、情報データベー
ス技術」、電気通信協会
– 横田一正、宮崎収兄、「新データベース論」、共立出版
– 山本森樹、「体系的に学ぶデータベースの仕組み」、日経BPソ
フトプレス
– C.J.Date、「データベース実践講義」、オライリージャパン
• 「データベース論」WEBページ（現在準備中）
– http://www.dsl.gr.jp/~okuyama/lecture/2006/tut/
2006/04/17
データベース論（1回目）
4
データの収集・蓄積・利用
データ
実世界
アクセプタ
編集
加工
蓄積
要求
処理
ユーザ
データ要求
データの収集
2006/04/17
データ（フィードバッ
ク）
データの蓄積
データの利用
データベース論（1回目）
5
データと情報
「新データベース論」より
• データ：人間または自動的手段によって
行われる通信、解釈、処理に適するよう
に形式化された事実、概念または指令の
表現
• 情報：データを表現するために用いた約
束に基づいて、人間がデータに割り当て
た意味
2006/04/17
データベース論（1回目）
6
集合の基礎
• 定義：集合とは要素の集まりである
• 一般に集合の要素間には何の関係もな
い
• 集合に構造を持たせることで種々の応用
が可能となる
– 代数構造 → 四則演算
– 順序構造 → 大小関係
– 位相構造 → 連続性
2006/04/17
データベース論（1回目）
7
代数構造
• 集合の任意の二つの要素間に演算（２項
演算）を導入すること
• ２項演算→２つの要素を結合してもう１つ
の要素を作る一定の規則
• 有限幾何、ブロックデザイン、直交表等の
ようなバランスのとれた部分集合や配列が
出来る→効率の良い符号系やファイルを
作ることが可能
2006/04/17
データベース論（1回目）
8
順序構造
• 包含関係のような半順序が重要
• 束の概念から論理演算に結びつく
• 順序の定義づけが可能→比較可能性の
説明ができる→「空間における順序」など
の概念の基礎
2006/04/17
データベース論（1回目）
9
集合かどうか？
•
•
•
•
•
•
•
•
自然数全体の集まり→集合（無限集合）
0≦x≦1である実数全体の集まり→集合（無限集合）
10より小さい（正の）素数の集まり→集合（有限集合）
ｘ2＋ｙ2 ＜ 1 の不等式を満たす点(x,y)の全体の集合
→集合（無限集合）
実数の閉区間[0,1]で定義された連続な実数値関数全体
の集まり→集合（無限集合）
p,q,rという3つの文字の集まり→集合（有限集合）
p,q,rという3つの文字の順列全体の集まり→集合（有限
集合）
十分大きな自然数の集まり→集合ではない
2006/04/17
データベース論（1回目）
10
【演習問題1-1】
1) 十分大きな自然数の集まり→集合ではない
なぜ集合と言えないか説明せよ
2) 次のものは集合と言えるか
2
2
1) 正の整数の集まり
2) 豊橋技術科学大学における知識情報工学４年生の
集まり
3) 国道259号線を田原方面へ向かう車の集まり
4) LAN上を流れるパケットの集まり
5) 一つの内角が60度以下の正多角形の集まり
6) パソコンに搭載されている全メインメモリの集まり
2006/04/17
データベース論（1回目）
11
集合と元
• 集合はA, B, C, …, X, Y, Z等と表記する
• 集合Aに含まれる‘もの’を、Aの元（また
は元素、要素）と呼ぶ
• aが集合Aの元であるとき、a∈Aあるいは
A∋aと表記する（元でない場合はa∈Aある
いはA∋aとなる）
• 無限に元が存在する集合を無限集合、有
限の元しかもたない集合を有限集合という
2006/04/17
データベース論（1回目）
12
集合の表記
• 外延的表記
{p, q, r} {1, 2, 3, …….}
• 内包的表記
{x|xは有理数である}
{y|yは0≦y≦1である実数である}
{n|nは10より小さい正の素数}
2006/04/17
データベース論（1回目）
13
内包的記述についての考察
• 変数とその条件（性質）
yは0≦y≦1の実数である
• 変数yについての条件→C(y)
• C＝C(x)の時、あるaについて、C(a)が正
しいなら、aは条件Cを満たす（性質Cをも
つ）
• 条件Cを満たす全体→集合を形成
{x|C(x)}
2006/04/17
データベース論（1回目）
14
空集合(φ)とサイズ
• C＝C(x)の時、あるaについて、C(a)が正
しくなるのもが見つからない
• 条件Cを満たす全体→集合を形成
{x|C(x)}
上記関係を満たす（何も元を持たない）集
合を空集合(φ)と呼ぶ
• 集合に含まれる元の数→サイズ、|A|
2006/04/17
データベース論（1回目）
15
【演習問題1-2】
1) 集合{1,2,3}を内包的表記を用いて表せ
2) 次の集合を外延的表記で表せ（空集合
はφと書け）
1) {x|x∈Q, x3=2} (Qは有理数の集合)
2) {y|y ∈N, 1<y2<10} (Nは自然数の集合)
3) {z|z ∈Z, 0.1<2z<100} (Zは整数の集合)
2006/04/17
データベース論（1回目）
16
集合の相等
• すべての元が同じ集合 A=B
<例>
A:{x|xは2<x<10である素数}
B:{y|yは1<y<8である奇数}
• 外延的表記における注意
A={a,b,c,…}とB={a,b,c,…}基本的に同じ
ものを指さなければならない→A=Bという
相等が崩れる
2006/04/17
データベース論（1回目）
17
集合の相等（２）
• {x|C(x)}={y|C(y)}
• 任意の元xに対して、x∈A⇔x∈Bとなる。
(⇔は（論理的に）同等)
• 論理記号の補足
– p⇒q（pならばq）：pが正しいときはqもまた正
しい
– p⇔q（pはqと同等）：p⇒qが正しく、かつq⇒p
も正しいとき、またそのときに限り正しい
2006/04/17
データベース論（1回目）
18
部分集合
• 任意の元xにたいして、x∈A⇒x∈Bなる関
係が成り立つ時、AはBの部分集合である
という
A⊂BまたはB⊃A
• A⊂BでA≠Bのとき、AはBの真部分集合で
あるという（A⊂B、A ≠Bと記す、A⊆という
記述法もあるが、ここでは前者を採用す
る）
2006/04/17
データベース論（1回目）
19
部分集合による相等と推移律
• A=Bであるための必要十分条件
A⊂B かつ A⊃B
すなわち、A=B ⇔ A⊂BかつA⊃B
• A⊂B 、B⊂C ⇔ A⊂C
• φ⊂Aと約束する
2006/04/17
データベース論（1回目）
20
集合間の演算
• ２つの集合間の演算
–
–
–
–
–
2006/04/17
和集合
共通集合（積集合）
差集合
普遍集合と補集合
集合系とべき集合
データベース論（1回目）
21
集合演算（和集合）
• Aの元とBの元を全部集めた集合
• 和集合 A∪B、∪→結び(join, cup)
• A∪B={x|x∈Aまたはx∈B}
<例>
A={1,2,3,4,5}、B={3,5,7,9}
A ∪B={1,2,3,4,5,7,9}
Aを正の偶数全体の集合、Bを正の奇数全体の
集合
A ∪B=N
2006/04/17
データベース論（1回目）
22
集合演算（和集合）その２
(a1) A⊂A∪B、B⊂A∪B
(a2) A⊂C、B⊂C、⇒A∪B⊂C
(a2)の証明：
A⊂B, B⊂Cとして、x∈A∪Bとする
A ∪Bの定義によって, x∈Aまたはx∈B、x∈AならばA⊂B
であるから、x∈C, x∈Bの場合も同様
ゆえにx∈C、すなわちx∈A ∪Bならばx∈C
よって、A ∪B⊂C
2006/04/17
データベース論（1回目）
23
集合演算（和集合）その３
(a3) A∪A＝A（ベキ等律）
(a4) A∪B＝B∪A（交換律）
(a5) （A∪B）∪C＝A∪（B∪C）（結合律）
• (a5)の両辺はA∪B∪Cとも書く。一般に、n
個の集合、A1, A2, …, Anがあるとき、A1
∪A2∪…∪Anあるいは∪ni=1Aiと記す
2006/04/17
データベース論（1回目）
24
集合演算（和集合）その４
(a6) A⊂B⇔A∪B=B
(a7) A⊂B⇒A∪C⊂B∪C
(a8) φ∪A=A
2006/04/17
データベース論（1回目）
25
集合演算（積集合、共通集合）
• Aの元とBの元の共通部分を集めた集合
• 積集合 A∩B、∩→交わり(meet, cap)
• A∩B={x|x∈Aかつx∈B}
<例>
A={1,2,3,4,5}、B={3,5,7,9}
A∩B={3,5}
Aを正の偶数全体の集合、Bを正の奇数全体の
集合
A∩B=φ
2006/04/17
データベース論（1回目）
26
集合演算（積集合、共通集合）２
(a1)’ A⊃A∩B、B⊃A∩B
(a2)’ A⊃C、B⊃C、⇒A∩B⊃C
(a3)’ A∩A＝A（ベキ等律）
(a4)’ A∩B＝B∩A（交換律）
(a5)’ （A∩B）∩C＝A∩（B∩C）（結合律）
• (a5)’の両辺はA∩B∩Cとも書く。一般に、n
個の集合、A1, A2, …, Anがあるとき、A1
∩A2 ∩… ∩Anあるいは∩ni=1Aiと記す
2006/04/17
データベース論（1回目）
27
集合演算（積集合、共通集合）３
(a6)’ A⊂B⇔A∩B=A
(a7)’ A⊂B⇒A∩C⊂B∩C
(a8)’ φ∩A＝φ
• 分配律
(a9) （A∪B）∩C＝（A∩C）∪（B∩C）
(a9)’ （A∩B）∪C＝（A∪C）∩（B∪C）
• 吸収律
(aa) （A∪B）∩A＝A
(aa)’ （A∩B）∪A＝A
2006/04/17
データベース論（1回目）
28
集合演算（直和）
• AとBが互いに素であるとき
• A∪Bは直和である
<例>
A={1,3,5,7,9}、B={2,4,6,8}
A ∪B={1,2,3,4,5,6,7,8,9}
2006/04/17
データベース論（1回目）
29
集合演算（差集合）
•
•
•
•
Aの元であってBの元ではないものの集合
差集合 A－B
A∩B={x|x∈Aかつx∈B}
A⊃Bである場合、A－BをAに対するBの補集合
という
<例>
自然数の集合N、Bを正の奇数の整数全体の集
合
N－B：正の偶数の整数全体の集合
2006/04/17
データベース論（1回目）
30
普遍集合
• 現在の対象集合が、ある定まった集合の
部分集合である時、その集合を普遍集合
あるいは全体集合(universal set)とよぶ
• 普遍集合Xが与えらているとき、集合A（X
の部分集合）のXに対する補集合X－Aを
単にAの補集合と呼びAcで表す
2006/04/17
データベース論（1回目）
31
普遍集合その２
X
A
Ac
• x∈Xとすると、Ac={x|x∈A}
• x∈A⇔x∈Ac
2006/04/17
データベース論（1回目）
32
普遍集合その３
(ab) A ∪Ac=X, A ∩ Ac=φ
(ac) Acc=A
(ad) φc=X, Xc=φ
(ae) A⊂B⇔Ac⊃Bc
• de Morganの法則
(af) （A ∪ B）c=Ac ∩ Bc
(af)’ （A ∩ B）c=Ac ∪ Bc
2006/04/17
データベース論（1回目）
33
集合系とベキ集合
• 集合を要素とする集合→集合系
• 集合Aのすべての部分集合を含むものをベキ集
合という
• 部分集合の集合は情報処理の中では重要な役
割を演じることがある
＜例題＞７人が麻雀を７回戦行う場合を考える。こ
のさい、どの二人も２回ずつ顔を合わせるような
組み合わせを作れるか
→BIBD(balanced incomplete block design)
2006/04/17
データベース論（1回目）
34
ベキ集合
• ベキ集合→2n個の元を持つ
<例>
X={0,1,2,3}→24=16個の元
Δ(X)={φ,{1},{2},{3},{0,1},{0,2},
{0,3},{1,2},{1,3},{2,3},{0,1,2},
{0,1,2},{0,1,3},{0,2,3},{1,2,3},
{0,1,2,3}}
• ベキ集合の構成方法（次のスライド）
2006/04/17
データベース論（1回目）
35
ベキ集合構成の方法
0
01
012
12
1
23
φ
2
123
0123
30
230
02
3
13
2006/04/17
301
データベース論（1回目）
36
集合の直積
• 定義：A, Bを集合とするとき、Aの元aとB
の元bの順序付けられた組(a,b)全体の作
る集合をAとBの直積と呼ぶ
• 表記：
A×B
• 例： A={1,2}、B={p,q,r}とする
A×B={(1,p), (1,q), (1,r), (2,p), (2,q),
(2,r)}
A×A={(1,1), (1,2), (2,1), (2,2)}
2006/04/17
データベース論（1回目）
37
順序付けられたの意味
• 順序付けられた組(a,b)→aとbをこの
順番に‘組み合わせた’ものである
• aとbの順序が重要である
• (a,b)と(b,a)はa=bのときに限り、同じ
‘順序付けられた組’となる
2006/04/17
データベース論（1回目）
38
直積の元の相等
• A×Bの元(a,b)と(a’,b’)があるとする
• もちろん、a∈A、a’∈A、b∈B、b’∈Bで
ある
• (a,b)と(a’,b’)はa=a’、b=b’のとき、か
つそのときに限って等しいものとする
2006/04/17
データベース論（1回目）
39
直積の幾何学的な表現
• A×Bの元(a,b)に対して、aを第一成分（第一座
標）、bを第二成分（第二座標）と呼ぶ
• Aがm個の元、Bがn個の元からなる有限集合の
2
2
場合、A×Bはmn個の元を持つ有限集合となる
• A×Bを表すのに図のような幾何学的な平面を
考えることが多い
(a,b)
a
• R×Rの元(x,y)は
A
平面上の点の集合
b
2006/04/17
データベース論（1回目）
B
40
【演習問題1-3】
(1) 次の２つの集合の直積を示せ
・ A={a,b,c}, B={x,y,z}
・ A={1,2,3}, B=φ
2006/04/17
データベース論（1回目）
41
対応の定義
• A,Bを２つの集合とする
• ある規則Γによって、Aの元aに対して、そ
れぞれ１つずつのBの部分集合Γ(a)が定
められる
– 注：a≠a’のときΓ(a)＝Γ(a’)であってもよい
– また、Γ(a)＝φでもよい
• 規則Γ：AからBへの対応
2006/04/17
データベース論（1回目）
42
対応の表記と相等
• A,Bは集合とし、Aの元aにたいするBの部分集
合Γ(a)をΓによるaの像と呼ぶ、A,Bを対応Γの
始集合、終集合と呼ぶ
• 対応の表記
Γ：A→B
• 対応の相等
– Γ、Γ’がいずれもAがらBへの対応とする
– Aのいかなる元aにたいしても、Γ(a)=Γ’(a)
– ΓとΓ’は等しい（相等）である
2006/04/17
データベース論（1回目）
43
写像
• AからBへの対応Γは、次の性質を持つとき、特
にAからBへの写像と呼ばれる
Aの任意の元aに対して、Γ(a)はBのた
だ1つの元から成る集合である
• D(Γ)=A
• f をAからBへの写像、Aの元aとすると
f (a)={b} → f (a)=b
bをf によるaの像と呼ぶ
2006/04/17
データベース論（1回目）
44
写像(2)
• 写像 f ：A→Bによるaの像がbである
– aにおけるf の値はbである
– f はaにbを対応させる
– f はaはbを写す
• ＜例＞
実数xにx2+1に対応させれば、RからRへ
の１つの写像が得られる
f (x)=x2+1
2006/04/17
データベース論（1回目）
45
全射、単射、全単射
•
•
•
全射： f (A)=B
単射：f (a)=f (a’)⇒a=a’
全単射：写像 f ：A→Bが全射であると同
時に単射のとき
2006/04/17
データベース論（1回目）
46
全射
f ：A→Bのとき、
定義域 D( f )=Aであるが、値域V( f )=
f (A)がBであるとはいえない
• f (A)=Bであるとき、写像 f は全射である
• あるいは、f はAからBの上への写像
• 全射であるとき、Bのどの元bに対しても、
f –1(b)≠φである。すなわち、f (a)=bとなる
Aの元aが存在する
2006/04/17
データベース論（1回目）
47
単射
f ：A→Bのとき、
Aの任意の元a, a’に対して
• a ≠a’⇒ f (a) ≠ f (a’)
• f (a)=f (a’)⇒a=a’
が成り立つとき、AからBへの単射、または
AからBへの１対１の写像である
• f の値域V( f )の任意の元bに対して、
f –1(b)がいつもAのただ１つの元からなる
2006/04/17
データベース論（1回目）
48
全単射
f ：A→Bが同時に
全射かつ単射であるとき、
f はAからBへの全単射である
2006/04/17
データベース論（1回目）
49
恒等写像
•
•
•
•
•
Aを任意の集合、PをAの部分集合とする
Pの各元aにAのa自身を対応させる
PからAへの１つの写像 i が定まる
写像 i は明らかにPからAへの単射であ
る
→PからAへの標準的単射
特にP=Aの場合
→標準的単射は、Aの上の恒等写像IA
2006/04/17
データベース論（1回目）
50
逆写像
•
•
•
写像 f :A→Bを全単射
定理3-1により逆対応 f –1 ：B→Aも写像
f –1 を f の逆写像という
2006/04/17
データベース論（1回目）
51
写像の合成
•
•
•
A,B,Cを3つの集合とする
AからBへの写像 f , BからCへの写像 g
Aの任意の元aに対して
–
–
•
•
aの f による像 f (a)が定まる
f (a)の g による像 g ( f (a))が定まる
Aの各元aに対して、１つずつCの元
g ( f (a))が定まる
→aを g ( f (a))に対応させる写像ψ
ψ：A→Cを f と g の合成写像または積と呼ぶ
2006/04/17
データベース論（1回目）
52
写像の合成(2)
•
•
•
ψ：A→Cを f と g の合成写像または積
表記法： g。f または gf
すべてのa∈Aに対して
(g 。 f )(a)=g ( f (a))
2006/04/17
データベース論（1回目）
53
関係の概念
•
2個以上の変数を含む条件を考える
–
–
–
•
x,yは有理数でx<yである；
x,y,zは実数でx2+y2=2zである；
p,lは平面π上の点および直線で、pはlの上
にある；
これらは一般に変数間の関係と呼ばれ
る
• 関係に含まれる変数には変域、すなわち、
その変数に代入できるものの集合が定
2006/04/17まっている
54
データベース論（1回目）
関係の表記
• 関係をRで表す
• Rがn変数、x1,x2,…,xnの関係で、各
変数の変域がX1,X2,…,Xnとするな
らば、
R(x1,x2,…,xn) (xiの変域はXi)
• R(x,y) (x,yは共に変域A)という2変
数の関係がよく考えられる
2006/04/17
データベース論（1回目）
55
2変数の関係
•
•
•
•
R(x,y) (x,yは共に変域A)
これをAにおける単なる関係と呼び、xRy
と表記する
Rを集合Aにおける１つの関係とするとき、
aRbが成り立つようなAの元a,bの組(a,b)
の全体は、A×Aの１つの部分集合を形
作る
これを、関係Rのグラフと呼び、G(R)で表
す→G(R)={(a,b)|a∈A,b∈B, aRb}
2006/04/17
データベース論（1回目）
56
2変数の関係(2)
• A×Aの任意の部分集合Gが与えら
れたとき、G=G(R)となるような関係
Rを1つだけ定義することができる
• すなわち、Aの元a,bに対して、
(a,b)∈Gのときまたそのときに限って
aRbが成り立つRを定めればよい
2006/04/17
データベース論（1回目）
57
同値関係
•
集合Aにおける関係Rが次の(1)、(2)、(3)
を満たすとき、RはAにおける同値関係で
あるという
(1) Aのすべての元aに対してaRa
(2) Aの元a,bに対してaRb⇒bRa
(3) Aの元a,b,cに対してaRb,bRc⇒aRc
（１）は反射律、（２）は対称律、（３）は推
移律といい、これら3つを同値律と呼ぶ
2006/04/17
データベース論（1回目）
58
同値関係の例(1)
• Aを任意の集合として、RをAの元の
間の相等関係=とするば、これはA
における１つの同値関係である
• a=bは明らかに同値律を満たしてい
る
• 最も原始的な同値関係
2006/04/17
データベース論（1回目）
59
同値関係の例(2)
• 整数の集合Zと１つの定まった正の
整数nを考える
• Zの元a,bは、a-bがnで割り切れると
きに、nに関して合同であると言われ、
a≡b(mod n)またはa ≡b(n)と表記さ
れる
• この関係≡(mod n)はZにおける１つ
の同値関係である
2006/04/17
データベース論（1回目）
60
同値関係の例(2)-2
• 任意のa∈Zに対し、a-a=0であるから、
0はnで割り切れるので、a≡a(mod n)
である（反射律）
• a,b∈Zに対して、a-bがnで割り切れ
るなら、b-a=-(a-b)ももちろんnで割り
切れる。すなわち、a≡b(mod n)なら
ばb≡a(mod n)である（対称律）
2006/04/17
データベース論（1回目）
61
【演習問題1-4】
• 同値関係の例(2)において、推移律
が成り立つことを示せ
2006/04/17
データベース論（1回目）
62
同値関係の例(3)
•
•
•
•
f を集合Aから集合Bへの1つの写像とす
る
Aの元x,yに対して、それらの f による像
が一致する、すなわち
f (x) = f (y)
そのときに限り、xRyとして関係Rを定義
すれば、それは明らかにAにおける同値
関係となる
これを写像 f に付随する同値関係と呼ぶ
2006/04/17
データベース論（1回目）
63
対等の概念
•
•
•
•
集合AからBへの全単射が存在するとき、
BはAに対等(equipotent)である
A～B（対等の表記）
定理4-1
(d1) A～A
(d2) A～B⇒B～A
(d3) A～B, B～C⇒A～C
空集合φは、ただそれ自身のみに対等
2006/04/17
データベース論（1回目）
64
有限集合と無限集合
•
•
•
有限集合
ある自然数nについて、{1,2,3,…,n｝と対等
な集合及び空集合を有限集合と呼ぶ
無限集合
有限集合以外の集合を無限集合と呼ぶ
２つの有限集合が対等となるのは、同じ個
数の要素をもつときである
2006/04/17
データベース論（1回目）
65
対等の例
• N={1,2,3,…}, E={2,4,6,…}とする。f ：
N→Eをf(x)=2xとすると、f は全単射と
なるので、NとEは対等である
• f ： (-1,1)→Rを f(x)=x/(1-|x|)と定義す
ると, R上への1対1の関数を定義でき
る。ゆえに、開区間(-1,1)は実数全体
Rと対等である。
2006/04/17
データベース論（1回目）
66
可付番集合と可算集合
•
•
•
自然数全体Nと対等な集合X：可付番集
合という
Xは濃度(cardinality)として、X0（アフロゼ
ロ）を持つ
可算集合：有限または可付番集合
2006/04/17
データベース論（1回目）
67
【演習問題1-5】
(1) 次のものは可付番集合かどうか示せ
・異なる項からなる無限数列
a1,a2,a3,…
・M={0,1,2,3,…}=N∪{0}とするとき、
M×M
・単位区間[0,1]（ここで、[ ]なる表記は閉
区間であることを示す）
2006/04/17
データベース論（1回目）
68
連続体
•
•
•
•
有限でも可付番でもない集合を非可付
番または非可算と呼ぶ
演習問題4-1の3番目の例は非可算であ
る
区間[0,1]と対等な集合を、連続体濃度を
持つあるいは濃度 c を持つという
すべての区間は濃度 c を持つ、すなわち
Rと対等となる
2006/04/17
データベース論（1回目）
69
シュレーダー-ベルンシュタインの定理
•
•
•
AがBのある部分集合と対等なとき、
A B
と書く
すなわち、A B⇔∃B*⊂B（A～B*）
またA BであってA～B（すなわち、Aが
Bと対等でない）とき、A Bと書く
2006/04/17
データベース論（1回目）
70
NとRの関係
•
•
•
NはRの部分集合であるからN
る
Rは非可算
ゆえにN Rである
2006/04/17
データベース論（1回目）
Rであ
71
S-Bの定理
A BかつB AならばA～B
あるいは
X⊃Y⊃X1かつX～X1ならばX～Y
↓
任意のA,BについてA B, A～B, B
のいずれかが成立する
2006/04/17
データベース論（1回目）
A
72
濃度
•
•
•
•
•
•
A～Bのとき、AとBの基数あるいは濃度が同じ
であるという
card(A)で濃度を表す
card(A)=card(B)⇔A～B
card(A)＜card(B)⇔A B
card(B)＜card(A)⇔B A
S-Bの定理
card(A)≦card(B)かつcard(B)≦card(A)ならば
A～B
2006/04/17
データベース論（1回目）
73
濃度(２)
•
•
集合φ、{φ}、{φ、{φ}}、{φ、{φ}、{φ、
{φ}}}…の濃度を,０,１,２,３,…であらわし、
有限濃度と呼ぶ
０<１<２<３<…<X0<c
2006/04/17
データベース論（1回目）
74
半順序集合
•
A上の関係が次の性質を持つとき、A
上の半順序あるいは順序と呼ぶ
–
–
–
•
a
a
a
Aと
2006/04/17
a
bかつb
bかつb
aならばa=b
cならばa c
の組（A,
）を半順序集合と呼ぶ
データベース論（1回目）
75
【演習問題1-6】
(1) 集合の包含関係は集合族上の順序であ
る。これを示せ。
(2) Aを実数の任意の集合とすると、A上の
x≦yは順序である。これを示せ。（自然順
序）
(3) X={a,b,c,d,e}とするとき、それらを頂点と
する有向グラフは順序となる。これを示
せ。
2006/04/17
データベース論（1回目）
76
全順序集合
•
半順序集合が、さらに次の性質を持つと
き、全順序集合あるいは線形順序集合と
呼ぶ
–
2006/04/17
∀x,y∈A(x
yまたはy
データベース論（1回目）
x)
77
まとめ
•
•
•
•
データベース論の導入として、集合の基
礎を駆け足で学習した
データベースとは、まさに現実世界から
条件に合った部分集合を切り出したもの
である
集合の概念は、データベースの基礎をな
す
関係は集合の概念から導き出されたも
のである
2006/04/17
データベース論（1回目）
78

Download Report