Giáo trình Cơ sở dữ liệu nâng cao - Trường Đại học Hàng Hải
TRƢỜNG ĐẠI HỌC HÀNG HẢI
KHOA CÔNG NGHỆ THÔNG TIN
BỘ MÔN HỆ THỐNG THÔNG TIN
-----***-----
BÀI GIẢNG
CƠ SỞ DỮ LIỆU NÂNG CAO
TÊN HỌC PHẦN
MÃ HỌC PHẦN
: CƠ SỞ DỮ LIỆU NÂNG CAO
: 17406
TRÌNH ĐỘ ĐÀO TẠO : ĐẠI HỌC CHÍNH QUY
DÙNG CHO SV NGÀNH: CÔNG NGHỆ THÔNG TIN
HẢI PHÕNG – 2011
MỤC LỤC
CHƢƠNG 1: CÁC MÔ HÌNH DỮ LIỆU ........................................................................................7
1.1. Các mô hình dữ liệu..................................................................................................................7
1.1.1. Mô hình thực thể - quan hệ................................................................................................7
1.1.2. Mô hình mạng....................................................................................................................8
1.1.3. Mô hình phân cấp ..............................................................................................................8
1.2. Tóm tắt về cơ sở dữ liệu quan hệ..............................................................................................9
1.2.1. Các khái niệm ....................................................................................................................9
1.2.2. Tóm tắt các phép toán đại số quan hệ..............................................................................10
1.2.3. Phương pháp xây dựng cơ sở dữ liệu quan hệ.................................................................10
1.3. Một số mô hình cơ sở dữ liệu mở rộng...................................................................................11
1.3.1. Mô hình cơ sở dữ liệu thời gian.......................................................................................11
1.3.2. Mô hình cơ sở dữ liệu tích cực........................................................................................12
1.4. Câu hỏi ôn tập chương 1.........................................................................................................14
CHƢƠNG 2: TỐI ƢU HÓA TRUY VẤN......................................................................................15
2.1. Giới thiệu ................................................................................................................................15
2.2. Các phép biến đổi tương đương..............................................................................................15
2.3. Thuật toán tối ưu hóa cây đại số quan hệ................................................................................17
2.3.1. Thuật toán........................................................................................................................17
2.3.2. Ví dụ ................................................................................................................................17
2.4. Câu hỏi ôn tập chương 2.........................................................................................................19
CHƢƠNG 3: GIAO DỊCH TRONG CƠ SỞ DỮ LIỆU ...............................................................20
3.1. Giới thiệu ................................................................................................................................20
3.2. Các tính chất của giao dịch .....................................................................................................20
3.3. Các trạng thái của giao dịch....................................................................................................21
3.4. Lịch biểu .................................................................................................................................21
3.5. Tính khả tuần tự của lịch biểu.................................................................................................22
3.6. Thuật toán kiểm tra tính khả tuần tự của lịch biểu..................................................................23
3.7. Câu hỏi ôn tập chương 3.........................................................................................................24
4.1. Các giao thức dựa vào khóa....................................................................................................25
4.1.1. Mô hình khóa nhị phân....................................................................................................25
4.1.2. Mô hình khóa đọc – ghi (chia sẻ – độc quyền)................................................................25
2
4.1.3. Giao thức khóa 2 pha.......................................................................................................27
4.1.4. Deadlock..........................................................................................................................29
4.2. Giao thức thứ tự nhãn thời gian (Timestamp – Ordering protocol)........................................31
4.2.1 Nhãn thời gian (Timestamp).............................................................................................31
4.2.2. Giao thức thứ tự nhãn thời gian (Timestamp – Ordering Protocol) ................................31
4.3. Phục hồi hệ thống dựa vào nhật ký giao dịch (Log-based).....................................................32
4.3.1 Cập nhật trì hoãn cơ sở dữ liệu (Deferred Database Modification) .................................32
4.3.2. Cập nhật tức thời (Immediate Database Modification) ...................................................34
4.4. Kỹ thuật phân trang bóng (Shadow Paging)...........................................................................34
4.5. Câu hỏi ôn tập chương 4.........................................................................................................37
CHƢƠNG 5: CƠ SỞ DỮ LIỆU PHÂN TÁN ................................................................................38
5.1. Giới thiệu ................................................................................................................................38
5.2. Ưu nhược điểm của cơ sở dữ liệu phân tán ............................................................................39
5.3. Cấu trúc chung của một cơ sở dữ liệu phân tán......................................................................39
5.4. Phân đoạn dữ liệu (Fragmentation).........................................................................................40
5.4.1. Phân đoạn ngang..............................................................................................................42
5.4.2. Phân đoạn ngang dẫn xuất...............................................................................................42
5.4.3. Phân đoạn dọc..................................................................................................................43
5.4.4. Phân đoạn hỗn hợp ..........................................................................................................43
5.5. Thiết kế định vị dữ liệu...........................................................................................................44
5.6. Biến đổi truy vấn toàn cục thành truy vấn đoạn .....................................................................45
5.7. Câu hỏi ôn tập chương 5.........................................................................................................47
MỘT SỐ ĐỀ THI MẪU...................................................................................................................48
3
Tên học phần: Cơ sở dữ liệu nâng cao
Bộ môn phụ trách giảng dạy: Hệ thống Thông tin
Mã học phần: 17406
Loại học phần: 2
Khoa phụ trách: CNTT.
Tổng số TC: 2
Tổng số tiết Lý thuyết
45 30
Thực hành/Xemina
Tự học
Bài tập lớn
Đồ án môn học
không
15
0
không
Học phần học trƣớc: Cơ sở dữ liệu.
Học phần tiên quyết: Cơ sở dữ liệu.
Học phần song song: Không yêu cầu.
Mục tiêu của học phần:
Cung cấp cho sinh viên những kiến thức nâng cao về cơ sở dữ liệu quan hệ, kiến thức về hệ cơ
sở dữ liệu phân tán.
Nội dung chủ yếu:
Các vấn đề nâng cao về cơ sở dữ liệu: Các mô hình dữ liệu mở rộng, tối ưu hóa câu hỏi truy
vấn, quản lý giao dịch trong cơ sở dữ liệu, điều khiển tương tranh và phục hồi hệ thống; Các vấn đề
về cơ sở dữ liệu phân tán: kiến trúc hệ cơ sở dữ liệu phân tán, thiết kế cơ sở dữ liệu phân tán, xử lý
truy vấn phân tán.
Nội dung chi tiết:
PHÂN PHỐI SỐ TIẾT
TÊN CHƢƠNG MỤC
TS LT TH BT KT
Chƣơng 1: Các mô hình dữ liệu
1.1. Các mô hình dữ liệu
6
6
7
4
5
3
2
1.2. Tóm tắt về cơ sở dữ liệu quan hệ
1.3. Một số mô hình cơ sở dữ liệu mở rộng
Chƣơng 2: Tối ƣu hóa truy vấn
2.1. Giới thiệu
1
1
2.2. Các phép biến đổi tương đương
2.3. Thuật toán tối ưu hóa cây đại số quan hệ
Chƣơng 3: Giao dịch trong cơ sở dữ liệu
3.1. Giới thiệu
3
4
PHÂN PHỐI SỐ TIẾT
TÊN CHƢƠNG MỤC
TS LT TH BT KT
3.2. Các tính chất của giao dịch
3.3. Các trạng thái của giao dịch
3.4. Lịch biểu
3.5. Tính khả tuần tự của lịch biểu
3.6. Thuật toán kiểm tra tính khả tuần tự của lịch biểu
Chƣơng 4: Điều khiển đồng thời và khôi phục hệ thống
4.1. Các giao thức dựa vào khóa
6
6
4.2. Giao thức thứ tự nhãn thời gian
4.3. Phục hồi hệ thống dựa vào nhật ký giao dịch (Log-based)
4.4. Kỹ thuật phân trang bóng (Shadow Paging)
Chƣơng 5: Cơ sở dữ liệu phân tán
5.1. Giới thiệu
20
9
10
1
5.2. Ưu nhược điểm của cơ sở dữ liệu phân tán
5.3. Cấu trúc chung của một cơ sở dữ liệu phân tán
5.4. Phân đoạn dữ liệu (Fragmentation)
5.5. Thiết kế định vị dữ liệu
5.6. Biến đổi truy vấn toàn cục thành truy vấn đoạn
Nhiệm vụ của sinh viên:
Tham dự các buổi học lý thuyết và thực hành, làm các bài tập được giao, làm các bài thi giữa
học phần và bài thi kết thúc học phần theo đúng quy định.
Tài liệu học tập:
1. Nguyễn Xuân Huy, Giáo trình về cơ sở dữ liệu, Đại học Quốc Gia Hà Nội, 2000.
2. Raghu Ramakrishnan, Database Management Systems, McGraw – Hill, 1998.
3. Silberschatz, Korth, Sudarshan, Database System Concepts, 4th Edition, McGraw-Hill,
2001.
5
Hình thức và tiêu chuẩn đánh giá sinh viên:
- Hình thức thi: thi viết.
- Tiêu chuẩn đánh giá sinh viên: căn cứ vào sự tham gia học tập của sinh viên trong các buổi
học lý thuyết và thực hành, kết quả làm các bài tập được giao, kết quả của các bài thi giữa học phần
và bài thi kết thúc học phần.
Thang điểm: Thang điểm chữ A, B, C, D, F.
Điểm đánh giá học phần: Z = 0,3X + 0,7Y.
Bài giảng này là tài liệu chính thức và thống nhất của Bộ môn Hệ thống Thông tin, Khoa
Công nghệ Thông tin và được dùng để giảng dạy cho sinh viên.
Ngày phê duyệt:
Trƣởng Bộ môn
/
/
6
CHƢƠNG 1: CÁC MÔ HÌNH DỮ LIỆU
1.1. Các mô hình dữ liệu
Mô hình dữ liệu là sự trừu tượng hóa môi trường thực, đó là tập hợp các mô tả dữ liệu ở
mức cao mà không quan tâm đến chi tiết lưu trữ dữ liệu ở mức thấp. Trong phạm vi môn học ta xét
các mô hình dữ liệu sau: Mô hình thực thể - quan hệ, mô hình mạng, mô hình phân cấp, mô hình
hướng đối tượng.
1.1.1. Mô hình thực thể - quan hệ
Mô hình thực thể - liên kết (ER Model) là thể hiện logic của dữ liệu trong tổ chức hay trong
công tác kinh doanh. Nó mô tả thế giới thực gồm những đối tượng cơ bản được gọi là các thực thể
và những quan hệ giữa chúng.
Sơ đồ thực thể quan hệ (Entity Relationship Diagram - ERD) là thể hiện đồ họa của ER.
Thực thể là thành phần của thế giới thực, có khả năng tồn tại độc lập. Ví dụ một tài khoản ngân
hàng là một thực thể (Entity). Một nhóm các thực thể cùng chung một số tính chất, một số đặc
trưng cơ bản tạo ra một tập thực thể (Entity Set). Ví dụ tập các nhân viên trong một cơ quan.
Thuộc tính dùng để mô tả thực thể, ví dụ: Với thực thể khách hàng thì thuộc tính là: tên khách
hàng, địa chỉ, số điện thoại, … Thuộc tính có thể nhận một hoặc nhiều giá trị.
Các tập thực thể có thể liên kết với nhau theo mối liên kết 1 – 1, 1 – n, n – m.
Hình 1.1: Ví dụ mô hình ER (Crow’s Foot)
7
1.1.2. Mô hình mạng
Mô hình mạng (Network Model) là mô hình thực thể - quan hệ trong đó các mối liên hệ bị
hạn chế trong kiểu nhị phân và nhiều – một. Như vậy chúng ta có thể dùng một đồ thị có hướng cho
các dữ liệu. Ở vị trí của các tập thực thể, mô hình mạng đưa ra kiểu bản ghi (record type). Một kiểu
bản ghi là tên gán cho một tập các bản ghi (record). Bản ghi được cấu tạo bởi các trường (field)
chứa các giá trị cơ bản như số nguyên, chuỗi kí tự, … Tập các tên trường và kiểu của chúng tạo nên
khuôn dạng bản ghi (record format). Nếu so sánh với mô hình quan hệ ta thấy sự tương ứng như
sau:
Mô hình mạng
Kiểu bản ghi
Bản ghi
Mô hình quan hệ
Tên quan hệ
Bộ của quan hệ
Khuôn dạng bản ghi Lược đồ quan hệ
Đường nối (Link): dùng để biểu diễn mối quan hệ nhiều – một giữa hai đối tượng. Chúng ta
dùng đồ thị có hướng, gọi là mạng, đó thực sự là một sơ đồ thực thể - quan hệ đã được đơn giản
hóa để biểu diễn các kiểu bản ghi và đường nối giữa chúng. Các nút tương ứng với các kiểu bản
ghi.
Biểu diễn tập thực thể trong mô hình mạng: Các tập thực thể được biểu diễn bằng các kiểu bản
ghi; thuộc tính của tập thực thể trở thành các trường của khuôn dạng bản ghi.
Biểu diễn các mối quan hệ: Chỉ những mối quan hệ một – nhiều mới có thể biểu diễn trực tiếp
bằng các đường nối. Tuy nhiên ta có thể dùng một số phương pháp để biểu diễn một mối quan
hệ bất kỳ.
1.1.3. Mô hình phân cấp
Trong mô hình này dữ liệu được tổ chức thành cấu trúc cây, các nút (node) là tập các thực thể,
các cành là các mối quan hệ giữa hai nút theo mối quan hệ nhẩt định, cứng nhắc. Mô hình phân cấp:
Là mô hình dữ liệu trong đó các bản ghi được sắp xếp theo cấu trúc top-down(tree).
Một nút con chỉ liên kết tới một nút cha.
Tập dữ liệu được tổ chức theo cấu trúc của mô hình dữ liệu phân cấp gọi là CSDL phân cấp.
Hình 1.2 là một ví dụ về mô hình phân cấp quản lý nhân sự của một công ty.
8
Phòng ban
Nhân viên
Dự Án
Kỹ Năng
Người Thân
Thiết Bị
Hình 1.2: Ví dụ mô hình phân cấp trong quản lý nhân sự
1.2. Tóm tắt về cơ sở dữ liệu quan hệ
1.2.1. Các khái niệm
Cho Ω ={A1,A2,… ,An} là một tập hữu hạn các thuộc tính, khác rỗng và các phần tử không
nhất thiết phân biệt nhau. Mỗi thuộc tính Ai có một miền giá trị xác định D(Ai) = Dom(Ai).Tích Đề
các của các miền Dom(A1), Dom(A2), …, Dom(An) được biểu diễn như sau:
Dom(A1) × Dom(A2) × … × Dom(An) = {(a1, a2, …, an) | ai Ai, i = 1 ÷ n}.
Nói rằng R là một quan hệ trên tập Ω ↔ R Dom(A1) × Dom(A2) × … × Dom(An).
Ví dụ: Ω = {A1, A2}, Dom(A1) = {0, 1} và Dom(A2) = {a, b, c}
Như vậy tích Đề các Dom(A1) × Dom(A2) = {(0,a), (0,b), (0,c), (1,a), (1,b), (1,c)}. Khi đó tập R =
{(0,a),(0,b)} là một quan hệ trên tập Ω.
Trong mô hình cơ sở dữ liệu quan hệ người ta thường biểu diễn một quan hệ trên tập các
thuộc tính Ω bằng một bảng hai chiều. Các thuộc tính của quan hệ là các cột A1,A2,… ,An. Các
hàng của quan hệ gọi là các bộ, kí hiệu r R(Ω).
Ví dụ: Bảng sau thể hiện quan hệ Can_bo bao gồm các thuộc tính Ma_So, Ho_ten, Ngay_sinh,
Que_quan, Chuc_vu
Cán Bộ
Ma_so
Ho_ten
Ngay_sinh Que_quan
Chuc_vu
t1 0001
Lê Thanh Hằng 12/04/1970 Quảng Ninh Trưởng phòng
t2 0002 Hoàng Văn Cảnh 15/10/1981 Nam Định
t3 0003 Trần Bình Dương 20/01/1979 Ninh Bình
Nhân viên
Nhân viên
Khoá của một quan hệ là một hoặc một tập thuộc tính dùng để định tên duy nhất các bộ
trong quan hệ.
9
Khoá ngoại: Trong cơ sở dữ liệu có thể có rất nhiều các quan hệ, và đôi khi quan hệ này có
những thuộc tính lấy dữ liệu từ một quan hệ khác, hay nói các khác là các thuộc tính này có miền
giá trị là những giá trị được lưu tại một hoặc nhiều trường trong quan hệ khác hoặc chính nó.
1.2.2. Tóm tắt các phép toán đại số quan hệ
Phép chọn (Selection): E(R)= {t | t R & t[E]= “True”}
Phép chiếu (Projection): X (R) = {t[X] | t R}
Phép hợp (Union): R1R2 ={t | t R1 t R2}
Phép giao (Intersection): R1R2 ={t | t R1 t R2}
Phép trừ (Minus): R1 – R2 = {t | t R1 t R2}
Tích đề các (Cartesian Product): R × S = {t | t = (a,b) a R b S}
Phép kết nối (Join):
Kết nối tự nhiên (Natural Join): R * S = P(Ω ∑) = { t[Ω ∑] | t[Ω ∑]R = t[Ω ∑]S}
Phép chia (Division): R ÷ S = {t | sS, (t,s) R}
1.2.3. Phƣơng pháp xây dựng cơ sở dữ liệu quan hệ
1.2.3.1. Phương pháp Top – Down
Phân tích thực tiễn:
o Xác định các đối tượng có trong cơ sở dữ liệu
o Các mối liên hệ giữa chúng
o Các quy tắc quản lý
Xây dựng lược đồ liên kết thực thể - ER:
o Kiểu thực thể: Một lớp đối tượng
o Kiểu liên kết: Một lớp các mối liên hệ: 1 – 1, 1 – n, n – m
o Dùng thuật toán chuyển đổi từ lược đồ ER sang lược đồ quan hệ.
1.2.3.2. Phương pháp Bottom – Up
Tạo ra lược đồ phổ quát R(A1, A2, …, An)
Tìm ra tập phụ thuộc hàm F
Tách R thành các Ri đều ở dạng chuẩn BC (BCNF)
10
1.3. Một số mô hình cơ sở dữ liệu mở rộng
1.3.1. Mô hình cơ sở dữ liệu thời gian
Cơ sở dữ liệu thời gian (Temporal database) là cơ sở dữ liệu được xây dựng dựa trên khía
cạnh thời gian. Ví dụ:
o CSDL chăm sóc sức khỏe: bệnh án, lịch sử bệnh.
o Bảo hiểm: bảo hiểm xe, liên quan đến đền bù, sửa chữa.
o Các hệ thống đặt vé, giữ chỗ …
Valid time, transaction time, bitemporal time:
o Valid Time: Thời gian sự việc xảy ra trong thực tế.
. VST: Valid Start Time: Thời gian bắt đầu có hiệu lực.
. VET: Valid End Time: Thời gian kết thúc hiệu lực.
o Transaction Time: Thời gian khi sự thay đổi được lưu trong CSDL.
. TST: Transaction Start Time: Thời gian giao dịch được tạo ra.
. TET: Transaction End Time: Thời gian giao dịch bị hủy bỏ.
o Bitemporal time: Valid time + Transaction time.
Các kiểu cập nhật:
o Proactive: Thông tin được cập nhật vào cơ sở dữ liệu trước khi nó xảy ra trong thế
giới thực.
o Retroactive: Thông tin được cập nhật vào cơ sở dữ liệu sau khi nó xảy ra trong thế
giới thực.
o Simultaneous: Thông tin được cập nhật vào cơ sở dữ liệu cùng thời điểm nó xảy ra
trong thế giới thực.
Ví dụ:
o 03/04/1975: John ra đời (con trai của Jack và Jane).
o 04/04/1975: Jack đăng ký khai sinh cho con trai ở Smallville City.
o 26/08/1994: John chuyển đến sống ở Bigtown (sau khi tốt nghiệp trung học) nhưng
quên chưa khai báo thay đổi địa chỉ nơi ở mới.
o 27/12/1994: John khai báo địa chỉ nơi ở mới.
o 01/04/2001: John bị tai nạn. Nhân viên điều tra báo John mất cùng ngày.
Với mô hình cơ sở dữ liệu truyền thống: Ta có bảng Person lưu thông tin nhân khẩu: Person
(Name, Address):
11
Với mô hình cơ sở dữ liệu thời gian (Valid time):
o 3/4/1975, John chào đời (Jack đăng ký khai sinh cho con vào ngày 4/4/1975):
Person(John, Smallville, 3-Apr-1975, ∞).
o 27/12/1994, John khai báo địa chỉ nơi ở mới (John sống ở Bigtown từ 26/8/1994):
Person(John, Smallville, 3-Apr-1975, 26-Aug-1994)
Person (John, Big Town, 26-Aug-1994, ∞).
o 1/4/2001, John mất:
Person(John, Smallville, 3-Apr-1975, 26-Aug-1994)
Person(John, Bigtown, 26-Aug-1994, 1-Apr-2001)
1.3.2. Mô hình cơ sở dữ liệu tích cực
Với cơ sở dữ liệu thụ động: Mọi hành động trên dữ liệu kết quả chỉ thực hiện với các
chương trình ứng dụng được chỉ ra nhưng với cơ sở dữ liệu tích cực: Các hành động có thể
xảy ra tự động trong trả lời để giám sát các sự kiện và đảm bảo tính toàn vẹn của dữ liệu. Ví
dụ một CSDL tích cực có thể được sử dụng để giám sát nhiệt độ của ngành công nghiệp
luyện kim:
o Làm tăng dự tích hợp các ràng buộc.
o Tự động bảo vệ dữ liệu nhận được.
o Bảo vệ các bảng sao nhất quán.
Cơ sở dữ liệu tích cực là một CSDL chứa các qui tắc tích cực (hoặc các qui tắc gây nên),
chủ yếu là các qui tắc dạng ECA (Event – Condition – Action).
Quy tắc ECA: có tác dụng đảm bảo tính toàn vẹn của cơ sở dữ liệu. Một quy tắc được cấu
tạo bởi 3 thành phần:
o Event: Sự kiện làm kích hoạt quy tắc. Chúng cũng có thể là sự kiện thời gian hoặc
một kiểu sự kiện mở rộng khác.
12
o Condition: Điều kiện làm vi phạm tính toàn vẹn của dữ liệu.
o Action: Một hành động nhằm loại bỏ sự vi phạm về tính toàn vẹn của dữ liệu. Hành
động thường là một câu truy vấn, hoặc một chương trình mở rộng được thực hiện
một cách tự động.
Mô hình cơ sở dữ liệu tích cực còn được gọi là mô hình ECA.
Trong cơ sở dữ liệu quan hệ các quy tắc tích cực được viết dưới dạng các Trigger. Ví dụ:
Với hai bảng:
o DonVi (MaDV, TenDV, TongLuong, MaNQL)
o NhanVien (MaNV, TenNV, NgaySinh, GioiTinh, Luong, MaDV)
Một quy tắc sẽ có dạng như sau:
o Event: Hành động Insert một bản ghi trong bảng NhanVien.
o Condition:
. Giá trị của MaDV được thêm vào không có trong tập giá trị hiện có trong
bảng DonVi.
. Nếu MaDV được thêm vào là đã có trong bảng DonVi Tổng lương của
đơn vị đó cần được thay đổi.
o Action:
. Sửa đổi sai sót do sự kiện gây ra.
. Thông báo lỗi cho người dùng.
Khi thiết kế và cài đặt cơ sở dữ liệu tích cực cần lưu ý một số vấn đề sau:
o Cần phân tích và xác định đúng đắn các ràng buộc dữ liệu, từ đó mới có tập quy tắc
phục vụ đầy đủ cho cơ sở dữ liệu.
o Phải có phương pháp để các quy tắc có thể được kích hoạt trước hay sau khi sự kiện
xảy ra.
o Tập các quy tắc của một cơ sở dữ liệu tích cực thường rất lớn nên tại một thời điểm
không phải tất cả các quy tắc đều được áp dụng, do vậy mỗi quy tắc cần phải có hai
trạng thái: Active, Deactive.
13
1.4. Câu hỏi ôn tập chƣơng 1
Mô hình cơ sở dữ liệu là gì?
Trình bày các khái niệm lược đồ quan hệ, quan hệ, trường, thuộc tính trong mô hình cơ sở
dữ liệu quan hệ.
Trình bày các khái niệm khóa, siêu khóa, khóa chính, khóa ngoại, thuộc tính khóa trong mô
hình cơ sở dữ liệu quan hệ.
Trình bày các loại ràng buộc trong mô hình cơ sở dữ liệu quan hệ.
Trình bày các phép toán đại số quan hệ: phép chọn, phép chiếu, phép hợp, phép giao, phép
trừ, phép kết nối, phép chia.
Mô hình cơ sở dữ liệu thời gian là gì?
Phân biệt các kiểu thời gian: Valid time, Transaction time, Bitemporal time?
Mô hình cơ sở dữ liệu tích cực là gì?
Quy tắc ECA là gì?
14
CHƢƠNG 2: TỐI ƢU HÓA TRUY VẤN
2.1. Giới thiệu
Trong chương này chúng ta sẽ nghiên cứu một kỹ thuật tối ưu hóa vấn tin cơ bản. Khi diễn
tả truy vấn bằng một ngôn ngữ khai báo, như ngôn ngữ vấn tin quan hệ, hệ thống cơ sở dữ liệu rất
khó thực thi nhanh chóng. Với nhiều cách cài đặt một câu vấn tin, giai đoạn tối ưu hóa phải chọn ra
được một cách cài đặt tốt nhất.
Quá trình xử lý một truy vấn:
Bước 1:
o Bộ quét: Truy vấn được bằng một biểu thức. Bộ quét sẽ duyệt truy vấn để biết truy
vấn được viết bằng ngôn ngữ nào.
o Bộ kiểm tra: Kiểm tra cú pháp của truy vấn xem có hợp lệ hay không.
o Xác nhận tính hợp lệ (các quan hệ, thuộc tính sử dụng trong truy vấn đã được khai
báo hay chưa? Sau bước 1 truy vấn sẽ được biểu diễn bằng một biểu thức đại số
quan hệ)
Bước 2:
o Bộ tối ưu: Tìm ra phương pháp thực hiện tối ưu cho truy vấn.
o Sau bước này sẽ cho ra một biểu thức đại số quan hệ với chi phí thực hiện nhỏ nhất.
Bước 3:
o Bộ tạo mã sẽ tạo ra chương trình bằng ngôn ngữ trong để thực hiện truy vấn.
o Thực thi chương trình để lấy về kết quả.
2.2. Các phép biến đổi tƣơng đƣơng
Các truy vấn được viết bằng các ngôn ngữ bậc cao, ví dụ SQL, sau bước 1 của quá trình xử
lý truy vấn, truy vấn được biểu diễn bằng biểu thức đại số quan hệ. Ví dụ:
SELECT
FROM
*
R
E
↔
E(R)
WHERE
SELECT
A1, A2, …, Ai
FROM R
↔
↔
F (R)
SELECT
FROM R, S
WHERE
*
F
15
Tối ưu bằng biến đổi biểu thức đại số quan hệ: Biến đổi thứ tự thực hiện các phép toán của
biểu thức đại số quan hệ sao cho các phép toán một ngôi được thực hiện trước các phép toán
hai ngôi, do các phép toán chiếu, chọn thì có chi phí nhỏ hơn so với các phép kết nối, tích đề
các.
Một số phép biến đổi tương đương:
o Tách điều kiện trong phép chọn:
o Tính chất giao hoán của phép chọn:
o Dãy các phép chiếu liên tiếp:
o Phép chọn – phép tích đề các và phép kết nối :
.
.
o Tính chất giao hoán của phép kết nối :
o Tính chất giao hoán của phép kết nối tự nhiên:
o Tính chất kết hợp của phép kết nối tự nhiên:
o Tính chất kết hợp của phép kết nối :
.
, nếu các thuộc tính trong
chỉ thuộc và .
o Phép chọn và phép kết nối :
. , nếu các thuộc tính trong 0 chỉ thuộc .
.
nếu các thuộc tính trong chỉ
thuộc , các thuộc tính trong 2 chỉ thuộc .
o Phép chiếu và phép kết nối :
.
, nếu:
Các thuộc tính trong chỉ thuộc .
Các thuộc tính trong chỉ thuộc .
16
Các thuộc tính trong đều có trong và .
.
Các thuộc tính trong chỉ thuộc .
Các thuộc tính trong chỉ thuộc .
Các thuộc tính trong chỉ có trong , liên quan đến nhưng không
thuộc
.
Các thuộc tính trong chỉ có trong , liên quan đến nhưng không
thuộc
.
o Phép hợp – Phép giao và phép trừ
. Tính chất giao hoán:
. Tính chất kết hợp:
. Tính chất phân phối của phép chọn qua phép hợp – giao – trừ:
. Tính chất phân phối của phép chiếu qua phép hợp:
2.3. Thuật toán tối ƣu hóa cây đại số quan hệ
2.3.1. Thuật toán
Bước 1: Biểu diễn truy vấn dưới dạng cây với lá là các quan hệ, đỉnh trong là các phép toán
đại số quan hệ.
Bước 2: Áp dụng các phép biến đổi tương đương đẩy các phép toán một ngôi xuống dưới
các phép toán hai ngôi.
Bước 3: Thêm vào các phép chiếu để giảm bớt kích thước của các quan hệ.
2.3.2. Ví dụ
Xét hai bảng nhân viên và đơn vị sau:
o NhanVien (MaNV, MasoDV, HoTen, NgaySinh, GioiTinh, Luong)
o DonVi(MaDV, TenDV)
17
Truy vấn đưa ra họ tên của các nhân viên nữ ở đơn vị có tên là „PhongDaoTao‟:
18
2.4. Câu hỏi ôn tập chƣơng 2
Trình bày các bước trong quá trình xử lý truy vấn.
Trình bày các phép biến đổi tương đương.
Trình bày thuật toán tối ưu hóa cây đại số quan hệ.
Cho hai bảng nhân viên và đơn vị sau:
o NhanVien (MaNV, MasoDV, HoTen, NgaySinh, GioiTinh, Luong)
o DonVi(MaDV, TenDV)
Hãy viết biểu thức đại số quan hệ thực hiện truy vấn sau: Đưa ra họ tên của các nhân viên
nữ ở đơn vị có tên là „PhongDaoTao‟. Tối ưu hóa truy vấn trên sử dụng phương pháp biến
đổi đại số quan hệ.
Cho các quan hệ:
o DonVi(MDV, TenDV, MaNQL, DiaDiem)
o DuAn (MaDA, TenDA, KinhPhi, MaDV)
Truy vấn nào dưới đây đã tối ưu?
Q1.
Q2.
Q3.
Q4.
19
CHƢƠNG 3: GIAO DỊCH TRONG CƠ SỞ DỮ LIỆU
3.1. Giới thiệu
Thuật ngữ giao dịch (Transaction) đề cập tới một tập hợp các lệnh tạo thành một đơn vị làm
việc logic, hoặc nó được thực hiện một cách đầy đủ hoặc bị hủy bỏ hoàn toàn.
Ví dụ 3.1: Chuyển tiền từ tài khoản A sang tài khoản B là một giao dịch:
Kiểm tra tiền trong tài khoản A (có X không?).
A = A – X.
B = B + X.
Thường giao dịch được tạo ra bởi các chương trình người dùng được viết trong ngôn ngữ xử
lý dữ liệu bậc cao hoặc ngôn ngữ lập trình (vd: SQL, C++, Java).
Mục dữ liệu (data item) là đơn vị dữ liệu trong CSDL. Bản chất, kích thước của các mục dữ
liệu do nhà thiết kế chọn. Chúng được lựa chọn sao cho việc truy xuất dữ liệu đạt hiệu quả nhất. Ví
dụ trong mô hình dữ liệu quan hệ, ta có thể chọn mục dữ liệu là: các quan hệ, các bộ, hay các thành
phần của bộ. Kích thước của các mục dữ liệu mà hệ thống sử dụng gọi là độ mịn của hệ thống
(granularity).
Bộ lập lịch (Scheduler) là một thành phần của hệ thống CSDL chịu trách nhiệm tạo ra một
lịch biểu (thứ tự thực hiện) các thao tác trong các giao dịch.
3.2. Các tính chất của giao dịch
Để đảm bảo tính toàn vẹn của dữ liệu, hệ cơ sở dữ liệu cần duy trì các tính chất sau của giao
dịch:
Tính nguyên tử (Atomicity): Hoặc toàn bộ các thao tác của giao dịch được phản ánh đúng
đắn trong cơ sở dữ liệu hoặc không có gì cả.
Tính nhất quán (Consistency): Sự thực hiện của một giao dịch phải bảo đảm tính nhất quán
của cơ sở dữ liệu.
Tính cô lập (Isolation): Nhiều giao dịch có thể thực thi đồng thời nhưng mỗi giao dịch
không cần biết đến các giao dịch khác đang thực hiện đồng thời. Các kết quả trung gian của
giao dịch phải được che giấu trước các giao dịch khác.
Tính lâu bền (Durability): Sau khi giao dịch hoàn thành, các thay đổi đã được tạo ra đối với
cơ sở dữ liệu vẫn còn ngay cả khi xảy ra sự cố hệ thống.
20
Tải về để xem bản đầy đủ
58 trang
15120
Free
Bạn đang xem 20 trang mẫu của tài liệu "Giáo trình Cơ sở dữ liệu nâng cao - Trường Đại học Hàng Hải", để tải tài liệu gốc về máy hãy click vào nút Download ở trên
File đính kèm:
- giao_trinh_co_so_du_lieu_nang_cao_truong_dai_hoc_hang_hai.pdf
