TR NG ĐI H C S PH M K THU T H CHÍ MINHƯỜ Ạ Ọ Ư Ạ Ỹ Ậ Ồ
H và tênọ: Đinh Th Huy nị ề
SBD: 13610017
L pớ: CNTT – K3
Gi i quy t bài toán phân m ng d cả ế ả ọ
Đ bàiề: Cho quan h toàn c c Project nh sau:ệ ụ ư
Project(PNo, Name, Location, Budget, MgrName, Duration)
Xét các truy v n:ấ
q1: Tìm thông tin tên và kinh phí các d án:ự
SELECT Name, Budget FROM Project
q2: Xác đnh thông tin tên, đa đi m và th i gian th c hi n các d ánị ị ể ờ ự ệ ự
SELECT Name, Location, Duration FROM Project
q3: Tìm t t c các đa đi m d án theo ng i qu n lýấ ả ị ể ự ườ ả
SELECT Location FROM Project WHERE MgrName = value
q4: Tìm thông tin tên, kinh phí các d án theo th i gian th c hi n d ánự ờ ự ệ ự
SELECT Name, Budget FROM Project WHERE Duration = value
T n s s d ng các truy v n qầ ố ử ụ ấ i t i các site Sạj nh sau:ư
Trong đó: a – 2 s cu i c a mã s sinh viên c a h c viênố ố ủ ố ủ ọ
a/ Xây d ng ma tr n ái l c c a các thu c tính quan h Project;ự ậ ự ủ ộ ệ
b/ Cho bi t s truy xu t đn các c p thu c tính cho m i ngế ố ấ ế ặ ộ ỗ ứ
d ng t i các v trí refụ ạ ị i(qj) = 1. Phân đo n d c quan h Project sạ ọ ệ ử
d ng thu t toán năng l ng k t BEA.ụ ậ ượ ế
S1S2S3
q12 8 0
q23 0 1
q3a 10 0
q4a 0 5
BÀI LÀM
Project(PNo, Name, Location, Budget, MgrName, Duration)
Name: A1
Location: A2
Budget: A3
MgrName: A4
Duration: A5
Ma tr n Useậ: Ma tr n t n s truy c p:ậ ầ ố ậ
- Ta tính đc ma tr n AA:ượ ậ
A1A2A3A4A5
q11 0 1 0 0
q21 1 0 0 1
q30 1 0 1 0
q41 0 1 0 1
S1S2S3
q12 8 0
q23 0 1
q317 10 0
q417 0 5
A1A2A3A4A5
A136 4 32 0 26
A24 31 0 27 4
A332 0 32 0 22
A40 27 0 27 0
A526 4 22 0 26
Dùng thu t toán năng l ng liên k t đ tính ma tr n CA:ậ ượ ế ể ậ
Xét ma tr n AA và ma tr n CA sau đây v i Aậ ậ ớ 1, A2 đã đc đt:ượ ặ
Ta c n chèn thêm Aầ3, có 3 kh năng:ả
1. Chèn A3 tr c Aướ 1:
Cont (_, A3, A1) =
bound(_, A3) + bound(A3,A1) – bound(_,A1) =
0 + 2748 – 0 = 2748
2. Chèn A3 vào gi a Aữ1, A2:
Cont (A1, A3, A2) =
bound(A1, A3) + bound(A3,A2) – bound(A1,A2) =
2748 + 216 – 372 = 2592
A1A2
A136 4
A24 31
A332 0
A40 27
A526 4
A3A1A2
A132 36 4
A20 4 31
A332 32 0
A40 0 27
A522 26 4
A1A3A2
A136 32 4
A24 0 31
A332 32 0
A40 0 27
A526 22 4
3. Chèn A3 sau A2:
Cont (A2, A3, _) =
bound(A2, A3) + bound(A3,_) – bound(A2,_) =
2160 – 0 = 216
Ta th y kh năng th nh t cho k t qu l n nh t ấ ả ứ ấ ế ả ớ ấ ch n chèn Aọ3 vào tr c Aướ 1
Ma tr n CA sau khi thêm c t Aậ ộ 3:
- Ti p t c chèn thêm Aế ụ 4, có 4 kh năng:ả
1. Chèn A4 tr c Aướ 3:
Cont (_, A4, A3) =
bound(_, A4) + bound(A4,A3) – bound(_,A3) =
0 + 0 + 0 = 0
A1A2A3
A136 4 32
A24 31 0
A332 0 32
A40 27 0
A526 4 22
A3A1A2
A132 36 4
A20 4 31
A332 32 0
A40 0 27
A522 26 4
A4A3A1A2
A10 32 36 4
A227 0 4 31
A30 32 32 0
A427 0 0 27
A50 22 26 4
2. Chèn A4 vào gi a Aữ3, A1:
Cont (A3, A4, A1) =
bound(A3, A4) + bound(A4,A1) – bound(A3,A1) =
0 + 108 – 2748 = -2640
3. Chèn A4 vào gi a Aữ1, A2:
Cont (A1, A4, A2) =
bound(A1, A4) + bound(A4,A2) – bound(A1,A2) =
108 + 1566 – 372 = 1302
4. Chèn A4 sau A2:
Cont (A2, A4, _) =
bound(A2, A4) + bound(A4, _) – bound(A2, _) =
1566 + 0 – 0 = 1566
A3A4A1A2
A132 0 36 4
A20 27 4 31
A332 0 32 0
A40 27 0 27
A522 0 26 4
A3A1A4A2
A132 36 0 4
A20 4 27 31
A332 32 0 0
A40 0 27 27
A522 26 0 4
A3A1A2A4
A132 36 4 0
A20 4 31 27
A332 32 0 0
A40 0 27 27
A522 26 4 0