Bài giảng Cơ sở dữ liệu nâng cao

imestamp – Ordering Protocol) 
 Giao dịch T muốn thực hiện write_item(X): 
1. Nếu Read_TS(X) >TS(T) hoặc Write_TS(X) > TS(T) thì bỏ qua và rollback. 
 44 
2. Nếu điều kiện 1 khơng thỏa mãn, cho phép T write_item(X) và gán lại: 
Write_TS(X) = TS(T). 
 Giao dịch T muốn thực hiện read_item(X): 
1. Nếu Write_TS(X) >TS(T) thì bỏ qua và rollback. 
2. Nếu điều kiện 1 khơng thỏa mãn, cho phép T read_item(X) và gán lại: 
Read_TS(X) = Max{Read_TS(X), TS(T)}. 
5.3.Phục hồi hệ thống dựa vào nhật ký giao dịch (Log-based) 
Một cấu trúc thường được dùng để ghi lại những thay đổi trên cơ sở dữ liệu là sổ ghi lộ trình 
(log). Log là một dãy các mẩu tin lộ trình (log records). Một thao tác cập nhật trên cơ sở dữ liệu sẽ 
được ghi nhận bằng một log record. Một log record kiểu mẫu chứa các trường sau: 
 Định danh giao dịch ( transaction identifier ): định danh duy nhất của giao dịch thực hiện 
hoạt động write. 
 Định danh hạng mục dữ liệu ( Data-item identifier ): định danh duy nhất của hạng mục dữ 
liệu được viết ( thường là vị trí của hạng mục dữ liệu trên đĩa ). 
 Giá trị cũ ( Old value ): giá trị của hạng mục dữ liệu trước thao tác write. 
 Giá trị mới ( New value ): giá trị hạng mục dữ liệu sẽ cĩ sau khi write. 
Cĩ một vài log record đặc biệt mang các ý nghĩa riêng. Bảng sau đây chỉ ra một số loại log record 
và ý nghĩa của chúng: 
LOẠI LOG RECORD Ý NGHĨA 
 Giao dịch Ti đã khởi động. 
Giao dịch Ti đã thực hiện thao tác ghi trên hạng mục dữ liệu Xj, Xj 
cĩ giá trị V1 trước khi ghi và nhận giá trị V2 sau khi ghi. 
 Giao dịch Ti đã bàn giao. 
 Giao dịch Ti đã huỷ bỏ. 
Giao dịch muốn thực hiện một thao tác ghi, trước tiên phải tạo ra một log record cho thao 
tác ghi đĩ (trong log file), trước khi giao dịch thay đổi cơ sở dữ liệu. Như vậy, hệ thống cĩ cơ sở để 
huỷ bỏ (undo) một thay đổi đã được làm trên cơ sở dữ liệu bằng cách sử dụng trường Old-value 
trong log record.Log phải được lưu trong những thiết bị lưu trữ bền. Mỗi một log record mới ngầm 
định sẽ được thêm vào cuối tập tin log. 
5.3.1. Cập nhật trì hỗn cơ sở dữ liệu (Deferred Database Modification) 
 Tư tưởng chính của ký thuật cập nhật trì hỗn là trì hỗn việc cập nhật thực sự vào csdl cho 
đến khi giao dịch đạt tới trạng thái commit. 
 Một giao dịch khơng thể thay đổi csdl trên đĩa cho đến khi nĩ đạt tới trạng thái commit. 
 Một giao dịch khơng thể đạt tới trạng thái commit cho đến khi tất cả các thao tác cập nhật 
của nĩ được ghi lại trên file log (WAL: write – ahead logging). 
 45 
 Các thao tác CSDL sẽ khơng được cập nhật cho đến khi giao dịch hồn tất nên khơng cần 
các thao tác UNDO. Cĩ thể phải REDO trong trường hợp hệ thống lỗi sau khi giao dịch đã 
hồn tất nhưng trước khi tất cả các thay đổi được ghi vào cơ sở dữ liệu.Giao dịch Ti cần 
được REDO nếu trong file log chứa cả hai bản ghi: và . Cũng vì vậy 
mà kỹ thuật phục hồi này cịn được gọi là NO – UNDO/ REDO recovery algorithm. Bảng 
sau chỉ ra các loại bản ghi được tạo ra trong file log: 
Thao tác của giao dịch Bản ghi trong file Log 
Giao dịch Ti bắt đầu Ti,Start 
Ti Write(X) Ti, X, New_Value 
Giao dịch Ti hồn tất Ti, Commit 
Ví dụ: Xét ba mục dữ liệu A, B, C với các giá trị ban đầu lần lượt là 1000, 2000, 700 và hai giao 
dịch T1, T2: 
T0: Read(A) 
Bản ghi trong file log 
 A = A – 50 T0,Start 
 Write(A) T0, A, 950 
 Read(B) T0, B, 2050 
 B = B + 50 T0, Commit 
 Write(B) T1, Start 
 T1, C, 600 
T1: Read(C) T1, Commit 
 C = C – 100 
 Write(C) 
Sau đây là một số tình huống xảy ra và hành động của hệ thống phục hồi sử dụng kỹ thuật cập nhật 
trì hỗn cơ sở dữ liệu: 
Tình huống Hệ thống phục hồi 
Giá trị các mục dữ liệu 
A B C 
Lỗi sau khi T0 vừa thực hiện thao tác 
write B. 
Khơng làm gì. 1000 2000 700 
Lỗi sau khi T1 thực hiện Write(C). REDO(T0) 950 2050 700 
5.3.2. Cập nhật tức thời (Immediate Database Modification) 
Kỹ thuật cập nhật tức thời cho phép các thao tác sửa đổi cơ sở dữ liệu cĩ quyền xuất dữ liệu 
tức thời ra đĩa trong khi giao dịch vẫn cịn ở trong trạng thái hoạt động (active state). 
Trong kỹ thuật này khi giao dịch thực hiện thao tác ghi, cơ sở dữ liệu sẽ được cập nhật tức 
thời mà khơng cần đợi đến khi giao dịch đạt tới trạng thái commit.Các thao tác cập nhật vẫn phải 
được ghi lại trong file log trước khi ghi lại trong csdl. 
 46 
Bảng sau chỉ ra các loại bản ghi được tạo ra trong file log: 
Thao tác của giao dịch Bản ghi trong file Log 
Giao dịch Ti bắt đầu Ti, Start 
Ti Write(X) Ti, X, Old_Value, New_Value 
Giao dịch Ti hồn tất Ti,Commit 
5.4.Kỹ thuật phân trang bĩng (Shadow Paging) 
Kỹ thuật “Phân trang bĩng” cũng là kỹ thuật cho phép phục hồi sau lỗi, nhưng ý tưởng thực 
hiện khác với các kỹ thuật dựa trên sổ ghi lộ trình vừa trình bày ở phần trên. 
Bảng trang và ý nghĩa của nĩ: Khái niệm trang đã nĩi được mượn từ lý thuyết về Hệ điều 
hành. Cách quản lý trang cũng được thừa kế từ đĩ. Giả sử rằng cơ sở dữ liệu được phân thành n 
trang và sự phân bố trên đĩa của chúng cĩ thể khơng theo một thứ tự cụ thể nào cả. Tuy nhiên, phải 
cĩ cách để tìm ra nhanh một trang.Người ta dùng bảng trang cho mục đích này.Bảng trang cĩ n đầu 
vào (entry).Mỗi đầu vào ứng với một trang. Một đầu vào chứa một con trỏ, trỏ đến một trang trên 
đĩa. Đầu vào đầu tiên chỉ đến trang đầu tiên của cơ sở dữ liệu, đầu vào thứ hai chỉ đến trang thứ hai 
... 
Hình 5.6: Bảng trang 
Ý tưởng then chốt của kỹ thuật “Phân trang bĩng” là người ta sẽ duy trì hai bảng trang trong 
suốt chu kỳ sống của giao dịch, một bảng trang gọi là “bảng trang hiện hành” (current page table), 
bảng trang cịn lại gọi là “bảng trang bĩng” (shadow page table). Khi giao dịch khởi động, hai bảng 
trang này giống nhau.Bảng trang bĩng sẽ khơng thay đổi suốt quá trình hoạt động của giao dịch. 
Bảng trang hiện hành sẽ bị thay đổi mỗi khi giao dịch thực hiện tác vụ write. Tất cả các thao tác 
 47 
input và output đều sử dụng bảng trang hiện hành để định vị các trang trong đĩa. Điểm quan trọng 
khác là nên lưu bảng trang bĩng vào thiết bị lưu trữ bền. 
Hình 5.7: Current Page và Shadow Page 
Giả sử giao dịch thực hiện tác vụ write(X) và hạng mục dữ liệu X được chứa trong trang thứ i. 
Tác vụ write được thực thi như sau: 
1. Nếu trang thứ i chưa cĩ trong bộ nhớ chính, thực hiện input(X). 
2. Nếu đây là lệnh ghi được thực hiện lần đầu tiên trên trang thứ i bởi giao dịch, sửa đổi bảng 
trang hiện hành như sau: 
a) Tìm một trang chưa được dùng trên đĩa. 
b) Xố trang vừa được tìm xong ở bước 2.a khỏi danh sách các khung trang tự do. 
c) Sửa lại bảng trang hiện hành sao cho đầu vào thứ i trỏ đến trang mới vừa tìm được trong 
bước 2.a. 
d) Gán giá trị xi cho X trong trang đệm (buffer page). 
Để bàn giao một giao dịch, cần làm các bước sau: 
B1. Đảm bảo rằng tất cả các trang đệm trong bộ nhớ chính đã được giao dịch sửa đổi phải 
được xuất ra đĩa. 
B2. Xuất bảng trang hiện hành ra đĩa (khơng được ghi đè lên trang bĩng). 
B3. Xuất địa chỉ đĩa của bảng trang hiện hành ra vị trí cố định trong thiết bị lưu trữ bền. Vị trí 
này chính là nơi chứa địa chỉ của bảng trang bĩng. Hành động này sẽ ghi đè lên địa chỉ 
của bảng trang bĩng cũ. Như vậy, bảng trang hiện hành sẽ trở thành bảng trang bĩng và 
giao dịch được bàn giao. 
 48 
Nếu sự cố xảy ra trước khi hồn thành bước thứ 3, hệ thống sẽ trở về trạng thái trước khi giao 
dịch được thực hiện.Nếu sự cố xảy ra sau khi bước thứ 3 hồn thành, hiệu quả của giao dịch được 
bảo tồn; khơng cần thực hiện thao tác redo nào cả. 
 Kỹ thuật phân trang bĩng cĩ một số điểm lợi hơn so với các kỹ thuật dựa vào file log: 
o Khơng mất thời gian ghi các log record. 
o Khơi phục sau sự cố nhanh hơn, do khơng cần các thao tác undo hoặc redo. 
 Tuy nhiên kỹ thuật phân trang bĩng lại cĩ nhiều nhược điểm: 
o Tốn chi phí bàn giao, xuất nhiều khối ra đĩa: các khối dữ liệu hiện tại, bảng trang hiện 
hành, địa chỉ của bảng trang hiện hành. Trong khi kỹ thuật dựa vào file log chỉ cần xuất ra 
các log record. 
o Gây ra hiện tượng phân mảnh dữ liệu: Do kỹ thuật phân trang bĩng đổi vị trí của trang khi 
trang này bị sửa đổi. 
o Ngồi ra, kỹ thuật phân trang bĩng sẽ gặp nhiều khĩ khăn khi cần đáp ứng yêu cầu phục vụ 
song song cho nhiều giao dịch. Vì những lý do trên, kỹ thuật phân trang bĩng khơng được 
sử dụng rộng rãi. 
 49 
5.5. Câu hỏi ơn tập chƣơng 5 
5.5.1. Trình bày mơ hình khĩa nhị phân. 
5.5.2. Trình bày các luật trong mơ hình khĩa nhị phân. 
5.5.3. Trình bày mơ hình khĩa đọc – ghi. 
5.5.4. Trình bày các luật trong mơ hình khĩa đọc – ghi. 
5.5.5. Trình bày mơ hình khĩa 2 pha. 
5.5.6. Trình bày về các biến thể của giao thức khĩa hai pha. 
5.5.7. Trình bày hiện tượng Deadlock. 
5.5.8. Trình bày các chiến lược ngăn cản và phát hiện Deadlock. 
5.5.9. Trình bày về giao thức thứ tự nhãn thời gian. 
5.5.10. Phân biệt hai kỹ thuật cập nhật trì hỗn và cập nhật tức thời. 
5.5.11. Trình bày kỹ thuật Shadow Paging. 
5.5.12. Cho hai giao dịch sau: 
 T1: read(A); 
 read(B); 
 if A = 0 then B := B + 1 
 write(B). 
 T2: read(B); 
 read(A); 
 if B = 0 then A := A + 1; 
 write(A). 
Thêm các lệnh lock và unlock vào hai giao dịch trên để đảm bảo chúng tuân theo giao thức 
khĩa hai pha. Việc thực thi hai giao dịch trên cĩ thể sinh ra deadlock khơng? 
 50 
MỘT SỐ ĐỀ THI MẪU 
 51 
Trƣờng Đại Học Hàng Hải Việt Nam 
Khoa Cơng nghệ Thơng tin 
BỘ MƠN HỆ THỐNG THƠNG TIN 
-----***----- 
THI KẾT THƯC HỌC PHẦN 
Tên học phần: CƠ SỞ DỮ LIỆU NÂNG CAO 
Năm học: x 
Đề thi số: Ký duyệt đề: 
x 
Thời gian: 60 phút 
Thang điểm: 100 
PHẦN I – TRẮC NGHIỆM (30 ĐIỂM) 
Câu 1: (10 điểm) 
Cho các quan hệ: 
o Khoa (MKhoa, TenKhoa, DiaDiem) 
o Lop (MaLop, TenLop, SiSo, MaKhoa) 
và truy vấn Q: Hiển thị TenLop của các lớp cĩ SiSo > 50 và thuộc khoa „Kinh Tế‟. Hỏi biểu 
thức đại số quan hệ nào dưới đây đã tối ưu? 
A. 
B. 
C. 
D. 
Câu 2: (10 điểm) 
Cho đồ thị phụ thuộc của lịch biểu S. 
Lịch biểu nào dưới đây là lịch biểu tuần 
tự tương đương với S: 
A. T1  T2  T3  T4 
B. T2  T1  T3  T4 
C. T4  T2  T3  T1 
D. T4  T3  T1  T2 
Câu 3: (10 điểm) 
Lịch biểu nào dưới đây là khả tuần tự: 
A. R1(X), R2(Y), R1(Y), W1(X), R3(Y), W2(Y), W3(Y) 
B. R1(X), R2(Y), R1(Y), W1(X), R3(Z), W2(Y), W3(Z) 
T1 T2 
T3 T4 
 52 
C. R1(X), R2(Z), R1(Y), W1(X), R3(Z), W2(Z), W3(Z) 
D. R1(Z), R2(Z), R1(Y), W1(Z), R3(Y), W2(Z), W3(Y) 
PHẦN II – TỰ LUẬN (70 ĐIỂM) 
Câu 4: (30 điểm) 
 Cho các quan hệ sau: 
 LoaiHang (MaLH, TenLH, MoTa) 
 HangHoa (MaHH, TenHH, HinhThuc, SoLuong, MaLH) 
và truy vấn Q: Lập danh sách gồm MaHH, TenHH của các mặt hàng cĩ số lượng >100 và 
thuộc loại hàng „Mỹ phẩm‟. 
a. Viết biểu thức đại số quan hệ thực hiện truy vấn Q. 
b. Sử dụng phương pháp tối ưu Heuristic để tối ưu hĩa Q. 
Câu 5: (40 điểm) 
 Cho các quan hệ tồn cục: 
 Khoa (MaKhoa, TenKhoa, DiaDiem) 
 Lop (MaLop, TenLop, SiSo, MaKhoa) 
Giả sử Khoa và Lop được phân đoạn ngang theo MaKhoa =1 và MaKhoa = 2 thành Khoa1, 
Khoa2, Lop1, Lop2. 
a. Viết biểu thức đại số quan hệ của các đoạn trên. 
b. Viết biểu thức xây dựng lại của 2 quan hệ tồn cục Khoa, Lop. 
c. Hãy viết truy vấn tồn cục QTC: Lập danh sách gồm TenLop, TenKhoa của các lớp cĩ 
MaKhoa = 2. 
d. Chuyển truy vấn QTC ở câu c thành truy vấn đoạn. 
----------------------------***HẾT***---------------------------- 
Lưu ý: - Khơng sửa, xĩa đề thi, nộp lại đề sau khi thi 
 53 
Trƣờng Đại Học Hàng Hải Việt Nam 
Khoa Cơng nghệ Thơng tin 
BỘ MƠN HỆ THỐNG THƠNG TIN 
-----***----- 
THI KẾT THƯC HỌC PHẦN 
Tên học phần: CƠ SỞ DỮ LIỆU NÂNG CAO 
Năm học: x 
Đề thi số: Ký duyệt đề: 
x 
Thời gian: 60 phút 
Thang điểm: 100 
PHẦN I – TRẮC NGHIỆM (30 ĐIỂM) 
Câu 1: (10 điểm) 
 Cho các quan hệ: 
o Khoa (MKH, TenKH, DiaDiem, MaCNK) 
o Lop (MaLH, TenLH, SiSo, MaKH) 
và truy vấn Q: Hiển thị MaLH, TenLH, SiSo của các lớp thuộc khoa „CNT‟. Hỏi biểu thức 
đại số quan hệ nào dưới đây đã tối ưu? 
A. 
B. 
C. 
D. 
Câu 2: (10 điểm) 
Cho đồ thị phụ thuộc của lịch biểu S. 
Lịch biểu nào dưới đây là lịch biểu tuần 
tự tương đương với S? 
A. T4  T1  T2  T3 
B. T4  T3  T2  T1 
C. T3  T1  T4  T2 
D. T4  T3  T1  T2 
Câu 3: (10 điểm) 
Lịch biểu nào dưới đây là khả tuần tự? 
A. R1(X), R1(Y), R3(Z), R2(Y), W3(Z), W2(Y), W1(X) 
T1 T2 
T3 T4 
 54 
B. R2(Y), R1(X), R1(Y), R3(X), W3(X), W2(Y), W1(X) 
C. R3(X), R2(Y), R1(X), R1(Y), W2(Y), W1(Y), W3(X) 
D. R1(X), R1(Y), R3(X), R2(Y), W2(Y), W1(Y), W3(X) 
PHẦN II – TỰ LUẬN (70 ĐIỂM) 
Câu 4: (30 điểm) 
 Cho các quan hệ sau: 
 HoaDon (MaHD, MaKH, NgayLap) 
 ChiTiet (MaHD, MaHang, SoLuong, GiaBan, ChietKhau) 
và truy vấn Q: Lập danh sách gồm MaHang, SoLuong của các mặt hàng bán vào ngày 
„29/04/2011‟. 
a. Viết biểu thức đại số quan hệ thực hiện truy vấn Q. 
b. Sử dụng phương pháp tối ưu Heuristic để tối ưu hĩa Q. 
Câu 5: (40 điểm) 
 Cho các quan hệ tồn cục: 
 KhoHang (MaKH, TenKH, ViTri) 
 LoaiHang (MaLH, TenLH, MoTa, MaKH) 
Giả sử KhoHang, LoaiHang được phân đoạn ngang theo MaKH =1 và MaKH = 2 thành 
KhoHang1, KhoHang2, LoaiHang1, LoaiHang2. 
a. Viết biểu thức đại số quan hệ của các đoạn trên. 
b. Viết biểu thức xây dựng lại của 2 quan hệ tồn cục DonVi, NhanVien. 
c. Hãy viết truy vấn tồn cục QTC: Lập danh sách gồm TenLH, ViTri của loại hàng cĩ 
MaLH=‟LH01‟ và ở kho hàng cĩ MaKH = 2. 
d. Chuyển truy vấn QTC ở câu c thành truy vấn đoạn. 
----------------------------***HẾT***---------------------------- 
Lưu ý: - Khơng sửa, xĩa đề thi, nộp lại đề sau khi thi 
 55 
Trƣờng Đại Học Hàng Hải Việt Nam 
Khoa Cơng nghệ Thơng tin 
BỘ MƠN HỆ THỐNG THƠNG TIN 
-----***----- 
THI KẾT THƯC HỌC PHẦN 
Tên học phần: CƠ SỞ DỮ LIỆU NÂNG CAO 
Năm học: x 
Đề thi số: Ký duyệt đề: 
x 
Thời gian: 60 phút 
Thang điểm: 100 
PHẦN I – TRẮC NGHIỆM (30 ĐIỂM) 
Câu 1: (10 điểm) 
 Cho các quan hệ: 
o LoaiHang (MLH, TenLH, MoTa) 
o Hang (MaHH, TenHH, HinhThuc, SoLuong, MaLH) 
và truy vấn Q: Hiển thị TenHH của các mặt hàng cĩ SoLuong <10 và thuộc loại hàng „Điện 
Tử‟. Hỏi biểu thức đại số quan hệ nào dưới đây đã tối ưu? 
A. 
B. 
C. 
D. 
Câu 2: (10 điểm) 
Cho đồ thị phụ thuộc của lịch biểu S. 
Lịch biểu nào dưới đây là lịch biểu tuần 
tự tương đương với S: 
A. T3  T1  T2  T4 
B. T3  T2  T1  T4 
C. T4  T2  T3  T1 
D. T4  T3  T1  T2 
Câu 3: (10 điểm) 
Lịch biểu nào dưới đây là khả tuần tự: 
A. R1(X), R2(Y), R1(Y), W2(Y), R3(Y), W1(X), W3(Y) 
T1 T2 
T3 T4 
 56 
B. R1(X), R2(Y), R1(Y), R3(Y), W1(X), W3(Y), W2(Y) 
C. R1(X), R2(Y), R1(Y), R3(Y), W3(Y), W2(Y), W1(X) 
D. R1(Y), R3(Y), R1(X), R2(Y), W3(Y), W2(Y), W1(X) 
PHẦN II – TỰ LUẬN (70 ĐIỂM) 
Câu 4: (30 điểm) 
 Cho các quan hệ sau: 
 Khoa (MKhoa, TenKhoa, DiaDiem) 
 Lop (MaLop, TenLop, SiSo, MaKhoa) 
và truy vấn Q: Lập danh sách gồm MaLop, TenLop của các lớp cĩ sĩ số nhỏ hơn 30 và thuộc 
khoa „Điện tự động‟. 
a. Viết biểu thức đại số quan hệ thực hiện truy vấn Q. 
b. Sử dụng phương pháp tối ưu Heuristic để tối ưu hĩa Q. 
Câu 5: (40 điểm) 
 Cho các quan hệ tồn cục: 
 DonVi (MaDV, TenDV, DiaDiem) 
 NhanVien (MaNV, HoTen, NgaySinh, GioiTinh, Luong, MaDV) 
Giả sử DonVi và NhanVien được phân đoạn ngang theo MaDV = 1 và MaDV = 2 thành 
DonVi1, DonVi2, NhanVien1, NhanVien2. 
a. Viết biểu thức đại số quan hệ của các đoạn trên. 
b. Viết biểu thức xây dựng lại của 2 quan hệ tồn cục DonVi, NhanVien. 
c. Hãy viết truy vấn tồn cục QTC: Lập danh sách gồm HoTen, TenDV của các nhân viên 
thuộc đơn vị cĩ MaDV = 1. 
d. Chuyển truy vấn QTC ở câu c thành truy vấn đoạn. 
----------------------------***HẾT***---------------------------- 
Lưu ý: - Khơng sửa, xĩa đề thi, nộp lại đề sau khi thi 
 57 
Trƣờng Đại Học Hàng Hải Việt Nam 
Khoa Cơng nghệ Thơng tin 
BỘ MƠN HỆ THỐNG THƠNG TIN 
-----***----- 
THI KẾT THƯC HỌC PHẦN 
Tên học phần: CƠ SỞ DỮ LIỆU NÂNG CAO 
Năm học: x 
Đề thi số: Ký duyệt đề: 
x 
Thời gian: 60 phút 
Thang điểm: 100 
PHẦN I – TRẮC NGHIỆM (30 ĐIỂM) 
Câu 1: (10 điểm) 
 Cho các quan hệ: 
o SinhVien (MSV, TenSV, NgaySinh, DiaChi, MaLop) 
o KetQua (MaSV, MaMH, Diem) 
và truy vấn Q: Hiển thị MaMH, Diem của sinh viên „Trần Huyền‟. Hỏi biểu thức đại số 
quan hệ nào dưới đây đã tối ưu? 
A. 
B. 
C. 
D. 
Câu 2: (10 điểm) 
Cho đồ thị phụ thuộc của lịch biểu S. 
Lịch biểu nào dưới đây là lịch biểu tuần 
tự tương đương với S? 
A. T2  T4  T1  T3 
B. T4  T3  T2  T1 
C. T2  T1  T4  T3 
D. T4  T3  T1  T2 
Câu 3: (10 điểm) 
Lịch biểu nào dưới đây là khả tuần tự? 
A. R1(X), R1(Z), R3(Z), R2(Y), W3(Z), W2(Y), W1(Z) 
T1 T2 
T3 T4 
 58 
B. R1(X), R2(Y), R1(Y), R3(X), W3(X), W1(X), W2(Y) 
C. R3(Z), R2(Y), R1(X), R1(Y), W1(X), W3(Z), W2(Y) 
D. R3(X), R1(X), R1(Y), R2(Y), W2(Y), W1(Y), W3(X) 
PHẦN II – TỰ LUẬN (70 ĐIỂM) 
Câu 4: (30 điểm) 
 Cho các quan hệ sau: 
 DonVi(MDV, TenDV, MaNQL, DiaDiem) 
 DuAn (MaDA, TenDA, KinhPhi, MaDV) 
và truy vấn Q: Hiển thị TenDA của các dự án cĩ KinhPhi > 100000 và do đơn vị cĩ TenDV 
= „XD1‟ quản lý. 
a. Viết biểu thức đại số quan hệ thực hiện truy vấn Q. 
b. Sử dụng phương pháp tối ưu Heuristic để tối ưu hĩa Q. 
Câu 5: (40 điểm) 
 Cho quan hệ NhanVien (MaNV, TenNV, DiaChi, Luong, PhuCap, MaNQL, MaPB) 
và thơng tin phân đoạn như sau: NhanVien được phân đoạn dọc thành: 
o NV1 chứa các thơng tin: MaNV, TenNV, DiaChi, MaNQL, MaPB 
o NV2 chứa các thơng tin: MaNV, Luong, PhuCap 
NV1 được phân đoạn ngang thành: 
o NV11: Những nhân viên cĩ MaPB < 5. 
o NV12: Những nhân viên cĩ MaPB 5. 
a. Viết biểu thức đại số quan hệ của các đoạn trên. Viết biểu thức xây dựng lại của 2 quan 
hệ tồn cục NhanVien. 
b. Hãy viết truy vấn tồn cục QTC: Lập danh sách gồm TenNV, Luong, PhuCap của các 
nhân viên cĩ MaPB = 8. Chuyển truy vấn QTC ở câu c thành truy vấn đoạn. 
----------------------------***HẾT***---------------------------- 
Lưu ý: - Khơng sửa, xĩa đề thi, nộp lại đề sau khi thi
 59 
Trƣờng Đại Học Hàng Hải Việt Nam 
Khoa Cơng nghệ Thơng tin 
BỘ MƠN HỆ THỐNG THƠNG TIN 
-----***----- 
THI KẾT THƯC HỌC PHẦN 
Tên học phần: CƠ SỞ DỮ LIỆU NÂNG CAO 
Năm học: x 
Đề thi số: Ký duyệt đề: 
x 
Thời gian: 60 phút 
Thang điểm: 100 
PHẦN I – TRẮC NGHIỆM (30 ĐIỂM) 
Câu 1: (10 điểm) 
 Cho các quan hệ: 
o DonVi (MDV, TenDV, DiaDiem) 
o NhanVien (MaNV, HoTen, NgaySinh, GioiTinh, Luong, MaDV) 
và truy vấn Q: Hiển thị HoTen của các nhân viên nữ thuộc đơn vị „PKD‟. Hỏi biểu thức đại 
số quan hệ nào dưới đây đã tối ưu? 
A. 
B. 
C. 
D. 
Câu 2: (10 điểm) 
Cho đồ thị phụ thuộc của lịch biểu S. 
Lịch biểu nào dưới đây là lịch biểu tuần 
tự tương đương với S: 
A. T3  T1  T2  T4 
B. T3  T2  T1  T4 
C. T3  T1  T4  T2 
D. T4  T3  T1  T2 
Câu 3: (10 điểm) 
Lịch biểu nào dưới đây là khả tuần tự: 
A. R2(X), R1(X), R1(Y), R3(Z), W3(Z), W2(X), W1(X) 
B. R1(Y), R2(X), R1(X), R3(Z), W3(Z), W2(X), W1(X) 
T1 T2 
T3 T4 
 60 
C. R1(Z), R2(X), R1(Y), W2(X), R3(Z), W1(Y), W3(Z) 
D. R1(Y), R2(X), R1(X), R3(Z), W1(X), W3(Z), W2(X) 
PHẦN II – TỰ LUẬN (70 ĐIỂM) 
Câu 4: (30 điểm) 
 Cho các quan hệ sau: 
 DonHang (MaDH, MaNV, MaNhaCC, NgayLap, TongTien) 
 ChiTiet (MaDH, MaHang, SoLuong, DonGia, ChietKhau) 
và truy vấn Q: Lập danh sách gồm MaHang, SoLuong của các mặt hàng cĩ DonGia > 90000 
trong đơn hàng cĩ NgayLap = „29/04/2011‟. 
a. Viết biểu thức đại số quan hệ thực hiện truy vấn Q. 
b. Sử dụng phương pháp tối ưu Heuristic để tối ưu hĩa Q. 
Câu 5: (40 điểm) 
 Cho các quan hệ tồn cục: 
 DonVi(MaDV, TenDV, MaNQL) 
 DuAn (MaDA, TenDA, KinhPhi, MaDV) 
Giả sử DonVi và DuAn được phân đoạn ngang theo MaDV = 1 và MaDV = 2 thành 
DonVi1, DonVi2, DuAn1, DuAn2. 
a. Viết biểu thức đại số quan hệ của các đoạn trên. 
b. Viết biểu thức xây dựng lại của 2 quan hệ tồn cục DonVi, DuAn. 
c. Hãy viết truy vấn tồn cục QTC: Lập danh sách gồm TenDA, TenDV của các dự án cĩ 
KinhPhi > 900000 và do đơn vị cĩ MaDV = 1 quản lý. 
d. Chuyển truy vấn QTC ở câu c thành truy vấn đoạn. 
----------------------------***HẾT***---------------------------- 
Lưu ý: - Khơng sửa, xĩa đề thi, nộp lại đề sau khi thi