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