GIAOVIEN

MON

giang
hoten
tenmon
tuoi
id_m
sotiet
id_gv
(1,n)
(1,n)

GIAOVIEN

KHOA

giang
hoten
tenkhoa
tuoi
id_k
sodienthoai
id_gv
tongsotiet
(1,n)
(1,n)

NGUOI

liệu, gắn với CSDL. 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.
 Qui tắc điều kiện (condition): Điều kiện là lựa chọn. Nếu không có điều
kiện nào được xác định thì hành động sẽ được thực hiện khi sự kiện xảy
ra. Nếu điều kiện được xác định thì hành động chỉ xảy ra khi sự kiện là
đúng.
 Qui tắc hành động chiếm giữ (action rule): hành động thường là một
câu truy vấn (SQL), một thực hiện CSDL hoặc một chương trình mở
rộng được thực hiện một cách tự động.
 CSDL tích cực nâng cao: nâng cao chức năng CSDL truyền thống với
đầy đủ các quy tắc - khả năng xử lý.
 CSDL tích cực cung cấp một máy có khả năng và hoạt động tương tự
như bất kỳ ứng dụng hệ thống CSDL như:
+ Tích hợp ràng buộc
+ Khung nhìn
+ Thống kê kết quả
+ Giám sát hoặc thông báo,…
• TrongcơsởdữliệuquanhệcácquytắctíchcựcđượcviếtdướidạngcácTrigger.Vídụ:
Với hai bảng:
o DonVi (MaDV, TenDV,TongLuong, MaNQL)
1
o NhanVien (MaNV, TenNV, NgaySinh, GioiTinh,Luong, MaDV)
Một quytắcsẽ có dạngnhư sau:
o Event:Hành động Insert một bản ghi trongbảng NhanVien.
o Condition:
 GiátrịcủaMaDVđượcthêmvàokhôngcótrongtậpgiátrịhiệncótrong
bảng DonVi.
 NếuMaDVđượcthêmvàolàđãcótrongbảngDonViTổnglươngcủa đơn
vị đó cần được thay đổi.
o Action:

 user-define time: do tùy người sử dụng.
4. Mô hình và thao tác trên CSDL suy diễn:
4.1 Mô hình CSDL suy diễn:
 Kí pháp toán học để mô tả hình thức dữ liệu và các quan hệ.
 Kỹ thuật để xử lý dữ liệu như trả lời các câu hỏi, kiểm tra điều kiện
toàn vẹn.
 Logic bậc một được dùng như kí pháp toán học để mô tả dữ liệu
trong mô hình CSDL suy diễn và dữ liệu được xử lý trong các mô
hình như vậy nhờ việc đánh giá công thức logic.
 Tuy nhiên để dễ biểu diễn hình thức các khái niệm về CSDL suy
diễn, người ta thường dùng phép toán vị từ, tức logic vị từ bậc
nhất. Logic vị từ bậc nhất là ngôn ngữ hình thức dùng để thể hiện
các quan hệ giữa các đối tượng và để suy diễn ra quan hệ mới.
 Các định nghĩa:
o Định nghĩa 1: Mỗi một hằng số, một biến số hay một hàm số
áp lên các tên là một hạng thức (term)
Hàm n ngôi f(x1,x2, ,xn); xi | i = 1,2, ,n là một hạng thức thì
f(x1,x2,…,xn) là một term.
o Định nghĩa 2: Công thức nguyên tố (công thức nhỏ nhất) là
kết quả của việc ứng dụng một vị từ trên các tham số của
term dưới dạng P(t1, t2,…, tn).
Nếu P là vị từ có n ngôi và ti | i=1,2, ,n là một hạng
thức(term).
o Định nghĩa 3: (Literal) Dãy các công thức nguyên tố hay phủ
định của công thức nguyên tố đã được phân tách qua các
liên kết logic (∧, ∨, →, ↔, ¬, ∀, ∃) thì công thức đó được
thiết lập đúng đắn.
 Nhận xét:
• i) Một công thức nguyên tố là công thức thiết
lập đúng đắn.

Trong đó: Pi và Qj (i,j=1,2,…,n) là các Literal dương
Trong hệ thống logic, Literal dương có dạng nguyên tố,
nhỏ nhất, trái với Literal âm là phủ định của nguyên tố.
o Định nghĩa 5: Câu Horn (Horn clause) là câu có dạng
P1
∧
P2
∧
….
∧
Pn
→
Q1
o Định nghĩa 6: CSDL suy diễn tổng quát (General deductive
database)
CSDL suy diễn tổng quát, hay CSDL suy diễn được xác định
như cặp (D,L), trong đó D là tập hữu hạn của các câu CSDL và
L là ngôn ngữ bậc một.
Giả sử L có ít nhất hai ký hiệu, một là ký hiệu hằng số và
một ký kiệu vị từ.
+ Một CSDL xác định (hay CSDL chuẩn) là CSDL suy
diễn(D,L) mà D chỉ chứa các câu xác định(câu chuẩn).
+ Một CSDL quan hệ là CSDL suy diễn (D,L) mà D chỉ chứa
các sự kiện xác định .
4.2 Thao tác trên CSDL suy diễn:
4.2.1 Định nghĩa 1:Giao tác (Transaction)
Một giao tác trong CSDL suy diễn là một một xâu hữu hạn của các phép
toán, hay các hành động bổ sung, loại bỏ hay cập nhật các câu.
Vì một CSDL suy diễn được xem như tập các câu, tức là theo quan điểm
lý thuyết mô hình, không một phép loại bỏ hay cập nhật nào được phép

 Một trong các cách sử dụng phổ biến là là định nghĩa một bảng cho mỗi
lớp, trong đó mỗi cột trong bảng đại diện cho một thuộc tính của lớp (attri
đơn trị, hoặc đa trị)
Employee_Table
• Tất cả các thuộc tính của Employee được lưu trong bảng Employee
• Những thuộc tính trên cùng với các thuộc tính bổ sung của
HourlyEmployee sẽ được copy để lưu bảng HourlyEmployee.
5
Tương tự đối với bảng SalariedEmployee.
Nhận xét:
– Việc chuyển mô hình đối tượng về quan hệ khi có kế thừa sẽ phải copy
các thuộc tính của lớp cha sang lưu vào lớp con nên không bảo đảm
được các dạng chuẩn dữ liệu.
– Một khi các sơ đồ cần thiết đã được định nghĩa mã chuyển đổi từ đối
tượng sang quan hệ được ghi. Mã này là cần thiết để có một đối tượng,
khi nó được tạo ra và xử lý trong các ngôn ngữ lập trình và loại bỏ cấu
trúc (deconstruct) để biểu diễn chúng theo yêu cầu của cơ sở dữ liệu.
– Ngoài ra khi cần tìm các đối tượng HourlyEmployee trong CSDL thì phải
kết nối các bảng HourlyEmployee và Employee. Như vậy sẽ tốn kém
thời gian.
– Vấn đề quan trọng nữa là khi cập nhật thông tin, vì có nhiều mối quan
hệ giữa các bảng thực thể nên độ phức tạp sẽ càng tăng.
7. Chuyển đổi từ mô hình ER sang mô hình quan hệ:
 Mỗi tập thực thể của mô hình ER chuyển đổi thành 1 lớp đối tượng có
cùng tên và cùng tập thuộc tính. Các thuộc tính đa trị và phức hợp của mô
hình ER được chuyển thành các thuộc tính đa trị (sử dụng từ khóa set) và
phức hợp (sử dụng từ khóa tuple) cảu mô hình hướng đối tượng.
 Việc xác định các phương thức cho mỗi lớp đối tượng được thực hiện sau
đó bởi người thiết kế hệ thống CSDL.
 Các qui tắc:

o Qui tắc 2 (qui tắc chuyển đổi mối quan hệ nhị nguyên không có
thuộc tính) : nếu 2 tập thực thể A và B có mối quan hệ R (R không có
các thuộc tính đính kèm), thì mỗi lớp tương ứng A và B sẽ được bổ
sung thêm thuộc tính mối quan hệ R (khai báo thuộc tính đa trị/đơn
trị là tùy thuộc vào bản số liên quan). Cụ thể:
Xét 2 trường hợp sau:
 Trường hợp 1: Nếu chỉ số cực đại của cung nối A và R là 1 thì
thuộc tính R trong lớp A được khai báo :
<Tên thuộc tính R> : <Lớp B>;
 Trường hợp 2: Nếu chỉ số cực đại của cung nối A và R là n thì
thuộc tính R trong lớp A được khai báo :
<Tên thuộc tính R> : set (<Lớp B>);
Ví dụ : mối quan hệ 1-1
Mô hình hướng đối tượng
Class TRUONGKHOA
properties
Id_tk: String;
Hoten: String;
Tuoi: Integer;
Quanly: KHOA;
End TRUONGKHOA.
Class KHOA
properties
Id_k: String;
Tenkhoa: String;
Sodienthoai: String;
Quanly: TRUONGKHOA;
End KHOA.
Mô hình quan hệ
TRUONGKHOA(id_tk, hoten, tuoi)

GIAOVIEN(id_gv, hoten, tuoi)
MON(id_m, tenmon, sotiet)
GIANG(id_gv, id_m)
Ví dụ : (Mối quan hệ nhiều – nhiều)
9

GIAOVIEN

KHOA
thuoc
id_gv
hoten
tenkhoa
tuoi
id_k
sodienthoai
M« h×nh thùc thÓ - mèi quan hÖ

(1,1)
(1,n)
Mô hình hướng đối tượng
Class GIAOVIEN
properties
Id_gv: String;
Hoten: String;
Tuoi: Integer;
Thuoc: KHOA;
End GIAOVIEN.
Class KHOA
properties

Giang1: set(GVIEN_KHOA);
End GIAOVIEN.
Class KHOA
properties
Id_k: allID;
Tenkhoa: String;
Sodienthoai: String;
Giang2: set(GVIEN_KHOA);
End KHOA.
Class GVIEN_KHOA
10
properties
Id_gvien_khoa: allID;
Tongsotiet: Integer;
Giang1: GIAOVIEN;
Giang2: KHOA;
End GVIEN_KHOA.
o Quy tắc 4: Qui tắc chuyển đổi mối quan hệ phản xạ. Việc chuyển đổi
được thực hiện tương tự như mối quan hệ nhị nguyên (bước 2 và
bước 3)
Ví dụ : Mối quan hệ phản xạ
Mô hình hướng đối tượng
Class NGUOI
properties
Id: allID;
11
Hoten: String;
Tuoi: Integer;
Con: set(NGUOI);
Cha, Me: NGUOI;

Class LOP
properties
Id_lop: String;
End LOP.
Class MONHOC
properties
Id_monhoc: String;
Sotiet: Integer;
End MONHOC.
Class LICHDAY
properties
Thoigian: String;
Giang: GIAOVIEN;
Gomco: MONHOC;
Botri: LOP;
End LICHDAY.
8. Truy vấn trong cơ sở dữ liệu hướng đối tượng và ODMG 3.0 :
9. Phân mảnh trong CSDL phân tán:
Phân mảnh (theo chiều ngang, dọc, kết hợp), bản sao (replication), cấp phát
trong CSDL phân tán:
 Mô hình phân đoạn của một CSDL là việc định nghĩa tập các cách phân
đoạn bao gồm các thuộc tính và tuple trong CSDL và việc thoả các điều
kiện để có xây dựng CSDL ban đầu từ các phân đoạn bằng cách sử dụng
các toán tử OUTER UNION (hoặc OUTER JOIN) và UNION.
 Nếu một phân đoạn được lưu trữ ở nhiều site, ta nói rằng phân đoạn
đó được sao lưu (replicated).
9.1 Phân mảnh ngang (horizontal fragmentation):
13
 Phân mảnh ngang một quan hệ tổng thể n-bộ R là tách R thành các
quan hệ con n-bộ R

gồm tất cả các thuộc tính trong R nhưng chỉ chia sẻ chỉ thuộc tính
khoá của R gọi là phân đoạn đầy đủ của R.
 Trong trường hợp này, phép chiếu danh sách thoả:
o
o với mọi i ≠ j trong đó ATTTRS(R) là
tập các thuộc tính của R và PK(R) là khoá chính của R.
 Để xây dựng lại R từ các phân đoạn dọc ta sử dụng toán tử OUTER
UNION trên phân đoạn dọc.
 Phân mảnh dọc một quan hệ tổng thể n-bộ R là tách R thành các
quan hệ con R1, R2, , Rk sao cho quan hệ R có thể được khôi phục
lại từ các quan hệ con này bằng phép nối:
R = R1 R2 , Rk
9.3 Phân mảnh kết hợp (hybrid fragmentation):
 Là việc tổ hợp phân đoạn dọc và phân đoạn ngang.
 Quan hệ ban đầu có thể xây dựng lại bằng cách áp dụng các toán tử
UNION và OUTER UNION.
 Thông thường, mỗi phân đoạn của quan hệ R có được bằng cách tổ
hợp toán tử SELECT−PROJECT, kí hiệu Π
L
(σ
C
(R)):
o If C = TRUE and L ≠ ATTRS(R): phân đoạn dọc.
o If C ≠ TRUE and L = ATTRS(R): phân đoạn ngang
o If C ≠ TRUE and L ≠ ATTRS(R): phân đoạn hỗn hợp.
14
Ví dụ: Xét cơ sở dữ liệu của một công ty phần mềm được tổ chức như
sau:
• NHANVIEN (MANV, TENNV, CHUCVU): quan hệ này chứa dữ liệu về
nhân viên của công ty.

Phân tích HT
Thiết kế DL
HOSO(G)
MANV TENNV CHUCVU
A1
A2
A3
A4
A5
A6
A7
A8
Nam
Trung
Đông
Bắc
Tây
Hùng
Dũng
Chiến
Phân tích HT
Lập trình viên
Phân tích HT
Phân tích HT
Lập trình viên
Kỹ sư điện
Phân tích HT
Thiết kế DL
DUAN(J)
MADA TENDA NGANSACH

o Thứ hai, dữ liệu cần truy xuất phải được cục bộ hóa để các thao
tác trên các quan hệ được chuyển thành các thao tác trên dữ
liệu cục bộ (các mảnh).
o Cuối cùng câu truy vấn đại số trên các mảnh phải được mở rộng
để bao gồm các thao tác truyền thông và được tối ưu hóa để
hàm chi phí là thấp nhất.
 Hàm chi phí muốn nói đến các tính toán như thao tác xuất nhập đĩa, tài
nguyên CPU, và mạng truyền thông.
Bài toán xử lí vấn tin:
 Có hai phương pháp tối ưu hóa cơ bản được sử dụng trong các bộ
xử lý vấn tin:
o Phương pháp biến đổi đại số
o Chiến lược ước lượng chi phí.
17
 Phương pháp biến đổi đại số đơn giản hóa các câu vấn tin nhờ các
phép biến đổi đại số nhằm hạ thấp chi phí trả lời câu vấn tin, độc
lập với dữ liệu thực và cấu trúc vật lý của dữ liệu.
 Nhiệm vụ chính của thể xử lý vấn tin quan hệ là biến đổi câu vấn tin
cấp cao thành một câu vấn tin tương đương ở cấp thấp hơn được
diễn đạt bằng đại số quan hệ. Việc biến đổi này phải đạt được cả
tính đúng đắn lẫn tính hiệu quả.
Ví dụ 1:Xét một tập con của lược đồ CSDL đã được cho
NV( MNV, TênNV, Chức vụ)
PC (MNV, MDA, Nhiệm vụ, Thời gian)
Và một câu truy vấn đơn giản sau:
“Liệt kê tên của các nhân viên hiện đang quản lý một dự án”
Biểu thức truy vấn bằng phép tính quan hệ theo cú pháp của SQL là:
SELECT TênNV
FROM NV, PC
WHERE NV.MNV=PC.MNV

TênNV
(NV|><|
MNV(
σ
Nhiệmvụ=”Quảnlý”
(PC)))
chúng ta giả sử rằng các quan hệ NV và PC được phân mảnh ngang như
sau:
NV1=σ
MNV
≤
“E3”
(NV)
NV2=σ
MNV > “E3”
(NV)
PC1=σ
MNV
≤
“E3”
(PC)
PC2=σ
MNV
≥
“E3”
(PC)
Các mảnh PC1, PC2, NV1, NV2 theo thứ tự được lưu tại các vị trí 1, 2, 3
và 4 và kết quả được lưu tại vị trí 5.
18
Mũi tên từ vị trí i đến vị trí j có nhãn R chỉ ra rằng quan hệ R được

các vị trí khác nhau và truyền dữ liệu giữa các vị trí.
 Một công cụ khác là thời gian đáp ứng của câu vấn tin, là thời gian
cần thiết để chạy câu vấn tin.
 Trong môi trường CSDL phân tán, tổng chi phí cần phải giảm thiểu là
chi phí CPU, chi phí xuất nhập và chi phí truyền.
 Độ phức tạp của các phép toán quan hệ:
o Các phép toán chọn, Chiếu (Không loại bỏ trùng lặp) có độ
phức tạp là O(n).
o Các phép chiếu (Có loại bỏ trùng lặp), trùng lặp, nối, nối nửa,
chia có độ phức tạp là O(n*logn).
o Tích Descartes có độ phức tạp là O(n
2
) (N biểu thị lực lượng
của quan hệ nếu các bộ thu được độc lập với nhau)
 Đánh giá:
o Các thao tác có tính chọn lựa làm giảm đi lực lượng cần phải
thực hiện trước tiên.
o Các phép toán cần phải được sắp xếp để tránh thực hiện tích
Descartes hoặc để lại thực hiện sau.
11. Lịch tuần tự, khả tuần tự của các giao tác:
 Lịch biểu(dãy có thứ tự) là môt dãy các thao tác của một tập các giao
tác mà trong đó thứ tự các thao tác trong mỗi giao tác được bảo toàn.
Ví dụ1 : Xét 2 giao tác chuyển tiền:
 10$ từ A -> B
 20$ từ B -> C
T1 T2
20
Read (A) Read (B)
A = A- 10 B = B- 20
Write (A) Write (B)

Read (B)
B = B- 20
Write (B)
Read(C)
C = C +20
21
Write (C)
 Lịch biểu không tuần tự (non serial schedule): là lịch biểu mà các thao
tác trong các giao dịch được đan xem vào nhau.
Ví dụ :
T1 T2
Read (A)
Read (B)
A = A- 10
B = B- 20
Write (A)
Write (B)
Read(B)
Read(C)
B = B +10
C = C +20
Write (B)
Write (C)
 Tính khả tuần tự của lịch biểu: Lịch biểu gọi là khả tuần tự (serializable)
nếu nó tương đương với một lịch biểu tuần tự.
o Tương đương theo nghĩa cho ra cùng 1 trạng thái CSDL sau khi kết
thúc việc thực hiện lịch biểu.
o Lịch biểu bất khả tuần tự nếu nó không tương đương với 1 lịch biểu
tuần tự.
Ví dụ :

Read (B)
Write (A)
B = B- 20
Read(B)
Write (B)
B = B +10
Read(C)
Write (B)
C = C +20
Write (C)
Thuật toán kiểmtra tínhkhảtuầntựcủalịch biểu
• Input:S{T1, T2, …, Tn}
• Output:Skhảtuần tự hayk?
• Thuật toán:
o Xâydựngđồ thịphụ thuộc G:
 Nút: là cácgiao dịch.

CungTi

Tj:
•
Tj read(X) sau Ti wite(X).
• Tj write(X) sau Ti read(X).
• Tj write (X) sau Ti write(X).
o Nếu G không có chu trình thì lịch tuần tự S là khả tuần tự, ngược lại lịch biểu S là bất
23
khả tuần tự.
• Ví dụ:Lịch biểu Scủahai giaodịch T1, T2 vàđồ thị phụ thuộcG củaS:
Hình3.4:Ví dụkiểmtratínhkhả tuầntự của lịchbiểu
Trongví dụ nàyta thấyđồ thịG có chu trình, do vậylịch biểu Slà bất khả tuần tự.