Tài liu lun vn s phm 1 of 63.

TRƯỜNG ĐẠI HỌC SƯ PHẠM HÀ NỘI 2
VIỆN CÔNG NGHỆ THÔNG TIN
======

PHẠM THỊ NHƯ QUỲNH

MỘT SỐ TÍNH CHẤT CỦA KHÓA
TRÊN KHỐI VÀ TRÊN LÁT CẮT

KHÓA LUẬN TỐT NGHIỆP ĐẠI HỌC
Chuyên ngành: Sư phạm tin học

HÀ NỘI - 2019

Footer Page 1 of 63.


Tài liu lun vn s phm 2 of 63.

TRƯỜNG ĐẠI HỌC SƯ PHẠM HÀ NỘI 2
VIỆN CÔNG NGHỆ THÔNG TIN
======

PHẠM THỊ NHƯ QUỲNH

MỘT SỐ TÍNH CHẤT CỦA KHÓA
TRÊN KHỐI VÀ TRÊN LÁT CẮT
KHÓA LUẬN TỐT NGHIỆP ĐẠI HỌC
Chuyên ngành: Sư phạm Tin học


Tài liu lun vn s phm 4 of 63.

LỜI CAM ĐOAN
Tôi xin cam đoan khóa luận này được hoàn thành bằng sự cố gắng, nỗ
lực của bản thân, dưới sự hướng dẫn tận tình của PGS.TS. Trịnh Đình
Thắng và tham khảo một số tài liệu đã được ghi rõ nguồn.
Khóa luận hoàn toàn không sao chép từ tài liệu có sẵn nào. Kết quả
nghiên cứu không trùng lặp với các tác giả khác.
Nếu sai, tôi xin hoàn toàn chịu trách nhiệm!

Hà nội, ngày 05 tháng 05 năm 2019.
Người cam đoan

Phạm Thị Như Quỳnh

Footer Page 4 of 63.


Tài liu lun vn s phm 5 of 63.

DANH MỤC CÁC KÍ HIỆU, CHỮ CÁI VIẾT TẮT

Kí hiệu
LĐQH
PTH

Lược đồ quan hệ
Phụ thuộc hàm


Chứa



Thuộc



Không thuộc

X+

Footer Page 5 of 63.

Ý nghĩa

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



Tương đương



Rỗng



Tồn tại



CHƯƠNG 3. MỐI QUAN HỆ GIỮA KHÓA CỦA LƯỢC ĐỒ KHỐI VÀ
LƯỢC ĐỒ LÁT CẮT ................................................................................... 34
3.1. Khóa của lược đồ khối và lược đồ lát cắt. ............................................... 34
3.2. Mối quan hệ giữa khóa của lược đồ khối và khóa của lược đồ lát cắt qua
phép dịch chuyển............................................................................................. 35
3.3. Một số tính chất mới trong mối quan hệ giữa khóa của lược đồ khối và
lược đồ lát cắt. ................................................................................................. 44
KẾT LUẬN .................................................................................................... 50
TÀI LIỆU THAM KHẢO ............................................................................ 51

Footer Page 7 of 63.


Tài liu lun vn s phm 8 of 63.

DANH MỤC BẢNG BIỂU
Bảng 1.1: Biểu diễn quan hệ r. ........................................................................ 5
Bảng 1.2: Biểu diễn quan hệ Khachhang. ....................................................... 5
Bảng 1.3: Biểu diễn các quan hệ KH1, KH2 và KH1 ∪ KH2.. ...................... 7
Bảng 1.4: Biểu diễn các quan hệ KH1, KH2 và KH1 ∩ KH2. ....................... 7
Bảng 1.5: Biểu diễn các quan hệ KH1, KH2 và KH1 – KH2.. ....................... 8
Bảng 1.6: Biểu diễn các quan hệ r, s và r × s.. ................................................ 9
Bảng 1.7: Biểu diễn các quan hệ KH, ∏𝑀𝑎𝐾𝐻,𝑇𝑒𝑛𝐾𝐻,𝐷𝑖𝑎𝐶ℎ𝑖 (KH). ................ 10
Bảng 1.8: Biểu diễn các quan hệ KH, δDiaChi=’Thái Bình’(KH). ......................... 11
Bảng 1.9: Biểu diễn quan hệ r÷s. .................................................................. 13
Bảng 1.10: Biểu diễn quan hệ Khachhang.. .................................................. 14
Bảng 2.1: Biểu diễn lát cắt r(R2/2019).. ........................................................... 20

Footer Page 8 of 63.

đã được đề xuất, đó là mô hình dữ liệu dạng khối. Mô hình dữ liệu này có thể
xem là một mở rộng của mô hình dữ liệu quan hệ.
Trong quản lý cơ sở dữ liệu (CSDL), khóa của quan hệ là thuộc tính có
thể suy ra được các thuộc tính còn lại và nó cũng là yếu tố liên kết giữa các
(CSDL) với nhau. Nhờ có khóa mà hệ quản trị (CSDL) có thể quản lý tốt việc
cập nhập dữ liệu.
Để góp phần hoàn chỉnh về mô hình dữ liệu dạng khối và tìm hiểu về
mối quan hệ giữa khóa trên khối và trên lát cắt, tôi đã lựa chọn đề tài “Một số
tính chất của khóa trên khối và trên lát cắt” cho khóa luận tốt nghiệp của
mình.
2. Mục đích nghiên cứu
- Tìm hiểu khái quát về mô hình dữ liệu dạng khối.
- Các tính chất của khóa trên khối và trên lát cắt.
- Phát biểu và chứng minh một số tính chất mới của khóa trên lược đồ
khối và mối quan hệ của khóa trên lược đồ khối và khóa trên lược đồ
lát cắt.

Footer Page 10 of 63.

1


Tài liu lun vn s phm 11 of 63.

3. Nhiệm vụ nghiên cứu
- Tìm hiểu về mô hình dữ liệu dạng khối và các tính chất của khóa trên
lược đồ khối và lược đồ lát cắt.
- Phát biểu và chứng minh một số tính chất mới của khóa trên lược đồ
khối và mối quan hệ của khóa trên lược đồ khối và khóa trên lược đồ
lát cắt.

một số tính chất mới trong mối quan hệ giữa khóa của lược đồ khối và lược
đồ lát cắt.

Footer Page 12 of 63.

3


Tài liu lun vn s phm 13 of 63.

CHƯƠNG I: MÔ HÌNH DỮ LIỆU QUAN HỆ
Chương này trình bày một số khái niệm cơ bản trong mô hình dữ liệu
quan hệ: các phép toán, phụ thuộc hàm, bao đóng của tập phụ thuộc hàm, bao
đóng của tập thuộc tính, các tính chất của khóa cùng với thuật toán tìm khoá.
Các vấn đề trình bày ở chương này được tham khảo trong các tài liệu [2], [4],
[5], [6].
1.1. Các khái niệm
1.1.1. Thuộc tính và miền thuộc tính
Định nghĩa 1.1 [4]
Thuộc tính
Thuộc tính là các đặc điểm riêng của một đố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.
Ví dụ 1.1: Đối tượng Khachhang có các thuộc tính là mã khách hàng,
tên khách hàng, giới tính, địa chỉ, số điện thoại. Khi đó ta có thể biểu diễn đối
tượng khách hàng như sau:
Khachhang(MaKH, TenKH, GT, DiaChi, SDT)
Miền giá trị
Tập hợp các giá trị mà thuộc tính 𝐴𝑖 có thể nhận được gọi là miền giá
trị của thuộc tính A, được kí hiệu là Dom(𝐴𝑖 ), viết tắt là 𝐷𝐴𝑖 .
Ví dụ 1.2:

diễn quan hệ r thành bảng như sau:
A1

A2

...

An

h1

h1(A1)

h1(A2)

...

h1(An)

h2

h2(A1)

h2(A2)

...

h2(An)

...


SDT

KH01

Phạm Mai An

Nữ

Thái Bình

0363124614

KH02

Lê Xuân Bình

Nam

KH03

Vũ Bích Phượng

Nữ

Hà Nội

0338795622

KH04

U = {A1, A2,..., An} được gọi là R(U) hoặc R(A1, A2,..., An).
1.2. Các phép toán đại số trên quan hệ
1.2.1. Phép hợp
Hai quan hệ r và s được gọi là khả hợp nếu như hai quan hệ này xác
định cùng tập thuộc tính và các thuộc tính cùng tên có cùng miền giá trị.
Cho hai quan hệ r và s khả hợp. Hợp của r và s kí hiệu là 𝑟 ∪ 𝑠 là quan
hệ gồm tất cả các bộ thuộc r hoặc thuộc s. Phép hợp được biểu diễn như sau:
𝑟 ∪ 𝑠 = {𝑡| 𝑡 ∈ 𝑟 ∨ 𝑡 ∈ 𝑠}
Ví dụ 1.4: Cho 2 quan hệ KH1 và KH2:
KH1
MaKH

TenKH

DiaChi

KH01

Phạm Mai An

Thái Bình

KH02

Lê Xuân Bình

Hải Phòng

KH03



KH1 ∪ KH2:
MaKH

TenKH

DiaChi

KH01

Phạm Mai An

Thái Bình

KH02

Lê Xuân Bình

Hải Phòng

KH03

Vũ Bích Phượng

Hà Nội

KH04

Phạm Văn Quang


Vũ Bích Phượng

Hà Nội

MaKH

TenKH

DiaChi

KH01

Phạm Mai An

Thái Bình

KH04

Phạm Văn Quang

Thái Bình

MaKH

TenKH

DiaChi

KH01


KH01

Phạm Mai An

Thái Bình

KH02

Lê Xuân Bình

Hải Phòng

KH03

Vũ Bích Phượng

Hà Nội

MaKH

TenKH

DiaChi

KH01

Phạm Mai An

Thái Bình


1.2.4. Tích Đề-các
Cho hai quan hệ r và s bất kỳ có tập thuộc tính lần lượt 𝑈1 𝑣à 𝑈2 với
𝑈1 ∩ 𝑈2 = ∅. Tích Đề-các của r và s kí kiệu là: 𝑟 × 𝑠 là một quan hệ trên
𝑈1 ∪ 𝑈2 gồm tất cả các bộ ghép được từ 2 quan hệ r và s.
Phép Tích Đề-các được biểu diễn như sau:
𝑟 × 𝑠 = {(𝑢, 𝑣)| ∀𝑢 ∈ 𝑟, ∀𝑣 ∈ 𝑠}

Footer Page 17 of 63.

8


Tài liu lun vn s phm 18 of 63.

Ví dụ 1.7: Cho hai quan hệ r và s:
r

s

MaKH

MaSP HoaDon

TenSP

SoLuong

KH01

SP01

SP01

0805

Ti Vi

10

KH01

SP02

0805

Điều Hòa

15

KH02

SP01

0806

Ti Vi

10

KH02



GT

DiaChi

SDT

KH01

Phạm Mai An

Nữ

Thái Bình

0363124614

KH02

Lê Xuân Bình

Nam

Hải Phòng

0987654777

KH03

Vũ Bích Phượng


Hải Phòng

KH03

Vũ Bích Phượng

Hà Nội

Bảng 1.7: Biểu diễn quan hệ KH, ∏𝑀𝑎𝐾𝐻,𝑇𝑒𝑛𝐾𝐻,𝐷𝑖𝑎𝐶ℎ𝑖(𝐾𝐻)

1.2.6. Phép chọn
Phép chọn là phép toán học lấy ra một tập con các bộ của quan hệ đã
cho thỏa 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 F được định nghĩa là một tổ hợp logic của 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 F 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 trong biểu thức F: >,
Nam

Hải Phòng

0987654777

KH03

Vũ Bích Phượng

Nữ

Thái Bình

0338795622

KH04

Phạm Văn Quang

Nam

Thái Bình

0338990001

KH05

Phạm Như Quỳnh



Vũ Bích Phượng

Nữ

Thái Bình

0338795622

KH04

Phạm Văn Quang

Nam

Thái Bình

0338990001

Bảng 1.8: Biểu diễn các quan hệ KH, δDiaChi=’Thái Bình’(KH)

1.2.7. Phép kết nối
Cho quan hệ r(U) và s(V). Đặt M= U ∩ V. Phép kết nối tự nhiên hai
quan hệ r(U) và s(V), ký hiệu r*s, cho ta quan hệ gồm các bộ được dán từ

Footer Page 20 of 63.

11




a3 2

2

a2

3

r*s (A B

C

D)

a1 1

2

1

a2 1

2

2

a2 1

1

Phạm Mai An

1

4

5

Lê Xuân Bình

5

2

2

Vũ Bích Phượng

2

1

1

s
Ti Vi

Điều Hòa

Tủ Lạnh


Tài liu lun vn s phm 23 of 63.

Nói rằng X → Y (đọc là X xác định hàm Y hay Y phụ thuộc hàm vào
X) nếu với mọi quan hệ r xác định trên U sao cho bất kỳ hai bộ t1, t2 ∈ r mà
t1(X) = t2(X) thì t1(Y) = t2(Y).
Ví dụ 1.12: Ta có quan hệ Khachhang như sau:
MaKH

TenKH

GT

DiaChi

KH01

Phạm Mai An

Nữ

Thái Bình 0363124614

KH02

Lê Xuân Bình

Nam

Hải Phòng 0987654777

1) Nếu Y  X thì X → Y
2) Nếu X → Y thì XW → YW (Tính mở rộng hai vế)
3) Nếu X → Y, Y → Z thì X → Z (Tính chất bắc cầu)
4) Nếu X → Y, YZ → W thì XZ → W (Tính tựa bắc cầu)
5) Nếu X → Y, Z → W thì XZ → YW (Tính cộng đầy đủ)
6) Nếu X → Y thì XZ → Y (Tính mở rộng vế phải)
7) Nếu X → Y, X → Z thì X → YZ (Tính cộng ở vế phải)
8) Nếu X → YZ thì X → Y (Tính bộ phận ở vế phải)
9) Nếu X → YZ, Z → W thì X → YZW (Tính lũy đẳng)

Footer Page 23 of 63.

14


Tài liu lun vn s phm 24 of 63.

1.3.2. Hệ tiên đề Armstrong cho các phụ thuộc hàm
Gọi R là quan hệ trên tập thuộc tính U = {A1, A2,..., An}. Khi đó với
các tập thuộc tính X, Y, Z ⊆ U, ta có hệ tiên đề Amstrong như sau:
1) Phản xạ: Nếu Y ⊆ X thì X → Y.
2) Tăng trưởng: Nếu Z ⊆ R và X → Y thì XZ → YZ.
3) Bắc cầu: Nếu X → Y, Y → Z thì X → Z.
Trong đó, ký hiệu XZ là hợp của hai tập X và Z (thay cho kí hiệu X ∪ Z).
1.4. Bao đóng
1.4.1. Bao đóng của tập phụ thuộc hàm
Định nghĩa 1.5 [5]
Giả sử F là tập các phụ thuộc hàm trên sơ đồ quan hệ s = <R, F>. Gọi
F+ là tập tất cả các phụ thuộc hàm có thể suy dẫn logic từ F bởi các luật của hệ
tiên đề Armstrong. Khi ấy F+ được gọi là bao đóng của F.

3) Tính lũy đẳng: 𝑋 ++ = 𝑋 +
4) 𝑋 + 𝑌 + ⊆ (𝑋𝑌)+
5) (𝑋 + 𝑌)+ = (𝑋𝑌 + )+ = (𝑋 + 𝑌 + )+ = (𝑋𝑌)+
6) 𝑋 → 𝑌 ⇔ 𝑌 + ⊆ 𝑋 +
7) 𝑋 → 𝑋 + và 𝑋 + → 𝑋
8) 𝑋 + = 𝑌 + ⇔ 𝑋 → 𝑌 𝑣à 𝑌 → 𝑋
Thuật toán 1 (tìm bao đóng):
Ta xây dựng tập các thuộc tính 𝑋0 , 𝑋1 , 𝑋2 , 𝑋3 , 𝑋4 …. như sau:
Bước 1: 𝑋0 =X.
Bước 2: Lần lượt xét các phụ thuộc hàm của F, nếu 𝑌 → 𝑍 𝑐ó 𝑌 ⊆ 𝑋𝑖
thì 𝑋𝑖+1 = 𝑋𝑖 ∪ 𝑍. 𝐿𝑜ạ𝑖 𝑝ℎụ 𝑡ℎ𝑢ộ𝑐 ℎà𝑚 𝑌 → 𝑍 khỏi F.
Bước 3: Nếu ở bước 2 không tính được 𝑋𝑖+1 thì 𝑋𝑖 chính là bao đóng của X.
Ngược lại ta quay về bước 2.
Ví dụ 1.14: Cho lược đồ quan hệ R=(U,F) với U={A,B,C,D,E,K}
và F={C → N, B → CN, BN → CD, AMN → BC, CN → AM}
Tìm bao đóng của phần tử X={C} dựa trên F?
Giải:
Bước 1: Chọn 𝑋0 = 𝐶
Bước 2: Lần lượt xét các phụ thuộc hàm của F, ta thấy có C→N thỏa mãn
nên: X1 = C ∪ N = CN.
Lặp lại bước 2: Ta lại gặp CN → AM thỏa mãn nên X2 = CNAM
Tương tự ta có:
X3 = CNAMB (áp dụng AMN → BC)
X4 = CNAMBD (áp dụng BN → CD)
vậy (C)+ = ABCDMN

Footer Page 25 of 63.

16