Chương V
QUAN HỆ
I. QUAN HỆ VÀ CÁC TÍNH CHẤT
o Khái niệm và tính chất :
Đònh nghóa: Cho A và B là các tập hợp. Một quan hệ hai ngôi
ℜ
từ A đến B là một tập
con của tích Descartes AxB.
Chúng ta dùng cách kí hiệu: a
ℜ
b để chỉ (a,b)
∈
ℜ
và
nói rằng a có quan hệ
ℜ
với b. Khi A=B ta nói
ℜ
là một quan
hệ hai ngôi trên A.
Ví dụ 1: Xét tập A=
{
1; 2; 3; 4; 5
}

và tập B=
{
1; 2; 3; 4; 5; 6
}

với quan hệ

a
Đối xứng (symmetric) nếu và chỉ nếu :
∀
a,b
∈
A : a
ℜ
b
⇒
b
ℜ
a
Phản đối xứng (antisymmetric) nếu và chỉ nếu :
∀
a,b
∈
A : (a
ℜ
b)
∧
(b
ℜ
a)
⇒
(a=b)
Bắc cầu (transitivity) nếu và chỉ nếu :
∀
a,b,c
∈
A : (a

a (mod 5)
2)
∀
(a,b)
∈
ZxZ: a
≡
b (mod 5)
⇒
a
≡
b (mod 5)
3)
∀
a,b,c
∈
Z : [a
≡
b (mod 5)]
∧
[b
≡
c (mod 5)]
⇒
a
≡
c (mod 5)
Vậy quan hệ đồng dư modulo 3 xác đònh trên tập Z là một quan hệ hai ngôi có các tính
chất phản xạ, đối xứng và bắc cầu. Quan hệ này không có tính phản đối xứng vì, chẳng hạn, :
[10

p
là một quan hệ hai ngôi có các tính chất: phản xạ,
phản đối xứng và bắc cầu.
o Đònh nghóa khái niệm “hàm” nhờ quan hệ :
Một hàm f từ tập A đến tập B cho phép thiết lập mối quan hệ f giữa mỗi phần tử a
∈
A
với một phần tử b
∈
B tương ứng. Đồ thò của f:
Γ
(f)=
{ }
( , ) ( ) ( ) ( ( ))a b a A b B b f a∈ ∧ ∈ ∧ =
là một tập con của AxB nên f cũng có thể xem như một quan hệ hai ngôi từ A đến B.
Ngược lại nếu
ℜ
là một quan hệ hai ngôi từ A đến B sao cho mọi phần tử trong A là
phần tử thứ nhất của chỉ một cặp có sắp xếp trong
ℜ
thì có thể đònh nghóa hàm f với
ℜ
như là
đồ thò của nó.
Ví dụ 4:
Cho
ℜ
là quan hệ 2-ngôi từ A =
{
1; 2; 3; 4; 5

n
là các tập hợp. Một quan hệ n-ngôi
ℜ
xác đònh trên các
tập này là một tập con của tích Descartes A
1
xA
2
x..xA
n
.
Ví dụ 5:
Cho
ℜ
là quan hệ gồm các bộ sáu (T,N,P,Q,K,B) biểu diễn thông tin về mỗi
sinh viên, trong đó T là họ và tên, N là ngày sinh, P là phái tính, Q là quê quán,
K là lớp, B là số danh bộ. Chẳng hạn nam sinh viên Trần Dạ Lan sinh ngày
12-2-1987 tại Mỏ cày lớp K1 CNTT có số danh bộ là K1_9110 thì:
(Trần Dạ Lan, 12-2-1987, Nam, Mỏ cày, K1 CNTT,K1_9110)
∈

ℜ
Khi đó
ℜ
là quan hệ 6-ngôi xác đònh trên các tập dữ liệu về Họ và tên, Ngày
sinh, Phái tính, Danh sách lớp, Sổ danh bộ.
Một quan hệ
ℜ
kiểu như vậy, như trong phần trình bày dưới đây, được gọi là một bảng.
Tập các bảng chứa các thông tin có liên quan với nhau (dữ liệu) được gọi là một cơ sở dữ liệu

a) Khác
∅
b) Không có hai mẫu tin nào có cùng giá trò tại trường (filed) này.
Tập đó gọi là Khóa (key) của bảng dữ liệu. Tuy nhiên một tập hợp các trường cũng có
thể xác đònh một biểu thức thỏa mãn hai tính chất a) và b) nói trên khi đó ta có một khóa phức
hợp .
Ví dụ 7:
Trong ví dụ 5, trường HoTen không thể lấy làm khóa được mặc dù ai cũng phải
có họ và tên (ie: khác
∅
) tuy nhiên có thể có nhiều sinh viên có cùng họ và tên.
Tương tự như vậy có thể có rất nhiều sinh viên có cùng ngày tháng năm sinh do
đó trường Ngaysinh cũng không thể là một khóa. Trường số danh bộ SDBo có
thể được lấy làm khóa vì mỗi sinh viên đều bắt buộc phải có một số danh bộ và
hơn nữa số danh bộ này không trùng lắp giữa hai sinh viên khác nhau. Một khóa
là nhằm để phân biệt các mẫu tin khác nhau vì vậy đối với một bảng không cần
thiết phải có hơn một khóa
1
, tuy nhiên nếu tin tưởng chắc rằng trên các tập
HoTen, NgaySinh, Phai, Noisinh, Lop, và SDBo đang xét không thể có hai
người cùng họ tên, cùng ngày sinh và nơi sinh thì bộ
“HoTen+NgaySinh+Noisinh” có thể lấy làm một khóa được (khóa phức hợp) .
 Có nhiều phép toán trên các quan hệ n-ngôi để tạo nên các quan hệ n-ngôi mới, ta xét
một số trong các phép toán đó:
Đònh nghóa: Phép chiếu P
i1,i2,..,im
ánh xạ bộ n phần tử (a
1
,a
2

1,4,5
ánh xạ bộ
(Trần Dạ Lan, 12-2-1987, Nam, Mỏ cày, K1 CNTT,K1_9110)
thành bộ
(Trần Dạ Lan, Mỏ cày, K1 CNTT)
Qua ví dụ này ta có thể thấy phép chiếu P
i1,i2,..,im
đã biến đổi một quan hệ n-ngôi thành
một quan hệ khác chỉ gồm n-m ngôi. Qua phép chiếu một bảng ta sẽ nhận được một bảng mới
1
Một số hệ quản trò CSDL, như Visual Foxpro, dùng thuật ngữ PRIMARY KEY để chỉ khóa này.
90
mà số mẫu tin có thể bò giảm đi nếu có một số mẫu tin có các giá trò như nhau trong tất cả m
phần tử của phép chiếu.
Ví dụ 9:
Phép chiếu P
2,3
sẽ biến bảng
ℜ
thành bảng
ℜ
’ như sau:
Ngược lại với phép chiếu làm số cột của một
bảng có thể giảm đi thì phép hợp nói sau đây cho phép tổ hợp hai bảng thành một bảng mới khi
hai bảng này có một số trường giống nhau.
Đònh nghóa: Cho
ℜ
là quan hệ bậc m và S là quan hệ bậc n. Phép hợp J
p
(

, c
1
,c
2
,..,c
p
) thuộc
ℜ
và bộ n phần tử
c
1
,c
2
,..,c
p
,b
1
,b
2
,b
n-p
) thuộc S.
Nói cách khác toán tử hợp J
p
tạo một quan hệ mới từ hai quan hệ cũ bằng cách tổ hợp
tất cả các bộ m phần tử của quan hệ thứ nhất với tất cả các bộ n phần tử của quan hệ thứ hai,
trong đó p phần tử cuối cùng của bộ m phần tử phù hợp với p phần tử đầu tiên của bộ n phần
tử.
2
Ví dụ 10:

Khoai
Sinh học Di truyền
Vàng A Vọt Toán học Đại số
Bảng
ℜ
’
Ngành
học
Môn học
Toán học Topology
Tin học C++
Sinh học Di truyền
Toán học Đại số
Bảng 2
Khoa Mã số môn
học
Phòng
học
Giờ
dạy
CNTT C123 A202 14h
CNTT C134 A203 8h
CNTT C216 A204 10h
Tự Nhiên T345 B201 8h
Tự Nhiên T367 B202 10h
Tự Nhiên T412 B204 10h
CNTT C052 B203 16h
Xã Hội X111 A301 8h
Xã Hội X117 A302 10h
Xã Hội X212 A303 14h

Nhiều vấn đề về các toán tử này sẽ còn được nghiên cứu sâu hơn trong môn Cơ Sở Dữ
Liệu Quan Hệ và ngôn ngữ SQL (Structured Query Language).
II. QUAN HỆ THỨ TỰ VÀ QUAN HỆ TƯƠNG ĐƯƠNG
1. Quan hệ thứ tự:
Đònh nghóa: Một quan hệ
ℜ
trên A gọi là quan hệ thứ tự nếu
ℜ
thỏa các tính chất:
phản hồi, phản đối xứng, bắc cầu.
Ví dụ 11: Quan hệ nói trong ví dụ 3 là một quan hệ thứ tự.
o Quan hệ tương đương và sự chia lớp
Đònh nghóa: Một quan hệ
ℜ
trên A gọi là quan hệ tương đươngï nếu
ℜ
thỏa các tính
chất: phản hồi, đối xứng, bắc cầu.
Ví dụ 12:
Quan hệ nói trong ví dụ 2 là một quan hệ tương đương.
Ví dụ 13:
Xét các tập X và Y, f là một ánh xạ từ X đến Y. Đònh nghóa một quan hệ
≈
trên X như
sau:

∀
x
1
,x

( ) ( )b b A a b∈ ∧ ℜ
92