BỘ GIÁO DỤC VÀ ĐÀO TẠO
TRƢỜNG ĐẠI HỌC SƢ PHẠM HÀ NỘI 2

NGUYỄN THÀNH GIỚI

CÁC TẬP THUỘC TÍNH NGUYÊN THỦY VÀ PHI
NGUYÊN THỦY TRONG LƢỢC ĐỒ KHỐI

LUẬN VĂN THẠC SĨ MÁY TÍNH

HÀ NỘI, 2016


BỘ GIÁO DỤC2 VÀ ĐÀO TẠO
TRƢỜNG ĐẠI HỌC SƢ PHẠM HÀ NỘI 2

NGUYỄN THÀNH GIỚI

CÁC TẬP THUỘC TÍNH NGUYÊN THỦY VÀ PHI
NGUYÊN THỦY TRONG LƢỢC ĐỒ KHỐI
Chuyên ngành: KHOA HỌC MÁY TÍNH
Mã số: 60 48 01 01

LUẬN VĂN THẠC SĨ MÁY TÍNH

Người hướng dẫn khoa học: PGS.TS Trịnh Đình Thắng

HÀ NỘI, 2016


1

LỜI CẢM ƠN
Hoàn thành luận văn này tôi xin chân thành cảm ơn các thầy cô giáo
trường Đại học Sư phạm Hà Nội 2 đã tạo điều kiện tốt nhất cho tôi trong suốt
quá trình học tập và nghiên cứu.
Tôi xin bày tỏ lòng biết ơn sâu sắc nhất đến PGS.TS Trịnh Đình Thắng
người thầy, người hướng dẫn khoa học, đã tận tình hướng dẫn tôi trong suốt
quá trình học tập, nghiên cứu đề tài và giúp đỡ tôi hoàn thành luận văn này.
Tôi xin gửi lời cảm ơn chân thành tới gia đình, bạn bè, đồng nghiệp đã
luôn tạo điều kiện, ủng hộ, động viên trong suốt thời gian qua.
Mặc dù đã cố gắng trong quá trình thực hiện nhưng luận văn không thể
tránh khỏi những sai sót. Tôi mong nhận được sự góp ý chân thành của quý
thầy cô, quý đồng nghiệp và bạn bè.
Xin trân trọng cảm ơn!
Hà Nội, tháng 8 năm 2016
Học viên

Nguyễn Thành Giới


2

LỜI CAM ĐOAN
Tôi xin cam đoan đây là kết quả nghiên cứu của tôi dưới sự hướng dẫn
khoa học của PGS.TS Trịnh Đình Thắng. Tôi xin cam đoan rằng số liệu và
kết quả nghiên cứu trong luận văn này là trung thực và không trùng lặp với
các đề tài khác. Tôi c ng xin cam đoan rằng mọi sự giúp đỡ cho việc thực
hiện luận văn này đã được cảm ơn và các thông tin trích dẫn trong luận văn đã
được chỉ rõ nguồn gốc.
Hà Nội, tháng 8 năm 2016

Học viên

Nguyễn Thành Giới


3

MỤC LỤC
Trang
Trang phụ bìa............................................................................
Lời cảm ơn................................................................................

1

Lời cam đoan............................................................................

2

Mục lục....................................................................................

3

Danh mục các ký hiệu, các chữ viết tắt......................................

5

MỞ ĐẦU..................................................................................

6


Chương 1. CÁC MÔ HÌNH DỮ LIỆU........................................

9

1.1 Mô hình thực thể - liên kết................................................

9

1.2 Mô hình dữ liệu mạng.......................................................

9

1.3 Mô hình dữ liệu phân cấp.................................................

10

1.4 Mô hình hướng đối tượng.................................................

11

1.5 Mô hình dữ liệu datalog....................................................

12

1.6 Mô hình dữ liệu quan hệ..................................................

12

1.6.1 Quan hệ, thuộc tính, bộ............................................


13

1.6.2 Đại số quan hệ.........................................................

14

1.6.3 Phụ thuộc hàm, hệ tiền đề Armstrong.......................

22

1.6.4 Bao đóng của tập thuộc tính.....................................

25

1.6.5 Khóa của lược đồ quan hệ........................................

27

Chương 2. MÔ HÌNH DỮ LIỆU DẠNG KHỐI.........................

30

2.1 Khối, lát cắt của khối........................................................

30

2.1.1 Khối, lược đồ khối....................................................

30


2.1.2 Lát cắt......................................................................

32

2.2 Các phép tính trên khối.....................................................

33

2.2.1 Phép chèn.................................................................

33

2.2.2 Phép loại bỏ...............................................................

33


4

2.2.3 Phép sửa đổi..............................................................

34

2.3 Đại số quan hệ trên khối....................................................

34

2.3.1 Phép hợp..................................................................

34


2.3.2 Phép giao..................................................................

35

2.3.3 Phép trừ....................................................................

35

2.3.4 Tích Đề-Các..............................................................

36

2.3.5 Tích Đề-Các theo tập chỉ số.......................................

36

2.3.6 Phép chiếu................................................................

37

2.3.7 Phép chọn.................................................................

38

2.3.8 Phép kết nối..............................................................

39

2.3.9 Phép chia..................................................................


39

2.4 Một số tính chất của đại số quan hệ trên khối.....................

29

2.5 Phụ thuộc hàm trên lược đồ khối.......................................

41

2.6 Bao đóng của tập các phụ thuộc hàm.................................

41

2.7 Bao đóng của tập các thuộc tính chỉ số...............................

42

2.8 Khóa của lược đồ khối R đối với tập F trên R.....................

46

Chương 3. CÁC TẬP THUỘC TÍNH NGUYÊN THỦY VÀ

50

PHI NGUYÊN THỦY TRONG LƯỢC ĐỒ KHỐI.....................
3.1 Các tập thuộc tính nguyên thủy và phi nguyên thủy trong


50

lược đồ khối..................................................................................
3.2 Một số tính chất mới của tập thuộc tính nguyên thủy và phi

56

nguyên thủy trong lược đồ khối....................................................
KẾT LUẬN............................................................................................

60

TÀI LIỆU THAM KHẢO.......................................................................

61


5

DANH MỤC CÁC KÝ HIỆU, CÁC CHỮ VIẾT TẮT
Ký hiệu

Ý nghĩa

CSDL

Cơ sở dữ liệu

Dom(A) hoặc dom(A)


Miền giá trị của thuộc tính A

<=>

Tương đương

=> hoặc 

Suy ra

∪

Phép hợp

∩

Phép giao

∃

Tồn tại

∄

Không tồn tại

∈

Thuộc




Không thuộc



Là con(chứa trong)



Chứa

∅

Rỗng

∀

Với mọi

≦

Phủ định

→

Kéo theo

|=


Suy diễn logic


6

MỞ ĐẦU
1. Lý do chọn đề tài
Trong những thập niên gần đây, việc ứng dụng công nghệ thông tin
đang trở nên rộng rãi và vai trò của công nghệ thông tin ngày càng được
khẳng định trong nhiều lĩnh vực khác nhau như: Học tập, khoa học kỹ thuật,
kinh tế, tài chính, xây dựng, ngân hàng và nhiều lĩnh vựa dưới nhiều quy mô
khác nhau. Với việc sử dụng các ứng dụng của công nghệ, lưu lượng dữ liệu
được sử dụng ngày càng tăng và việc xây dựng các mô hình quản lý dữ liệu
ngày càng cấp thiết và ảnh hưởng rất lớn đến giá trị sử dụng của dữ liệu. Từ
đó, đã có nhiều mô hình cơ sở dữ liệu được ra đời nhằm đáp ứng nhu cầu trên
như: Mô hình dữ liệu thực thể - liên kết, mô hình dữ liệu mạng, mô hình dữ
liệu phân cấp, mô hình hướng đối tượng, mô hình dữ liệu quan hệ, mô hình
dữ liệu dạng khối.
Trong đó, mô hình dữ liệu dạng khối là mở rộng của các mô hình đang
được sử dụng rất phổ biến là mô hình dữ liệu quan hệ và mô hình thực thể liên kết. Mô hình dữ liệu dạng khối thể hiện mối quan hệ giữa dữ liệu với các
thông tin thực tế một cách tự nhiên hơn.
Để góp phần hoàn chỉnh thêm về mô hình dữ liệu dạng khối tôi mạnh
dạn chọn đề tài là “Các tập thuộc tính nguyên thủy và phi nguyên thủy
trong lược đồ khối”.
2. Mục đích nghiên cứu
Tìm hiểu khái quát về mô hình dạng khối sau đó đi sâu và nghiên cứu
các tập thuộc tính nguyên thủy và phi nguyên thủy trong lược đồ khối.
3. Nhiệm vụ nghiên cứu
- Tìm hiểu mô hình dữ liệu
- Tìm hiểu mô hình dữ liệu dạng khối



7

- Tìm hiểu một số tính chất của tập thuộc tính nguyên thủy và phi
nguyên thủy trong lược đồ khối
- Phát biểu và chứng minh một số tính chất mới của tập thuộc tính tính
nguyên thủy và phi nguyên thủy trong lược đồ khối
4. Đối tƣợng và phạm vi nghiên cứu
* Đối tƣợng nghiên cứu
Các tính chất của tập thuộc tính nguyên thủy và phi nguyên thủy trong
lược đồ khối
* Phạm vi nghiên cứu
Tập thuộc tính nguyên thủy và phi nguyên thủy trong lược đồ khối
5. Phƣơng pháp nghiên cứu
- Phương pháp tổng hợp phân tích các vấn đề có liên quan đến đề tài
- Phương pháp lý luận và chứng minh
6. Những đóng góp của đề tài
- Tìm hiểu mô hình dữ liệu dạng khối
- Các khái niệm và tính chất của tập thuộc tính nguyên thủy và phi
nguyên thủy
- Phát biểu và chứng minh một số tính chất mới của tập thuộc tính
nguyên thủy và phi nguyên thủy trong lược đồ khối và lược đồ lát cắt.
7. Cấu trúc luận văn
Luận văn gồm lời mở đầu, nội dung của ba chương, kết luận và tài liệu
tham khảo
Chƣơng 1: Các mô hình dữ liệu
Chương này trình bày một số khái niệm cơ bản nhất về các mô hình dữ
liệu. Tập trung chủ yếu vào mô hình dữ liệu quan hệ do mô hình này có nhiều
ưu điểm, tính độc lập cao lại dễ dàng sử dụng. Trình bày được các phép toán

cơ bản các khái niệm về phụ thuộc hàm, hệ tiên đề Amstrong, khóa, bao đóng


8

cùng các tính chất trong mô hình dữ liệu quan hệ. Các thuật toán tìm khóa,
bao đóng trong mô hình dữ liệu quan hệ c ng được trình bày trong chương
này.
Chƣơng 2: Mô hình dữ liệu dạng khối
Nội dung trong chương này trình bày về mô hình dữ liệu dạng khối
như: Khái niệm về khối, lát cắt của khối, các phép tính trên khối, đại số quan
hệ và các tính chất của đại số quan hệ trên khối, các phép toán về khóa, bao
đóng và phụ thuộc hàm trên khối c ng được trình bày.
Chƣơng 3: Các tập thuộc tính nguyên thủy và phi nguyên thủy
trong lƣợc đồ khối.
Nội dung chương này trình bày định nghĩa về các tập thuộc tính nguyên
thủy và phi nguyên thủy trong lược đồ khối. Phát biểu và chứng minh một số
tính chất mới của tập thuộc tính nguyên thủy và phi nguyên thủy trong lược
đồ khối.


9

Chƣơng 1. CÁC MÔ HÌNH DỮ LIỆU
Nội dung chương này trình bày các khái niệm cơ bản về các mô hình dữ
liệu. Tập trung chủ yếu vào mô hình dữ liệu quan hệ do mô hình này có nhiều
ưu điểm, tính độc lập cao lại dễ dàng sử dụng đã được trình bày trong các tài
liệu [1], [5] ,[8], [9].
1.1 Mô hình thực thể - liên kết
Mô hình thực thể - liên kết (Entity-Relationship Model) gọi tắt là mô

hình ER. Là một mô hình dữ liệu ở mức phổ biến, tập trung vào các cấu trúc
dữ liệu và các ràng buộc.
Thuật ngữ “thực thể” (entity) không có một định nghĩa hình thức, c ng
giống như các thuật ngữ “điểm” và “đường” trong hình học ngầm được định
nghĩa bằng các tiêu đề về các đặc tính của chúng. Thực thể là một sự vật tồn
tại và phân biệt được, nghĩa là có thể phân biệt thực thể này với thực thể khác.
Một nhóm bao gồm tất cả các thực thể “tương tự” tạo ra một tập thực
thể (entity set). Các đặc tính của tập thực thể gọi là các thuộc tính.
Mô hình này trình bày các khái niệm cơ bản như: khóa, mối liên hệ,
phân cấp isa, ... Mục đích của mô hình này là cho phép mô tả lược đồ khái
niệm của một tổ chức mà không cần chú ý đến hiệu quả hoặc các chi tiết thiết
kế cơ sở dữ liệu vật lý.
1.2 Mô hình dữ liệu mạng
Ta có thể nói đơn giản rằng mô hình dữ liệu mạng (network data
model) là mô hình thực thể - liên kết mà ở đó các mối liên hệ bị ràng buộc
trong kiểu nhị phân và một nhiều. Hạn chế này cho phép ta dùng một mô hình
đồ 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


10

đưa ra kiểu mẫu tin logic (logical record type). Một kiểu mẫu tin logic là tên
gán cho một tập các mẫu tin, được gọi là các mẫu tin logic (logical record).
Mẫu tin logic được cấu tạo bởi các trường (filed) 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 mẫu tin logic.
Các thuật ngữ dành cho mô hình mạng gần như tương đồng với các
thuật dùng trong mô hình quan hệ. Tuy nhiên, có một sự khác biệt quan trọng
giữa bộ của quan hệ và mẫu tin của kiểu mẫu tin. Trong mô hình quan hệ, bộ
là giá trị của các thành phần. Hai bộ có cùng giá trị cho các thuộc tính giống

nhau chỉ là một bộ. Mô hình mạng thuộc loại hướng đối tượng, ít nhất theo
nghĩa nó hỗ trợ đặc tính nhận dạng đối tượng. Các mẫu tin của mô hình mạng
có thể được xem như là có một khóa “không nhìn thấy được” mà bản chất là
địa chỉ của mẫu tin, nghĩa là “đặc tính nhận dạng đối tượng” của nó. Dấu hiệu
nhận dạng duy nhất này làm cho các mẫu tin khác nhau, cho dù nếu chúng có
các giá trị giống nhau trong các trường hợp tương ứng.
Trong CSDL được xây dựng trên mô hình mạng, chúng có những con
trỏ vật lí chỉ đến những mẫu tin khác để biểu thị các mối liên hệ mà kiểu mẫu
tin của chúng có tham gia. Những con trỏ này làm cho hai mẫu tin có cùng giá
trị trường trở thành khác nhau và chúng ta không thể phân biệt được chúng
nếu chỉ quan tâm đến các giá trị trong trường.
1.3 Mô hình dữ liệu phân cấp
Mô hình dữ liệu phân cấp (Hierachical Data Model) - gọi tắt là mô hình
phân cấp (Hierachical Model). Ở mô hình này một phân cấp chính là một
mạng có nhiều cây, nghĩa là một tập các cây hay còn gọi là rừng, trong đó tất
cả các đường nối chỉ đi theo hướng từ con đến cha. Đường nối ở đây nếu
được biểu diễn bằng một m i tên sẽ đi từ con đến cha để biểu thị khái niệm


11

“xác định duy nhất” chứ không phải là đường duyệt qua cơ sở dữ liệu theo
nghĩa ngược lại.
Các thể hiện của CSDL trong mô hình phân cấp tương ứng với một
lược đồ sẽ chứa một tập các cây có các nút là mẫu tin, mỗi cây được gọi là
một mẫu tin CSDL (database record). Một mẫu tin CSDL tương ứng với một
cây trong lược đồ CSDL và mẫu tin gốc của một mẫu tin CSDL tương ứng
với một thực thể của kiểu mẫu tin gốc.
1.4 Mô hình hƣớng đối tƣợng
Một đặc điểm chung của mô hình hướng đối tượng là chúng hỗ trợ:

Đặc tính nhận dạng đối tượng (Object Identity), các thuộc tính phức
(Complex object), phân cấp theo kiểu (Type hierarchy).
Tập tất cả các cấu trúc đối tượng (Object structure) được định nghĩa
trong mô hình này rất gần với tập các lược đồ cho các mẫu tin CSDL trong
mô hình phân cấp.
Mô hình hướng đối tượng không bị giới hạn trong khái niệm kiểu đối
tượng. Khái niệm cơ bản thực sự là lớp (class), đó là một kiểu đối tượng làm
cấu trúc dữ liệu nền tảng và một tập các phương pháp (method), đó là các
thao tác được thể hiện trên các đối tượng có cấu trúc thuộc về lớp đó.
Mô hình đối tượng gắn liền với mô hình dữ liệu phân cấp theo nghĩa là
nếu được cho trước một lược đồ phân cấp nào đó, ta có thể mô phỏng nó
trong mô hình hướng đối tượng bằng cách xem các con của một nút trong
lược đồ phân cấp như là các trường trong một cấu trúc đối tượng tương ứng n.
Các cấu trúc đối tượng cho các con của n lại có các con của chúng là các
trường...
Mô hình hướng đối tượng có thể diễn tả mọi cấu trúc của mô hình thực
thể - liên kết, nhưng để đảm bảo yêu cầu truy xuất hiệu quả các thông tin cần
thiết trong các cấu trúc đối tượng c ng không phải là một công việc đơn giản.


12

1.5 Mô hình dữ liệu datalog
Mô hình toán học nền tảng của dữ liệu trong datalog biểu thị các quan
hệ. C ng giống như trong định nghĩa hình thức của đại số quan hệ, các quan
hệ này không có các thuộc tính để làm tên của các cột. Chúng là các quan hệ
theo nghĩa “tập danh sách”, ở đó các thành phần xuất hiện theo một thứ tự cố
định và ta tham chiếu đến một cột qua vị trí của nó trong danh sách các đối
của ký hiệu vị từ đã cho.
Trong mô hình dữ liệu datalog có hai cách để định nghĩa quan hệ. Một

vị từ có quan hệ được lưu trữ trong CSDL được gọi là quan hệ CSDL ngoại
xạ (extentional database relation: EDB), trong khi đó những quan hệ được
định nghĩa bởi các quy tắc logic được goi là quan hệ CSDL nội hàm
(intentional database relation: IDB).
Trong mô hình quan hệ, tất cả các quan hệ đều là EDB. Khả năng tạo ra
các khung nhìn (view) trong các mô hình quan hệ tương tự như khả năng định
nghĩa quan hệ IDB trong datalog.
Các chương trình datalog được xây dựng từ những công thức nguyên
tử, đó là những kí hiệu vị từ với một danh sách các đối. Một công thức
nguyên tử biểu thị cho một quan hệ, đó là quan hệ của vị từ được giới hạn
bằng cách:
- Chọn theo đẳng thức giữa một hằng và các thành phần mà ở đó là vị
trí của hằng.
- Chọn theo đẳng thức giữa các thành phần có biến giống nhau.
1.6 Mô hình dữ liệu quan hệ
Khái niệm toán học làm nền tảng cho mô hình quan hệ là các quan hệ
theo lý thuyết tập hợp. Đó là tập con của tích Đề-Các của một danh sách các
miền, mỗi miền đơn giản là một tập các giá trị. Ta có thể xem một quan hệ
như một bảng, trong đó mỗi hàng là một bộ và mỗi cột là một thuộc tính.


13

1.6.1 Quan hệ, thuộc tính, bộ
Định nghĩa 1.1:
Cho U = {A1, A2, ..., An} là một tập hữu hạn các phần tử khác rỗng với
Ai là các thuộc tính. Mỗi thuộc tính Ai (i=l, 2, ..., n) có miền giá trị là
dom(Ai). Khi đó r là một tập các bộ {h1, h2, ..., hm} được gọi là quan hệ trên U
với hj (j=l, 2, ..., m) là một hàm:
DAi sao cho hj(Ai) ∈ DAi (i=l, 2, ..., n)


h j: U →
AiU

Có thể hiểu rằng một quan hệ như một bảng và trong đó mỗi hàng
(phần tử) là một bộ và mỗi cột tương ứng với một thành phần gọi là thuộc
tính. Biểu diễn quan hệ r thành bảng như sau:
h1
h2

A1
h1(A1)
h2(A1)

A2
h1(A2)
h2(A2)

...

...

...

hm

hm(A1)

hm(A2)


...
...
...
...
...

An
h1(An)
h2(An)
...

hm(An)

Bảng 1.1. Biểu diễn quan hệ r
Ví dụ 1.1:
Ta có bảng Sinhvien
MaSV HoTen

NgaySinh DiaChi

Lop

Sv001 Nguyễn Văn A

12/5/1996 VP

CD1-K38

Sv002 Nguyễn Thành B


18/6/1995 HN

CD1-K38

Sv003 Nguyễn Văn C

22/8/1996 BN

CD1-K38

Bảng 1.2. Biểu diễn ví dụ Sinhvien
Trong đó các thuộc tính là MaSV: Mã sinh viên; HoTen: Họ tên;
NgaySinh: Ngày sinh; DiaChi: Địa chỉ; Lop: lớp.
Bộ giá trị: Sv001, A, 12/5/1996, VP, CD1-K38: là một bộ
Nếu có một bộ b = (b1, b2, ..., bm) ∈ r, r xác định trên U, X  U thì
b(X)(hoặc b.X) được gọi là giá trị của tập thuộc tính X trên bộ b.


14

Định nghĩa 1.2:
- Thuộc tính là đặc trưng của đối tượng. Mỗi thuộc tính có một tên
gọi và phải thuộc về một kiểu dữ liệu nhất định.
- Tập tất cả các giá trị có thể có của thuộc tính Ai gọi là miền giá trị
của thuộc tính đó, ký hiệu: Dom(Ai) viết tắt là DAi
Ví dụ 1.2:
Ta có bảng Sinhvien từ ví dụ 1.1
Đối tượng Sinhvien có các thuộc tính như:
Dom(MaSV) = {char(5)} = {„Sv001‟, „Sv002‟, „Sv003‟};
Dom(HoTen) = {char(30)} = („Nguyễn Văn A‟, „Nguyễn Thành B‟,

„Nguyễn Văn C‟};
Dom(NgaySinh) = {date} = {„12/5/1996‟, „18/6/1995‟, „22/8/1996‟};
Dom(DiaChi) = {char(10)} = {„VP‟, „HN‟, „BN‟};
Dom(Lop) = {char(10)} = {CD1-K38};
1.6.2
a)

Đại số quan hệ
Quan hệ khả hợp
Hai lược đồ quan hệ R(A1, A2,..., An) và S(B1, B2,..., Bm) được gọi

là khả hợp nếu: Chúng có cùng bậc: n = m, miền giá trị (Dom) của các
thuộc tính tương ứng bằng nhau: Dom(Ri) = Dom(Si) với 1 ≤ i ≤ n.
b)

Phép hợp
Hai quan hệ r và s khả hợp, phép hợp của 2 quan hệ kí hiệu: r ∪ s là

tập tất cả các bộ thuộc r hoặc thuộc s hoặc thuộc cả hai quan hệ. Ta có
r ∪ s = {t | t ∈ r hoặc t ∈ s}
Ví dụ 1.3:
Cho hai quan hệ Nhanvien1, Nhanvien2 như sau:
Nhanvien1


15

MaNV

Ten


NV01

Nguyễn Văn A

NV02

Nguyễn Văn B

NV03

Nguyễn Văn C

MaNV

Ten

NV01

Nguyễn Văn A

NV04

Nguyễn Văn D

Nhanvien2

Khi đó phép hợp của Nhanvien1 ∪ Nhanvien2
MaNV


Ten

NV01

Nguyễn Văn A

NV02

Nguyễn Văn B

NV03

Nguyễn Văn C

NV04

Nguyễn Văn D

Bảng 1.3. Biểu diễn quan hệ Nhanvien1 ∪ Nhanvien2
c)

Phép giao
Hai quan hệ r và s khả hợp, phép giao của 2 quan hệ kí hiệu: r ∩ s là

tập tất cả các bộ thuộc r và thuộc s. Ta có
r ∩ s = {t | t ∈ r và t ∈ s}
Ví dụ 1.4: Cho hai quan hệ Nhanvien1, Nhanvien2 như sau:
Nhanvien1
MaNV


Ten

NV01

Nguyễn Văn A

NV02

Nguyễn Văn B

NV03

Nguyễn Văn C


16

Nhanvien2
MaNV

Ten

NV01

Nguyễn Văn A

NV04

Nguyễn Văn D


Khi đó phép giao của Nhanvien1 ∩ Nhanvien2
MaNV
NV01

Ten
Nguyễn Văn A

Bảng 1.4. Biểu diễn quan hệ Nhanvien1 ∩ Nhanvien2
d)

Phép trừ
Hai quan hệ r và s khả hợp, phép trừ của 2 quan hệ kí hiệu: r – s là

tập tất cả các bộ thuộc r nhưng không thuộc s. Ta có
r – s = {t | t ∈ r và t

 s}

Ví dụ 1.5:
Cho hai quan hệ Nhanvien1, Nhanvien2 như sau:
Nhanvien1
MaNV

Ten

NV01

Nguyễn Văn A

NV02


Nguyễn Văn B

NV03

Nguyễn Văn C

Nhanvien2
MaNV

Ten

NV01

Nguyễn Văn A

NV04

Nguyễn Văn D

- Phép trừ của Nhanvien1 - Nhanvien2


17

MaNV

Ten

NV02


Nguyễn Văn B

NV03

Nguyễn Văn C

Bảng 1.5. Biểu diễn quan hệ Nhanvien1 - Nhanvien2
- Phép trừ của Nhanvien2 – Nhanvien1
MaNV

Ten

NV04

Nguyễn Văn D

Hình 1.6. Biểu diễn quan hệ Nhanvien2 – Nhanvien1
e)

Tích Đề-Các
Cho 2 quan hệ r và s, r xác định trên U1= {A1, A2,..., An} và s xác

định trên U2{B1, B2,..., Bm}. Tích Đề-Các của 2 quan hệ r và s kí hiệu: r x
s là tập tất cả các bộ thuộc ghép được từ các bộ r và s. Ta có
r x s = {t = (a1, a2, ..., an, b1, b2, ..., bm) | (a1, a2, ..., an) ∈ r và (b1, b2, ..., bm) ∈ s }

Ví dụ 1.6:
Cho 2 quan hệ Nhanvien1, Nhanvien2 như sau:
Nhanvien1

MaNV

Ten

Phong

NV01 Nguyễn Văn A

QTTB

Nguyễn Văn B

TCKT

NV02
Nhanvien2

MaPH

TenPH

QTTB

Quản trị Thiết bị

TCKT

Tài chính kế toán

Tích Đề-Các của Nhanvien1 x Nhanvien2



18

MaNV

Ten

Phong

MaPH

TenPH

NV01

Nguyễn Văn A

QTTB

QTTB

Quản trị Thiết bị

NV01

Nguyễn Văn A

QTTB


TCKT

Tài chính kế toán

NV02

Nguyễn Văn B

TCKT

QTTB

Quản trị Thiết bị

NV02

Nguyễn Văn B

TCKT

TCKT

Tài chính kế toán

Bảng 1.7 Biểu diễn quan hệ Nhanvien1 x Nhanvien2
f)

Phép chiếu
Phép chiếu thực chất là phép toán loại bỏ những thuộc tính không


cần thiết và giữ lại một số thuộc tính cần thiết của quan hệ.
Cho r là một quan hệ xác định trên tập thuộc tính U1= {A1, A2,...,
An}, X là tập con của U1. Phép chiếu của quan hệ r trên tập thuộc tính X
kí hiệu:

 X(r) = {t.X | t ∈ r}

Ví dụ 1.7:
Cho quan hệ Nhanvien
MaNV

Ten

Phong

Luong

NV01 Nguyễn Văn A

QTTB

500

NV02

Nguyễn Văn B

TCKT

600


NV03

Nguyễn Văn C

TCHC

700

NV04 Nguyễn Văn D

TCHC

800

Phép chiếu quan hệ Nhanvien trên hai thuộc tính MaNV và Luong
là:

 MaNV, Luong (Nhanvien)
Sẽ cho ta một quan hệ mới chỉ gồm hai thuộc tính là MaNV và

Luong như sau:


19

MaNV

Luong


NV01

500

NV02

600

NV03

700

NV04

800

Bảng 1.8 Biểu diễn phép chiếu
g)

 MaNV, Luong (Nhanvien)

Phép chọn
Phép chọn là phép toán lọc lấy ra một tập con các bộ của quan hệ

đã cho thoả mãn một điều kiện xác định. Điều kiện đó được gọi là điều
kiện chọn hay biểu thức chọn.
Biểu thức chọn G được định nghĩa là một tổ hợp logic của các toán
hạng, mỗi toán hạng là một phép so sánh đơn giản giữa hai biến là hai
thuộc tính hoặc giữa một biến là một thuộc tính và một giá trị hằng. Biểu
thức chọn G cho giá trị đúng hoặc sai đối với mỗi bộ đã cho của quan hệ

khi kiểm tra riêng bộ đó.
Các phép toán so sánh và logic trong biểu thức G: >, <, =,≥, ≤, ≠,
,  , .

Cho quan hệ r và G là một biểu thức logic trên các thuộc tính của r.
Phép chọn trên quan hệ r với biểu thức chọn G kí hiệu:
các bộ của r thoả mãn G. Ta có

δ G(r) là tập tất cả

δ G(r) = {t | t ∈ r và G(t)}

Ví dụ 1.8:
Cho quan hệ Nhanvien
TT
1

MaNV

Ten

NV01 Nguyễn Văn A

Phong

Luong

QTTB

500



20

2

NV02

Nguyễn Văn B

TCKT

600

3

NV03

Nguyễn Văn C

TCHC

700

4

NV04 Nguyễn Văn D

TCHC


800

5

NV05

Nguyễn Văn E

TCHC

900

Tìm nhân viên ở phòng TCHC và có Lương lớn hơn 700?
Khi đó phép chọn Phòng TCHC và có lương > 700 của quan hệ
Nhanvien được biểu diễn bằng công thức sau:

δ (Phong=TCHC  Luong > 700) (Nhanvien)
ta được quan hệ sau:
TT

MaNV

Ten

Luong

4

NV04 Nguyễn Văn D


TCHC

800

5

NV05

Nguyễn Văn E

TCHC

900

Bảng 1.9 Biểu diễn phép chọn
h)

Phong

δ (Phong=TCHC  Luong > 700) (Nhanvien)

Phép kết nối
Phép kết nối là một phép ghép các bộ giá trị của quan hệ mà đi kèm

là có điều kiện.
Cho 2 quan hệ r(U) và s(V). Đặt X= U ∩ V. Phép kết nối hai quan
hệ r(U) và s(V), kí hiệu r*s, cho ta quan hệ giữa các bộ được gán từ các
bộ u của quan hệ R với mỗi bộ v của quan hệ S (sao cho các giá trị trên
miền thuộc tính chung X của hai bộ này giống nhau).
P(UV) = r*s={u*v | u ∈ r, v ∈ s, u.X=v.X}.

Nếu X= U ∩ V = ∅, thì r*s sẽ cho ta tích Đề-Các mà trong đó mỗi
bộ của quan hệ r sẽ được ghép với mỗi bộ của quan hệ s .
Ví dụ 1.9:
Cho quan hệ r


21

A

B

C

A1

A1

3

A1

B1

8

B1

A1


8

B1

B1

9

và quan hệ s
A

C

A1

3

A1

6

B1

9

Khi đó phép kết nối của 2 quan hệ r*s là
A

B


C

A1

A1

3

B1

B1

9

Bảng 1.10 Biểu diễn phép kết nối r*s
i)

Phép chia
Cho 2 quan hệ r(U) và s(V) với V  U. Phép chia của quan hệ r

cho quan hệ s kí hiệu là r÷s là tập tất cả các bộ t trên U\V sao cho với
mọi bộ v ∈ s thì khi ghép bộ t với bộ v ta được một bộ thuộc r. Ta có
r÷s = {t | ∀ v ∈ s, (t,v) ∈ r}
Ví dụ 1.10:
Cho quan hệ r
A

B

A1


3

A1

6


22

B1

3

B1

6

C1

8

và quan hệ s
B
3
6
Khi đó phép chia 2 quan hệ r ÷ s là:
A
A1
B1

Bảng 1.11 Biểu diễn phép chia r ÷ s
1.6.3

Phụ thuộc hàm, hệ tiền đề Armstrong

a) Phụ thuộc hàm
Định nghĩa1.3:
Cho quan hệ r xác định trên tập thuộc tính U, trong đó X, Y  U. Ta
nói rằng X xác định hàm Y hay Y phụ thuộc hàm vào X trên lược đồ
quan hệ và kí hiệu: X → Y, nếu r là một quan hệ nào đó xác định trên
lược đồ quan hệ R thỏa mãn
 t1, t2 ∈ r sao cho t1.(X)=t2.(X) thì t1.(Y)=t2.(Y).

Khi xét đến mối quan hệ dữ liệu trong CSDL quan hệ một trong
những yếu tố quan trọng được xét đến là sự phụ thuộc giữa các thuộc
tính này với thuộc tính khác. Từ đó có thể xây dựng những ràng buộc dữ
liệu c ng như loại bỏ đi những dư thừa dữ liệu trong một CSDL.


23

Phụ thuộc hàm là những mối quan hệ giữa các thuộc tính trong
CSDL quan hệ. Khái niệm về phụ thuộc hàm có một vai trò quan trọng
trong việc thiết kế mô hình dữ liệu. Một trạng thái phụ thuộc hàm chỉ ra
rằng giá trị của một thuộc tính được quyết định một cách duy nhất bởi
giá trị của thuộc tính khác. Sử dụng các phụ thuộc hàm để chuẩn hóa
lược đồ quan hệ về dạng chuẩn 3 hoặc chuẩn Boyce-Codd.
b) Các tính chất của phụ thuộc hàm
Cho lược đồ quan hệ R xác định trên tập thuộc tính U={Al, A2, ...,
An}, cho X, Y, Z, W  U, ta có một số tính chất cơ bản của các phụ thuộc

hàm như sau:
1) Nếu Y  X thì X → Y.
2) Nếu X → Y thì XW → YW.
3) Nếu X → Y, Y → Z thì X → Z.
4) Nếu X → Y, YZ → W thì XZ → W.
5) Nếu X → Y, Z → W thì XZ → YW.
6) Nếu X → Y thì XZ → Y.
7) Nếu X → Y, X → Z thì X → YZ.
8) Nếu X → YZ thì X → Y.
9) Nếu X → YZ, Z → WV thì X → YZW.
Ví dụ 1.11: Cho quan hệ r như sau:
A

B

C

D

2

4

5

6

4

2


6

7

5

5

7

8

3

2

6

9

Những quan hệ nào sau đâu không thỏa r? Tại sao?
F = {A → B, BC → D, C → A}