ĐẠI HỌC THÁI NGUYÊN
TRƯỜNG ĐẠI HỌC CNTT & TRUYỀN THÔNG NGUYỄN QUANG THẮNG GIẢI CÁC BÀI TOÁN TRÊN CÂY TOÁN TỬ ĐƯỜNG ỐNG BẰNG
MA TRẬN ĐẶC TRƯNG th¹c sÜ khoa häc m¸y tÝnh
Chuyên ngành: Khoa học máy tính
Mã số chuyên ngành: 60 48 01
LUẬN VĂN THẠC SĨ KHOA HỌC MÁY TÍNH
NGƯỜI HƯỚNG DẪN KHOA HỌC
PGS.TS. LÊ HUY THẬP Th¸i Nguyªn – 2012
Số hóa bởi Trung tâm Học liệu – Đại học Thái Nguyên
i
LỜI CAM ĐOAN
Tôi xin cam đoan bản luận văn này là công trình nghiên cứu của riêng
tôi, không sao chép ở bất kỳ công trình khoa học nào trƣớc đây. Các kết quả
nêu trong luận văn có nguồn gốc rõ ràng và đƣợc trích dẫn đầy đủ. Nếu có gì
sai, tôi xin chịu hoàn toàn trách nhiệm.
Học viên
Trang
MỞ ĐẦU 1
CHƢƠNG 1: CƠ SỞ LÝ THUYẾT 2
1.2. Các kiểu phân mảnh 4
1.2.1. Phân mảnh ngang 4
1.2.2. Phân mảnh dọc 18
1.2.3. Phân mảnh hỗn hợp 21
1.4. Kết luận chƣơng 1 22
CHƢƠNG 2: CÂY POT VÀ CÁC THUẬT TOÁN XỬ LÍ TRÊN POM 24
2.1 Thể hiện cây toán tử với các phép toán đại số quan hệ. 24
2.1.1. Định nghĩa cây toán tử 24
2.1.2. Các phép toán đại số quan hệ 28
2.1.3. Các bƣớc thể hiện cây toán tử 29
2.2. Giới thiệu POT 30
2.3. Phƣơng pháp chuyển POT sang POM 30
2.4. Một số định nghĩa tƣơng đƣơng giữa POT và POM 33
2.5. Các thuật toán trên POM 36
2.5.1. Thuậ t toá n gộ p 36
Số hóa bởi Trung tâm Học liệu – Đại học Thái Nguyên
iii
2.5.2. Thuậ t toá n tá ch ……………………………………………………….38
2.5.3. POM tiền xử lí 41
2.6. Kết luận chƣơng 2 44
CHƢƠNG 3: ỨNG DỤNG GIẢI MỘT SỐ BÀI TOÁN THỰC TẾ 45
3.1. Giới thiệu bài toán lập lịch 45
Phép trừ
X
Tích đề các
Phép nối
Phép chiếu
Tê ta
>
Phép so sánh lớn hơn
<
Phép so sánh nhỏ hơn
Phép so sánh lớn hơn hoăc bằng
Phép so sánh nhỏ hơn hoăc bằng
\
Phép chia
*
Phép nhân
AND
Phép và
OR
Phép hoặc
MB Measure of Belief (Độ chắn chắn)
MD Measure of Disbelief (Độ không chắc chắn)
POM Pipelined Operator Matrix (Ma trận đặc trƣng)
POT Pipelined Operator Tree (Cây toán tử đƣờng ống)
SQL Structured Query Langguage (Ngôn ngữ truy vấn có cấu trúc)
STM Short Term Memory (bộ nhớ tạ m thờ i)
IP Isomorphous (Ma trận liền kề)
Số hóa bởi Trung tâm Học liệu – Đại học Thái Nguyên
vi
DANH MỤC CÁC BẢNG BIỂU
Trang
Bảng 1.1. Quan hệ NhanVien 2
Bảng 1.2. Quan hệ DuAn 3
Bảng 1.3. Quan hệ TraLuong 3
Bảng 1.4. Quan hệ PhanNhiem 4
Bảng 1.5. Mảnh ngang DuAn
H1
6
Bảng 1.6. Mảnh ngang DuAn H2 6
Bảng 1.7. Mảnh ngang DuAn H3 6
Bảng 1.8. TraLuong
1
10
Bảng 1.9. TraLuong
2
11
vii
Bảng 2.8. Bảng POM
2
39
Bảng 2.9. Bảng POM
3
39
Bảng 2.10. Bảng POM
2#
40
Bảng 2.11. Bảng POM
2a
40
Bảng 2.12 Bảng POM
1a
40
Bảng 2.13. Bảng POM
3a
41
Bảng 2.14. Bảng POM có trọng số lớn 42
Bảng 2.15. Bảng POM tiền xử lý 42
Bảng 2.16. Bảng POM có trọng số lớn 43
Bảng 2.17. Bảng POM tiền xử lý 44
Bảng 3.1. Bảng dữ liệu POM 50
Bảng 3.2. Bảng POM tiền xử lý tƣơng ứng 51
Bảng 3.3. Bảng POM 1 52
Bảng 3.4. Bảng POM 2 52
Bảng 3.5. Bảng POM 3 52
Bảng 3.6. Bảng POM 4 53
Bảng 3.7. Bảng POM 5 53
MỞ ĐẦU
Khi cần xử lý một vấn đề nào đó bằng máy tính, nếu vấn đề có thể chia nhỏ
đƣợc và các phần đó đƣợc thực hiện song song thì sẽ rút ngắn thời gian hoàn
thành, tiết kiệm các chi phí tiềm năng, giải quyết đƣợc các vấn đề lớn và phức tạp.
Các kiến trúc máy tính hiện tại đang ngày càng dựa vào khả năng song
song hóa phần cứng để cải thiện hiệu suất nhƣ: Có nhiều đơn vị thực hiện, dùng
các chỉ lệnh đƣờng ống (Pipelined Instructions), đa nhân (Multi-core). Hơn nữa
các thiết bị phần cứng hiện rất sẵn có và rẻ tiền.
Giải các bài toán trên cây toán tử đƣờng ống đã đƣợc sử dụng để giải các
vấn đề lớn, phức tạp nhƣ dự báo thời tiết, mô hình sinh thái Và việc lập lịch tối
ƣu cho cây toán tử đóng góp một phần không nhỏ trong mục đích đó.
Cây toá n tƣ̉ mà mộ t số toá n tƣ̉ củ a nó có thể thƣ̣ c hiệ n song song , vớ i dƣ̃
liệ u ra củ a toá n tƣ̉ nà y có thể là dƣ̃ liệ u và o củ a toá n tƣ̉ kia đƣợ c gọ i là cây toá n
tƣ̉ dạ ng đƣờ ng ố ng POT (Pipelined Operator Tree). Mộ t cây toá n tƣ̉ tƣơng ƣ́ ng
mộ t – mộ t vớ i mộ t ma trậ n đặc trƣng nxn . Nhƣ vậy, POT cũng sẽ tƣơng ứng
một - một vớ i một ma trận đặc trƣng mà ta gọ i là POM (Pipelined Operator
Matrix). Khi đã có POM, các Xử lí trên POT nhƣ cân bằ ng tả i, lập lị ch truy vấ n
tố i ƣu, thực hiện các nhát cắt cục bộ, phân phối các toán tử cho các bộ Xử lý,
đƣợ c thƣ̣ c hiệ n trên POM. Xử lí trên POM tức là Xử lý trên mảng (ma trận) sẽ
đơn giản và thuận lợi hơn rất nhiều so với POT.
Phƣơng pháp giải các bài toán trên cây toán tử đƣờng ống bằng ma trận
đặc trƣng có nhiều ứng dụng nhƣ: chấm thi trắc nghiệm, ngân hàng, xử lý các
thông tin về thiên tai, an ninh, Số hóa bởi Trung tâm Học liệu – Đại học Thái Nguyên
Lê Hồng Ngoc
Hoàng Trung Mã
Trịnh Kim Thanh
Ngô Đình Vinh
Trần Mỹ Lệfaa
Lê Hồng Hạnh
Nguyễn Trƣờng Tâm
Kỹ sƣ điện
Phân tích và thiết kế hệ thống
Kỹ sƣ cơ khí
Lập trình viên
Phân tích và thiết kế hệ thống
Kỹ sƣ điện
Kỹ sƣ cơ khí
Phân tích và thiết kế hệ thống
Bảng 1.1. Quan hệ NhanVien
Số hóa bởi Trung tâm Học liệu – Đại học Thái Nguyên
3
Quan hệ DuAn(MaDuAn, TenDuAn, NganSach, ViTri)
Trong đó MaDuAn là mã dự án; TenDuAn là tên dự án và NganSach là ngân
sách dự án, ViTri là vị trí triển khai dự án. Và dữ liệu giả định nhƣ bảng 1.2:
Quan hệ TraLuong(TrinhDoCM, Luong)
Trong đó Luong là tiền lƣơng trả cho nhân viên. Và dữ liệu giả định nhƣ
bảng 1.3:
Quan hệ PhanNhiem (MaNV, MaDuAn, ChucVu, ThoiGianLV)
34000
27000
24000
Bảng 1.3. Quan hệ TraLuong
Số hóa bởi Trung tâm Học liệu – Đại học Thái Nguyên
4
Trong đó PhanNhiem là phân công nhiệm vụ: Phân công nhân viên có
MaNV làm tại dự án có MaDuAn, thời gian làm, với nhiệm vụ. ChucVu là giữ
chức vụ. Và dữ liệu giả định nhƣ sau:
Bảng 1.4. Quan hệ PhanNhiem
1.2. Các kiểu phân mảnh
Thể hiện của các quan hệ chính là các bảng, vì thế vấn đề là tìm những
kiểu khác nhau để chia một bảng thành nhiều bảng con khác nhau.
Các cách phân mảnh cơ bản là: Phân mảnh ngang, phân mảnh dọc và phân
mảnh hỗn hợp.
1.2.1. Phân mảnh ngang
Yêu cầu thông tin của phân mảnh ngang:
+ Thông tin về CSDL: Thông tin về CSDL là thông tin về lƣợc đồ khái niệm
toàn cục của CSDL. Tức là chúng ta cần biết đƣợc các quan hệ sẽ kết lại với nhau
nhƣ thế nào. Trong mô hình quan hệ, liên kết giữa các quan hệ cũng đƣợc biểu thị
bằng quan hệ. Theo cách này, chúng ta sẽ vẽ một đƣờng nối có hƣớng từ quan hệ
Parent đến quan hệ Child.
MaNV
MaDuAn
ChucVu
ThoiGianLV
NV1
24
6
10
48
18
24
48
36
40
Số hóa bởi Trung tâm Học liệu – Đại học Thái Nguyên
5
Chẳng hạn trên hình 1.1, hƣớng của các đƣờng nối cho biết mối quan hệ
một - nhiều. Chẳng hạn nhiều nhân viên có cùng “trình độ chuyên môn”, vì thế
có đƣờng nối hƣớng từ quan hệ TraLuong đến quan hệ NhanVien là 1-n. Tƣơng
tự cho Traluong, Nhanvien; DuAn và PhanNhiem. Còn quan hệ n-n là giữa
(Nhanvien, DuAn) và PhanNhiem.
Quan hệ nằm tại đầu của đƣờng nối đƣợc gọi là chủ nhân và quan hệ tại
cuối đƣờng nối gọi là thành viên. Chúng ta hãy định nghĩa hai hàm: Owner (chủ
nhân) và Member (thành viên), chúng là các ánh xạ từ tập các đƣờng nối đến tập
các quan hệ. Cho trƣớc một đƣờng nối chúng sẽ trả về quan hệ thành viên hoặc
quan hệ chủ chủ nhân của đƣờng nối.( xem hình vẽ 1.1 )
Hình 1.1. Biểu diễn mối liên hệ giữa các quan hệ nhờ các đƣờng nối
Từ hình 1.1 ta có các hàm Owner và Member nhƣ sau:
Owner (l
1
) = TraLuong, Member (l
i
là công thức chọn đƣợc sử dụng để có đƣợc mảnh R
i
. Chú ý
rằng F
i
là một vị từ hội sơ cấp (m
i
).
Ví dụ:
Xét quan hệ DuAn. Chúng ta có thể định nghĩa các mảnh ngang sau đây
dựa vào vị trí dự án :
DuAn
H1
=
ViTri = "Hải Phòng")
(DuAn)
DuAn
H2
=
ViTri = "Hà Nội"
(DuAn)
DuAn
H3
=
ViTri = "TP.Hồ chí Minh"
(DuAn)
Các mảnh thu đƣợc trình bày trong các bảng 1.5, 1.6, 1.7:
DA4
Bảo dƣỡng
310000
TP.Hồ Chí Minh
Bảng 1.7. Mảnh ngang DuAn H3
Số hóa bởi Trung tâm Học liệu – Đại học Thái Nguyên
7
Bây giờ chúng ta có thể định nghĩa mảnh ngang chặt chẽ hơn. Mảnh ngang
R
i
của quan hệ R là một quan hệ chứa các bộ của R thoả mãn vị từ hội sơ cấp m
i
.
Vì vậy cho một tập các vị tập vị từ hội sơ cấp M, số lƣợng các mảnh ngang này
cũng thƣờng đƣợc gọi là các mảnh hội sơ cấp. Vì thế bƣớc đầu tiên của thuật
toán phân mảnh ngang phụ thuộc vào các vị từ sơ cấp.
Một số tính chất quan trọng của tập các vị từ đơn giản là: tính đầy đủ, tính
liên đới và tính cực tiểu.
Tính đầy đủ
Tập các vị từ đơn giản Pr đƣợc gọi là đầy đủ nếu và chỉ nếu xác suất mỗi
ứng dụng truy xuất đến một bộ bất kỳ thuộc về một mảnh hội sơ cấp nào đó
đƣợc định nghĩa theo Pr đều bằng nhau.
Ví dụ :
Xét quan hệ DuAn và các mảnh ngang. Nếu ứng dụng duy nhất truy suất
đến quan hệ DuAn, muốn truy suất của bộ theo vị trí, tập vị trí này là đầy đủ bởi
vì các bộ của mảnh DuAn
thành các mảnh F
i
và F
j
, thì ta có ít nhất một ứng dụng truy xuất đến F
i
và F
j
theo những cách khác nhau. Nói cách khác, vị từ đơn giản phải có liên đới với
vị từ phân mảnh.
Tính cực tiểu
Nếu tất cả các vị từ của tập Pr đều có liên đới thì Pr đƣợc gọi là cực tiểu.
Thuật toán COM_MIN sau đây sẽ cho ta tập vị từ đầy đủ và cực tiểu P’
R
khi đã có tập các vị từ đơn giản P
R
.
Thuật toán COM_MIN
Vào: R là quan hệ, P
R
là
tập các vị từ đơn giản.
Ra: P
R
'
là tập các vị từ đầy đủ.
F: tập các mảnh hội sơ cấp
Begin
{F
i
là mảnh hội sơ cấp theo p
i
}
Do
Begin
Tìm p
j
P
R
sao cho p
j
phân hoạch mảnh F
k
của P
R
' theo Quy tắc1
P
R
'
P
R
'
p
j
P
R
'
P
R
' - p
k
F
F - F
k
End
End-if
End_Begin
Until P
R
' đầy đủ
End. {Kết thúc thuật toán COM_MIN}
Thuật toán bắt đầu tìm một vị từ có liên đới và phân hoạch quan hệ đã cho.
Vòng lặp Do …. Until để thêm các vị từ vào tập này, bảo đảm tính cực tiểu tại
mỗi bƣớc vì thế vào cuối vòng lặp, tập P
R
’ là cực tiểu và đầy đủ.
Bƣớc thứ hai trong quá trình thiết kế phân mảnh ngang nguyên thuỷ là suy
dẫn ra tập các vị từ hội sơ cấp có thể định nghĩa trên các vị từ trong tập P
R
M do
If m
i
mâu thuẫn với I then
M
M
m
i
End If
End For
End. {PHORIZONTAL}
Ví dụ:
Xét hai quan hệ TraLuong và DuAn.
Tập vị từ đơn giản đƣợc sử dụng để phân hoạch quan hệ TraLuong là
p
1
: Luong 30000
p
2
: Luong > 30000
Vì vậy cho ra tập các vị từ đơn giản khởi đầu là P
R
= {p
1
, p
2
}. Áp dụng
2
} theo M nhƣ bảng 1.8 sau:
TrinhDoCM
Luong
Kỹ sƣ cơ khí
Lập trình viên
27000
24000
Bảng 1.8. TraLuong
1 Số hóa bởi Trung tâm Học liệu – Đại học Thái Nguyên
11
Và bảng TraLuong
2
nhƣ bảng 1.9:
TrinhDoCM
Luong
Kỹ sƣ điện
Phân tích và thiết kế hệ thống
40000
70000
Bảng 1.9. TraLuong
2
Chúng ta hãy xét quan hệ DuAn. Giả sử rằng có hai ứng dụng, ứng dụng
, p
3
, p
4
, p
5
} rõ
ràng là đầy đủ và cực tiểu.
Dựa trên Pr’, chúng ta có thể định nghĩa sáu vị trí từ hội sơ cấp sau đây tạo ra M:
m
1
: (ViTri = “Hải Phòng”) (NganSach 200000)
m
2
: (ViTri = “Hải Phòng”) (NganSach > 200000)
m
3
: (ViTri = “Hà Nội”) (NganSach 200000)
Số hóa bởi Trung tâm Học liệu – Đại học Thái Nguyên
12
m
4
: (ViTri = “Hà Nội”) (NganSach >200000)
m
5
: (ViTri = “TP.Hồ Chí Minh ”) (NganSach 200000)
m
p
3
i
3
: p
3
p
1
p
2
i
4
: p
4
p
4
p
5
i
5
: p
5
p
4
i
6
: p
4
p
, …, m
6
} có thể rỗng nhƣng chúng vẫn là các mảnh. Qua ngữ
nghĩa của CSDL không có bằng chứng nào cho thấy rằng các phép kéo theo từ i
s
đến i
11
là đúng.
Số hóa bởi Trung tâm Học liệu – Đại học Thái Nguyên
13
Kết quả của phân mảnh ngang nguyên thuỷ cho DuAn là tạo ra sáu mảnh
F
DuAn
= {DuAn
H1
, DuAn
H2
, DuAn
H3
, DuAn
H4
, DuAn
H5
, DuAn
H6
} của quan hệ
Hà Nội
DuAn
H4
MaDuAn
TenDuAn110
NganSach
ViTri
DA3
CAD/CAM
250000
Hà Nội
DuAn
H6
MaDuAn
TenDuAn
NganSach
ViTri
DA4
Bảo dƣỡng
31000
TP.Hồ Chí Minh
Bảng 1.10. Bảng các vị từ hội sơ cấp
Số hóa bởi Trung tâm Học liệu – Đại học Thái Nguyên
14
) = NhanVien. Thế thì chúng ta có thể nhóm các kỹ sƣ thành hai
nhóm tuỳ theo lƣơng: nhóm có lƣơng từ 30000 USD trở xuống và nhóm có
lƣơng trên 30000 USD. Trƣớc hết chúng ta phân mảnh quan hệ TraLuong thành
2 mảnh thoả mãn yêu cầu trên: TraLuong
1
, TraLuong
2
. Sau đó chúng ta phân
mảnh quan hệ NhanVien theo các mảnh trên, chúng ta sẽ đƣợc 2 mảnh ngang
dẫn xuất là NhanVien
1
, NhanVien
2
hình 1.2.
Hình 1.2. Đồ thị nối giữa các mảnh
TrinhDoCM
Luong
Kỹ sƣ cơ khí
Lập trình viên
27000
24000
Bảng 1.11. TraLuong
1 Số hóa bởi Trung tâm Học liệu – Đại học Thái Nguyên
NV6
NV8
Nguyễn Văn Bổng
M.Smith
Ngô Đình Vinh
Trần Mỹ Lệ
Nguyễn Trƣờng Tam
Kỹ sƣ điện
Phân tích và thiết kế hệ thống
Phân tích và thiết kế hệ thống
Kỹ sƣ điện
Phân tích và thiết kế hệ thống
Bảng 1.14. Mảnh dẫn xuất NhanVien
2
Muốn thực hiện phân mảnh ngang dẫn xuất, chúng ta cần ba thông tin vào:
tập các mảnh của quan hệ chủ (chẳng hạn TraLuong
1
và TraLuong
2
), quan hệ
thành viên, tập các vị từ nối nửa giữa chủ nhân và thành viên (chẳng hạn
NhanVien.TrinhDoCM = TraLuong.TrinhDoCM).
Trong lƣợc đồ CSDL, chúng ta đã gặp nhiều đƣờng nối đến một quan hệ R
(ví dụ nhƣ trong hình 1.1, PhanNhiem có hai đƣờng nối đến). Nhƣ thế có thể có
nhiều cách phân mảnh ngang dẫn xuất cho R. Quyết định chọn cách phân mảnh
nào cần dựa trên hai tiêu chuẩn:
(1) Phân mảnh có đặc tính nối tốt hơn.
Số hóa bởi Trung tâm Học liệu – Đại học Thái Nguyên
Copyright: Tài liệu đại học ©