..

ĐẠI HỌC THÁI NGUYÊN
TRƯỜNG ĐẠI HỌC CÔNG NGHỆ THÔNG TIN VÀ TRUYỀN THÔNG

NGÔ HUY THẮNG

BẢNG CÂU VẤN TIN TRÊN CÁC QUAN HỆ
VÀ XỬ LÝ CÂU VẤN TIN TRÊN BẢNG

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

Thái Ngun, năm 2012

Số hóa bởi Trung tâm Học liệu – Đại học Thái Nguyên




I

LỜI CẢM ƠN
Những kiến thức căn bản trong luận văn này là kết quả của quá trình tự
nghiên cứu trong q trình cơng tác và hai năm học Thạc sỹ (2010 - 2012) tại
Trường Đại học Công nghệ thông tin và Truyền thông Thái Nguyên. Dưới sự
giảng dạy, đào tạo và dìu dắt trực tiếp của các thầy cơ trong trường và Viện
Công nghệ thông tin Việt Nam.
Tôi xin bày tỏ lời cảm ơn chân thành tới các thầy cô trong Khoa Cơng
nghệ thơng tin, Phịng Đào tạo, Phịng Cơng tác học sinh sinh viên, Phòng
Đào tạo sau đại học Trường Đại học Công nghệ thông tin và Truyền thông
Thái Nguyên, đã tạo điều kiện thuận lợi cho tôi trong thời gian học tập tại

trường.
Tơi xin bày tỏ lịng biết ơn chân thành, lời cảm ơn sâu sắc nhất đối với
thầy giáo PGS.TS Lê Huy Thập đã trực tiếp hướng dẫn, định hướng cho tôi
giải quyết các vấn đề trong luận văn.
Tôi cũng xin cảm ơn đến các anh chị đồng nghiệp ở Sở Thông tin và
Truyền thông tỉnh Bắc Kạn, người thân, bạn bè và các bạn đồng môn lớp cao
học CH 9A, đã ủng hộ và giúp đỡ tơi trong q trình làm luận văn tốt nghiệp.
Thái Ngun, ngày 15 tháng 8 năm 2012
Học viên

Ngơ Huy Thắng

Số hóa bởi Trung tâm Học liệu – Đại học Thái Nguyên




II

LỜI CAM ĐOAN
Với mục đích nghiên cứu, tìm hiểu để nâng cao kiến thức và trình độ
chun mơn để áp dụng trong các bài toán cụ thể trong tương lai nên tôi đã
làm luận văn này một cách nghiêm túc và hoàn toàn trung thực. Nội dung
luận văn do tự tơi tìm hiểu và hồn thành.
Trong luận văn, tơi có sử dụng tài liệu tham khảo của một số tác giả
trong và ngoài nước để hoàn thành luận văn được nêu ở phần tài liệu tham
khảo.
Tôi xin cam đoan và chịu trách nhiệm về nội dung, sự trung thực trong
luận văn tốt nghiệp Thạc sỹ của mình.
Thái Nguyên, Ngày 15 tháng 8 năm 2012

Học viên

Ngơ Huy Thắng

Số hóa bởi Trung tâm Học liệu – Đại học Thái Nguyên




III

MỤC LỤC
LỜI CẢM ƠN …………….………………….………………………………

I

LỜI CAM ĐOAN ………………….…………………………………………

II

MỤC LỤC ………………….…………………………………………………

III

BẢNG CÁC KÝ HIỆU …………………….……………………………….

V

BẢNG CÁC CHỮ VIẾT TẮT …….……………………………………


VI

DANH MỤC HÌNH VẼ ……………………………………………………

VII

DANH MỤC BẢNG BIỂU ………………………..………………………

VIII

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

10

CHƯƠNG I: TỔNG QUAN VỀ CƠ SỞ DỮ LIỆU QUAN HỆ ……

11

1.1.Khái quát về cơ sở dữ liệu ……………………………………...………

11

1.1.1. Những vấn đề mà CSDL cần phải giải quyết ………..………

12

1.1.2. Ðịnh nghĩa Hệ thống cơ sở dữ liệu (Database Systems) .…

13


1.1.3. Cơ sở dữ liệu quan hệ và lược đồ cơ sở dữ liệu quan hệ ….

14

1.2.Các loại câu vấn tin SQL ………………………………………………

17

1.3.Phương pháp chuyển câu vấn tin SQL sang câu vấn tin đại số quan hệ AQL

19

1.3.1. Ngôn ngữ truy vấn đại số quan hệ (AQL) ……………….……

20

1.3.2. Các phép biến đổi tương đương trong đại số quan hệ ……..…

22

1.3.3. Thuật toánchuyển câu vấn tin SQL sang câu vấn tin đại số quan hệ AQL

25

1.4.Kết luận chương 1 ………………………………….……………………

32

CHƯƠNG II: PHƯƠNG PHÁP TÁCH GỘP CÁC HÀNG – CỘT


33

2.1. Phương pháp chuyển câu vấn tin đại số quan hệ sang bảng .……

34

2.1.1. Mục tiêu của xử lý vấn tin …………………………….…………

35

2.1.2. Mô tả đặc trưng của xử lý vấn tin …………...…………………

35

2.2. Định nghĩa và cách thể hiện câu truy vấn bằng bảng ….............…

37

Số hóa bởi Trung tâm Học liệu – Đại học Thái Nguyên




IV

2.2.1. Cách thể hiện bảng vấn tin đại số quan hệ …………..………

38

2.2.2. Độ phức tạp của phép toán đại số quan hệ ……………...……


40

2.3. Phương pháp tách gộp hàng trong bảng vấn tin ……………...……

40

2.3.1.Kỹ thuật Gộp các hàng – cột ………………………...…………

41

2.3.2. Kỹ thuật Tách các hàng – cột ………………….………………

44

2.3. Kết luận chương 2 ………………………………………………………

51

CHƯƠNG III: ỨNG DỤNG GIẢI BÀI TOÁN CỤ THỂ ……….……

52

3.1. Cách tính tải trên hàng và các phân hoạch của bảng vấn tin ……

52

3.1.1. Phân hoạch bảng vấn tin………………….……………………..

53


3.1.2. Cách tính tải trên hàng ………………….…………………….…

53

3.2. Phương pháp tìm Cell có chi phí truyền thơng lớn …….…………

56

3.3. Thuật tốn tạo ra bảng vấn tin tiền xử lý ……………….…..………

58

3.4. Ví dụ minh họa ………………….…………………….…………………

61

3.4.1. Cây tối ưu cho truy vấn dạng ống có cân bằng tải …………

61

3.4.2. Thuật tốn chia cơng việc ………………………………………

61

3.4.3. Mở rộng thuật tốn nhát cắt cục bộ cho bài toán POM ……

62

3.5.Kết luận chương 3 ………………………………………………………


68

KẾT LUẬN …………………………………………………………...………

69

HƯỚNG PHÁT TRIỂN ……………………………………………………

70

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

71

Số hóa bởi Trung tâm Học liệu – Đại học Thái Nguyên




V

BẢNG CÁC KÝ HIỆU

∩

Phép giao

∪


Phép hợp

∈

Ký hiệu thuộc

−

Phép trừ

×

Tích đề các

⋈

Phép nối
Phép chiếu
Tê ta

*

Kết nối tự nhiên

÷

Phép chia

∧


Phép và

∨

Phép hoặc
Phép chọn

⊆

Tập con

Số hóa bởi Trung tâm Học liệu – Đại học Thái Nguyên




VI

BẢNG CÁC CHỮ VIẾT TẮT
SQL

Structured Query Language – Ngôn ngữ truy vấn dữ liệu

CSDL

Cơ sở dữ liệu

HQTCSDL

Database management system - Hệ quản trị Cơ Sở Dữ Liệu


AQL

Algebraic Query Language (Ngôn ngữ vấn tin đại số)

POT

Pipeline Operator Tree – Cây toán tử dạng ống

POM

Pipeline Operator Matrix – Ma trận toán tử dạng ống

QH

Quan hệ

QHi

Quan hệ i, i = 1, 2,3,…

Ip

Isomorphous – Ma trận đặc trưng

Cell

Ơ

Số hóa bởi Trung tâm Học liệu – Đại học Thái Nguyên





VII

DANH MỤC HÌNH VẼ
Hình 1.1. Mơ hình xử lí thơng tin …………………………………………

11

Hình 1.2. Mơ hình hệ thống cơ sở dữ liệu ………………………………

13

Hình 1.3. Cây đại số quan hệ ví dụ ………………………………………

31

Hình 2.1. Gộp hai đỉnh i và j thành đỉnh m ……………………………..

43

Hình 2.2. Tách hai đỉnh i và j ……………………………………………..

46

Hình 2.3. Cắt các cạnh của cây tốn tử …………………………………

50


Hình 2.4. Gộp các đỉnh của cây tốn tử …………………………………

50

Hình 3.1. Cây tốn tử tổng qt …………………………………………

59

Hình 3.2. Cây tốn tử đã được tiền xử lí ………………………………….

60

Hình 3.3. Thuật tốn nhát cắt cục bộ ……………………………………

64

Hình 3.4. Cây tốn tử gốc …………………………..………………………

65

Số hóa bởi Trung tâm Học liệu – Đại học Thái Nguyên




VIII

DANH MỤC BẢNG BIỂU
Bảng 1.1. Bảng quan hệ NHANVIEN ……………………….….………


15

Bảng 1.2. Bảng quan hệ DONVI ……………………….…………………

16

Bảng 1.3. Bảng quan hệ DONVI_DIADIEM ……………….…………

16

Bảng 1.4. Bảng quan hệ DUAN ………………..…………………………

16

Bảng 1.5. Bảng quan hệ NHANVIEN_DUAN ……..…………………

17

Bảng 2.1. Bảng vấn tin dạng đại số quan hệ …………………………

39

Bảng 2.2. Toán tử Collapse (i,j) gốc ………………………………………

42

Bảng 2.3. Toán tử Collapse (i,j) sau khi gộp i,j …………………………

42


Bảng 2.4. POM dữ liệu …………………………………………………….

43

Bảng 2.5. POM sau khi gộp ………………………………………………

44

Bảng 2.6. Toán tử cut(i,j) gốc ………………………………………………

45

Bảng 2.7.Toán tử cut(i,j) sau khi gộp i,j ………………………………

45

Bảng 2.8. Dữ liệu POM ……………………………………………………

46

Bảng 2.9 POM1 ………………………………………………………………

47

Bảng 2.9a. POM1,1 ………………………………………………………….

47

Bảng 2.9b. POM 1,2 ………………………………..………………………..


47

Bảng 2.10. POM4 …………………………………………………………….

47

Bảng 2.11. Ma trận Ip truy vấn …………………………………………

48

Số hóa bởi Trung tâm Học liệu – Đại học Thái Nguyên




IX

Bảng 2.12. Ma trận Ip truy vấn mảnh F1 ………………………………

48

Bảng 2.13. Ma trận Ip truy vấn mảnh F2 ……………………………….

48

Bảng 2.14. Ma trận Ip truy vấn mảnh F3 ……………………………

49


Bảng 2.15. Ma trận Ip truy vấn lớp mảnh F1 …………………………

49

Bảng 2.16. Ma trận Ip truy vấn lớp mảnh F2 …………………………

49

Bảng 2.17. Ma trận Ip truy vấn lớp mảnh F3 …………………………

49

Bảng 3.1. Bảng truy vấn Ip với các phép toán đại số quan hệ ..……

54

Bảng 3.2. Các ti và cellij của Ip ……………………………………………

55

Bảng 3.3. Ma trận Ip tương ứng với cây toán tử gốc …………………

58

Bảng 3.4. Gộp các cạnh có trọng số lớn đã qua tiền xử lí …………..

60

Bảng 3.5. Ip truy vấn tương ứng với cây toán tử gốc …………..………


65

Bảng 3.6. Phân hoạch F1 …………..………………………………………

66

Bảng 3.7. Phân hoạch F2 …………..………………………………………

66

Bảng 3.8. Phân hoạch F3 …………..………………………………………

67

Bảng 3.9. Phân hoạch F4 …………..………………………………………

67

Bảng 3.10. Phân hoạch F5 …………..……………………….……………

67

Bảng 3.11. Phân hoạch F6 …………..……………………………………

68

Số hóa bởi Trung tâm Học liệu – Đại học Thái Nguyên





10

MỞ ĐẦU
Để thể hiện câu vấn tin SQL bằng bảng trước hết chúng ta chuyển nó sang
câu vấn tin đại số quan hệ, sau đó thể hiện câu vấn tin này bằng một bảng gọi là
bảng truy vấn. Các tiêu đề hàng và cột sẽ là tên các quan hệ cơ sở, các quan hệ
trung gian hoặc kết qủa thực hiện câu vấn tin. Các Cell sẽ là các toán tử để thực
hiện các phép toán đại số quan hệ nhằm sinh ra các quan hệ trung gian. Cùng với
tiêu đề hàng và cột ta sẽ gán một trọng số nào đó - là chi phí xử lý phép tốn trên
quan hệ đó; các Cell cũng được gán trọng số là chi phí chuyển số liệu từ tốn tử
nằm trên hàng đến toán tử nằm trên cột. Minh họa xử lý câu vấn tin bằng bảng
truy vấn sẽ được thực hiện cho việc tìm cây tốn tử tiền xử lý. Tức là phân chia
các toán tử cho các bộ xử lý để thời gian trả lời truy vấn nhỏ nhất.
Nội dung của luận văn gồm 3 chương:
Chương I: Tổng quan về cơ sở dữ liệu quan hệ. Trong chương này
cung cấp các kiến thức lý thuyết cơ bản những khái niệm về CSDL quan hệ,
các loại câu vấn tin và phương pháp chuyển đổi câu vấn tin SQL sang câu vấn
tin đại số quan hệ.
Chương II: Phương pháp tách – gộp hàng, cột trong bảng vấn tin.
Với những nội dung chính như: Phương pháp chuyển câu vấn tin đại số quan
hệ sang bảng và phương pháp tách gộp hàng, cột trong bảng vấn tin.
Chương III: Ứng dụng giải một số bài toán thực tế. Dựa vào những
cơ sở lý thuyết đã nghiên cứu, một số bài toán đã được ứng dụng giải quyết
như: Cách tính tải trên hàng và các phân hoạch của bảng vấn tin, phương pháp
tìm ơ có chi phí truyền thơng lớn và thuật tốn tạo ra bảng vấn tin tiền xử lý.

Số hóa bởi Trung tâm Học liệu – Đại học Thái Nguyên





11

CHƯƠNG I:
TỔNG QUAN VỀ CƠ SỞ DỮ LIỆU QUAN HỆ
1.1.Khái quát về cơ sở dữ liệu
Ðịnh nghĩa Dữ liệu: Dữ liệu là các sự kiện, văn bản, đồ họa, hình ảnh,
âm thanh và các đoạn phim video có ý nghĩa trong môi trường người dùng.
Ðịnh nghĩa thông tin: Thông tin là dữ liệu được xử lý theo các cách để
làm tăng hiểu biết của người đang sử dụng dữ liệu này.
Thông thường đối với việc thiết kế xây dựng một hệ thống tin quản lý,
chúng ta cần xử lý một hệ thống các file dữ liệu. Mỗi file này có cấu trúc bản
ghi khác nhau nhưng về nội dung có quan hệ với nhau tạo thành một cơ sở dữ
liệu (Database _ viết tắt CSDL).
Cơ Sở Dữ Liệu là tập hợp thơng tin (dữ liệu) có tổ chức nhằm thỏa mãn
một hay nhiều mục đích quản lý thơng tin của con người. Hệ các chương trình
nhằm quản lý khai thác dữ liệu này là Hệ quản trị Cơ Sở Dữ Liệu (viết tắt
HQTCSDL, Database management system). (ví dụ Access, SQL server,
Oracle...) Hệ thống thông tin gồm bộ phận xử lý thơng tin, kênh thơng tin vào
ra.(Xem hình 1.1)

Hình 1.1. Mơ hình xử lý thơng tin
Ưu điểm của cơ sở dữ liệu: Giảm sự trùng lắp thông tin xuống mức thấp
nhất và do đó bảo đảm được tính nhất qn và tồn vẹn dữ liệu. Đảm bảo dữ
liệu có thể truy xuất theo nhiều cách khác nhau. Khả năng chia sẻ thơng tin
cho nhiều người sử dụng.

Số hóa bởi Trung tâm Học liệu – Đại học Thái Nguyên





12

1.1.1.Những vấn đề mà CSDL cần phải giải quyết
Tính chủ quyền của dữ liệu: Tính chủ quyền của dữ liệu được thể hiện ở
phương diện an toàn dữ liệu, khả năng biểu diễn các mối liên hệ ngữ nghĩa
của dữ liệu và tính chính xác của dữ liệu. Điều này có nghĩa là người khai
thác CSDL phải có nhiệm vụ cập nhật các thơng tin mới nhất của CSDL.
Tính bảo mật và quyền khai thác thông tin của người sử dụng: Do có
nhiều người được phép khai thác dữ liệu một cách đồng thời, nên cần thiết phải
có một cơ chế bảo mật và phân quyền hạn khai thác CSDL. Các hệ điều hành
nhiều người sử dụng hay hệ điều hành mạng cục bộ đều có cung cấp cơ chế này.
Tranh chấp dữ liệu: Nhiều người được phép truy nhập cùng một lúc vào
tài nguyên dữ liệu của CSDL với những mục đích khác nhau, do đó cần thiết
phải có một cơ chế ưu tiên khi truy nhập dữ liệu. Cơ chế ưu tiên có thể được
thực hiện bằng việc cấp quyền ưu tiên cho từng người khai thác.
Đảm bảo an tồn dữ liệu khi có sự cố: Việc quản lý dữ liệu tập trung có
thể làm tăng khả năng mất mát hoặc sai lệch thơng tin khi có sự cố như mất
điện đột xuất, hay một phần đĩa lưu trữ CSDL bị hư hỏng,… một số hệ điều
hành mạng có cung cấp dịch vụ sao lưu ảnh đĩa cứng, tự động kiểm tra và
khắc phục lỗi khi có sự cố. Tuy nhiên, bên cạnh dịch vụ của hệ điều hành, để
đảm bảo CSDL luôn ổn định, một CSDL nhất thiết phải có một cơ chế khơi
phục dữ liệu khi có các sự cố bất ngờ xảy ra.
Các đối tượng sử dụng CSDL: Những người sử dụng CSDL không
chuyên về lĩnh vực tin học và CSDL. Các chuyên viên CSDL biết khai thác
CSDL, những người này có thể xây dựng các ứng dụng khác nhau, phục vụ
cho các mục đích khác nhau trên CSDL.
Những người quản trị CSDL, đó là những người hiểu biết về tin học, về

các hệ quản trị CSDL và hệ thống máy tính. Họ là người tổ chức CSDL, do
đó họ phải nắm rõ các vấn đề kỹ thuật về CSDL để có thể phục hồi CSDL khi

Số hóa bởi Trung tâm Học liệu – Đại học Thái Nguyên




13

có sự cố. Họ là những người cấp quyền hạn khai thác CSDL, do vậy họ có thể
giải quyết được các vấn đề tranh chấp dữ liệu nếu có.
1.1.2. Ðịnh nghĩa Hệ thống cơ sở dữ liệu (Database Systems)
Hệ thống cơ sở dữ liệu là hệ thống thông tin, cho phép người ta dùng
chung các dữ liệu có trong hệ thống.
Để giải quyết tốt những vấn đề mà cách tổ chức CSDL đặt ra như đã nói
ở trên, cần thiết phải có những phần mềm chuyên dùng để khai thác chúng.
Những phần mềm này được gọi là các hệ quản trị CSDL. Các hệ quản trị
CSDL có nhiệm vụ hỗ trợ cho các nhà phân tích thiết kế CSDL cũng như
những người khai thác CSDL. Hiện nay trên thị trường phần mềm đã có
những hệ quản trị CSDL hỗ trợ được nhiều tiện ích như: MS Access, Visual
Foxpro, SQL Server, Oracle,…(Xem hình 1.2)
user
1

CSDL
Ngơn

Hệ


ngữ
user

hỏi

cơ
CSDL

cơ sở
user

dữ

1

liệu

sở
dữ

CSDL

liệu

user
1

Hình 1.2 Mơ hình hệ thống cơ sở dữ liệu
Mỗi hệ quản trị CSDL đều được cài đặt dựa trên một mơ hình dữ liệu cụ
thể. Dù là dựa trên mơ hình dữ liệu nào, một hệ quản trị CSDL cũng phải hội

đủ các yếu tố sau:

Số hóa bởi Trung tâm Học liệu – Đại học Thái Nguyên




14

Ngôn ngữ mô tả dữ liệu: Cho phép khai báo cấu trúc của CSDL, khai báo
các mối liên hệ của dữ liệu và các quy tắc quản lý áp đặt lên các dữ liệu đó.
Ngơn ngữ thao tác dữ liệu: Cho phép người sử dụng có thể cập nhật dữ
liệu (thêm/sửa/xố).
Ngơn ngữ truy vấn dữ liệu: Cho phép người khai thác sử dụng để truy
vấn các thông tin cần thiết trong CSDL.
Ngôn ngữ quản lý dữ liệu: Cho phép những người quản trị hệ thống thay
đổi cấu trúc của các bảng dữ liệu, khai báo bảo mật thông tin và cấp quyền
hạn khai thác CSDL cho người sử dụng.,…
Từ điển dữ liệu: Dùng để mô tả các ánh xạ liên kết, ghi nhận các thành
phần cấu trúc của CSDL, các chương trình ứng dụng, mật mã, quyền hạn sử
dụng,…
Cơ chế giải quyết vấn đề tranh chấp dữ liệu: Mỗi hệ quản trị CSDL
cũng có thể cài đặt một cơ chế riêng để giải quyết các vấn đề này. Một số cơ
chế thường dùng sau đây:
- Cấp quyền ưu tiên cho từng người sử dụng;
- Đánh dấu yêu cầu truy xuất dữ liệu, phân chia thời gian, người nào có
yêu cầu trước thì có quyền truy xuất dữ liệu trước,…
Hệ quản trị CSDL cũng phải có cơ chế sao lưu (Backup) và phục hồi
(Recovery) dữ liệu khi có sự cố xảy ra. Điều này có thể thực hiện sau một thời
gian nhất định hệ quản trị CSDL sẽ tự động tạo ra một bản sao CSDL, cách

này hơi tốn kém, nhất là đối với CSDL lớn.
Hệ quản trị CSDL phải cung cấp một giao diện thân thiện, dễ sử dụng.
1.1.3.Cơ sở dữ liệu quan hệ và lược đồ cơ sở dữ liệu quan hệ
Một cơ sở dữ liệu quan hệ thường gồm nhiều quan hệ với các bộ giá trị
trong các quan hệ được liên kết với nhau theo nhiều cách. Một lược đồ cơ sở

Số hóa bởi Trung tâm Học liệu – Đại học Thái Nguyên




15

dữ liệu quan hệ S là một tập hợp các lược đồ quan hệ S = {R 1, R2,…, Rn} và
một tập các ràng buộc toàn vẹn.
Một trạng thái cơ sở dữ liệu quan hệ (hoặc một cơ sở dữ liệu quan hệ) R
của S là một tập hợp các trạng thái quan hệ:
R = {r1, r2, …, rn}
sao cho mỗi ri là một trạng thái của Ri và sao cho các trạng thái quan hệ ri
thoả mãn các ràng buộc toàn vẹn chỉ ra trong tập các ràng buộc tồn vẹn.
Ví dụ: Trình bày một lược đồ cơ sở dữ liệu CONGTY như sau:
NHANVIEN(MaNV, TenNV, NgaySinh, DiaChi, GioiTinh, Luong, MaDV)
DONVI(MaDV, TenDV, Ngay_Bat_Dau)
DONVI_DIADIEM(MaDV, Dia_Diem_DV)
DUAN(MaDA, TenDA, Dia_Diem_DA, MaDV)
NHANVIEN_DUAN(MaNV, MaDA, ThoiGian_LV)
Và cơ sở dữ liệu CONGTY bao gồm các bảng:
MaNV

TenNV


NgaySinh

DiaChi

GioiTinh

Luong MaDV

NV0001 Lê Duy

19/09/1980 Bắc Kạn Nam

5.000 DV02

NV0002 Vũ Thị Bé

20/07/1983 Hà Nội

4.500 DV01

NV0003 Lê Ba

23/05/1985 Phú Thọ Nam

4.000 DV01

NV0004 Phạm Hà

09/09/1969 Sơn La


Nam

6.000 DV03

NV005

Trần Bá Tí 09/05/1960 Hà Nội

Nam

7.000 DV02

NV006

Vũ Hùng

Nam

4.500 DV02

12/12/1987 Hà Nội

Nữ

Bảng 1.1. Bảng quan hệ NHANVIEN

Số hóa bởi Trung tâm Học liệu – Đại học Thái Nguyên





16

MaDV

TenDV

Ngay_Bat_Dau

DV01

Phịng Kế hoạch

15/06/2000

DV02

Phịng Kế tốn

10/10/2003

DV03

Phịng phát triển CN

20/07/2002

Bảng 1.2. Bảng quan hệ DONVI
MaDV Dia_Diem_DV

DV01

Thái Nguyên

DV02

Bắc Kạn

DV03

Bắc Kạn

Bảng 1.3. Bảng quan hệ DONVI_DIADIEM
MaDA

TenDA

Dia_Diem_DA

MaDV

DA001

Đào tạo

Thái Nguyên

DV02

DA002


Quản lý

Bắc Kạn

DV03

DA003

Xây dựng HT

Bắc Kạn

DV03

DA004

Lập trình PHP

Thái Nguyên

DV02

DA005

Thiết kế Web

Hà Nội

DV01


DA006

Lập trình Java

Hà Nội

DV01

DA007

Lập trình ASP

Thái Nguyên

DV02

DA 008

Lập trình .NET

Thái Nguyên

DV02

Bảng 1.4. Bảng quan hệ DUAN

Số hóa bởi Trung tâm Học liệu – Đại học Thái Nguyên





17

MaNV

MaDA ThoiGian_LV

NV0001 DA001

100

NV0002 DA002

80

NV0003 DA003

110

NV0004 DA008

200

NV005

DA007

90


NV006

DA005

150

NV007

DA006

230

Bảng 1.5. Bảng quan hệ NHANVIEN_DUAN
Trong một lược đồ cơ sở dữ liệu quan hệ, các thuộc tính biểu diễn cùng
một khái niệm thế giới thực có thể (hoặc khơng) có cùng tên như nhau trong
các quan hệ khác nhau. Ngược lại, các thuộc tính biểu diễn các khái niệm
khác nhau có thể có tên như nhau trong các quan hệ khác nhau.
1.2. Các loại câu vấn tin SQL.
Câu lệnh tạo cơ sở dữ liệu
Cú pháp của câu lệnh CREATE DATABASE
Create Database Ten_CSDL
Sau câu lệnh này, một CSDL có tên là Ten_CSDL được tạo ra.
Câu lệnh tạo bảng dữ liệu
Câu lệnh tạo quan hệ có cú pháp như sau
CREATE TABLE Ten_Quanhe
( ten_cot ten_thuoc_tinh_cot cac_rang_buoc [,...] )
Ràng buộc PRIMARY KEY được sử dụng để định nghĩa khố chính của bảng.
FOREIGN KEY là khóa ngoại, nó là khóa chính của bảng được quan hệ.
FOREIGN KEY có thể tham chiếu vào PRIMARY KEY hay cột có ràng buộc
duy nhất.


Số hóa bởi Trung tâm Học liệu – Đại học Thái Nguyên




18

Sửa bảng (ALTER TABLE)
Cú pháp của câu lệnh ALTER TABLE như sau:
ALTER TABLE Ten_Bang
ADD đinh_nghia_cot | ALTER COLUMN ten_cot kieu_du_lieu [NULL
|NOT NULL] DROP COLUMN ten_cot | ADD CONSTRAINT ten_rang_buoc
đinh_nghia_rang_buoc DROP CONSTRAINT ten_rang_buoc
Xóa bảng (DROP TABLE)
Khi một bảng khơng cịn cần thiết, ta có thể xố nó ra khỏi cơ sở dữ liệu
bằng câu lệnh DROP TABLE. Câu lệnh này cũng đồng thời xoá tất cả những
ràng buộc, chỉ mục, trigger liên quan đến bảng đó. Câu lệnh có cú pháp như sau:
DROP TABLE Ten_Bang
Sau câu lệnh này, bảng có tên là Ten_Bang sẽ bị xóa khỏi CSDL.
Thêm bản ghi mới (INSERT)
Để bổ sung một dòng dữ liệu mới vào bảng, ta sử dụng câu lệnh
INSERT với cú pháp như sau:
INSERT TABLE Ten_Bang[(danh_sach_cot)]VALUES (danh_sach_gia_tri)
Thêm một tập các dòng dữ liệu vào bảng
Cú pháp câu lệnh INSERT có dạng như sau:
INSERT INTO Ten_Bang (danh_sach_cot)] câu_lệnh_SELECT
Cập nhật bản ghi (UPDATE)
Câu lệnh UPDATE trong SQL được sử dụng để cập nhật dữ liệu trong
các bảng. Câu lệnh này có cú pháp như sau:

UPDATE Ten_Bang
Set ten_cot = bieu_thuc
[, ..., ten_cot_k = bieu_thuc_k]
[From danh_sach_bang]

Số hóa bởi Trung tâm Học liệu – Đại học Thái Nguyên




19

[Where dieu_kien]
Xoá bản ghi (DELETE)
Để xoá dữ liệu trong một bảng, ta sử dụng câu lệnh DELETE. Cú pháp
của câu lệnh này như sau:
DELETE FROM Ten_Bang
[FROM danh_sach_bang]
[WHERE dieu_kien]
Sau lệnh này, dữ liệu sẽ bị xóa trong bảng Ten_Bang theo danh sách và
điều kiện xóa trong mệnh đề FROM và WHERE
Truy vấn cơ sở dữ liệu (SELECT)
Cú pháp chung của câu lệnh SELECT có dạng:
SELECT [ALL | DISTINCT][TOP n] danh_sach_chon
[INTO ten_bang_moi]
FROM danh_sach_bang/khung_nhin
[WHERE dieu_kien]
[GROUP BY danh_sach_cot]
[HAVING dieu_kien]
[ORDER BY cot_sap_xep]

[COMPUTE danh_sach_ham_gop [BY danh_sach_cot]]
Câu lệnh SELECT được sử dụng để tác động lên các bảng dữ liệu và kết quả
của câu lệnh cũng được hiển thị dưới dạng bảng, tức là một tập hợp các dòng và các
cột (ngoại trừ trường hợp sử dụng câu lệnh SELECT với mệnh đề COMPUTE).
1.3. Phương pháp chuyển câu vấn tin SQL sang câu vấn tin đại số quan hệ AQL.
Từ câu vấn tin SQL, chúng ta chuyển sang câu vấn tin đại số quan hệ
bằng cách sử dụng các phép toán đại số quan hệ AQL như: phép chiếu, phép
chọn và phép kết nối.

Số hóa bởi Trung tâm Học liệu – Đại học Thái Nguyên




20

Nhiệm vụ chính của xử lý vấn tin là biến đổi câu vấn tin cấp cao (ở dạng
phép tính quan hệ) thành câu vấn tin cấp thấp hơn (dạng đại số quan hệ). Câu
vấn tin phải đạt được cả tính đúng lẫn tính hiệu quả.
Một biến đổi được xem là đúng đắn, nếu câu vấn tin cấp thấp có cùng
ngữ nghĩa với câu vấn tin gốc – tức là cả hai cùng cho ra một kết quả. Có
nhiều cách để biến đổi tương đương một câu vấn tin dạng phép tính quan hệ
thành đại số quan hệ. Do có nhiều cách biến đổi như vậy, nên có nhiều chiến
lược thực thi câu vấn tin cùng sử dụng tài nguyên. Cần phải chọn một chiến
lược hạ thấp nhất việc sử dụng tài nguyên.
Ví dụ: Cho một quan hệ CONGTY bao gồm
NhanVien(MaNV, TenNV, Ghi_Chu)
DuAn(MaDA,TenDA, Ngan_Sach, Vi_Tri)
NhanVien_DuAn(MaNV, MaDA , Chuc_Vu , Thoi_Gian).
Câu vấn tin “ Cho biết tên các nhân viên đang là người quản lý dự án”

Câu truy vấn SQL:
SELECT TenNV
FROM

NhanVien, NhanVien_DuAn

WHERE NhanVien.MaNV = NhanVien_DuAn.MaNV
AND NhanVien_DuAn.Chuc_Vu = “Quản lý dự án”
Câu truy vấn AQL tương ứng với SQL trên là:
πTenNV(σChuc_Vu=”Quản

lý dự án” ∧ NhanVien.MaNV=NhanVien_DuAn.MaNV

(NhanVien ×

NhanVien_DuAn)) hoặc
πTenNV(NhanVien ⋈MaNV(σChuc_Vu=”Quản lý dự án”(NhanVien_DuAn)))
1.3.1. Ngơn ngữ truy vấn đại số quan hệ (AQL)
Gọi r là quan hệ trên tập thuộc tính R={ A1,….,An}. Ta ln giả thiết
rằng quan hệ r là tập hữu hạn các bộ. Đối với các phép hợp (ký hiệu ) phép
giao (ký hiệu ), phép trừ (ký hiệu -) hai quan hệ tham gia phải khả hợp.

Số hóa bởi Trung tâm Học liệu – Đại học Thái Nguyên




21

AQL (Algebraic Query Language) là ngôn ngữ truy vấn đại số quan

hệ. Để truy vấn dữ liệu, thay vì sử dụng câu truy vấn SQL thông thường,
câu truy vấn AQL sử dụng các phép toán đại số quan hệ để truy vấn dữ
liệu thơng qua các phép tốn trên các mảnh con như: Phép chọn, phép
chiếu, phép kết nối trên cây toán tử và các phép hợp, phép giao, phép trừ,
phép Tích Đềcác,… trên bảng Ip (Isomorphous) truy vấn. Cụ thể chúng ta
tham khảo một số phép toán đại số quan hệ như dưới đây:
Phép hợp: Ký hiệu 
Hợp của hai quan hệ r và s ký hiệu là r  s là tập các bộ hợp thuộc r
hoặc thuộc s hoặc thuộc r lẫn thuộc s:
r  s = { t: t  r hoặc t  s hoặc t r và t  s }
Phép giao: Ký hiệu 
Giao của hai quan hệ r và s ký hiệu là r  s là tập các bộ phải vừa thuộc r
phải vừa thuộc s:
r  s = {t: t  r v à t  s }
Phép trừ: Ký hiệu Hiệu của hai quan hệ r và s ký hiệu là r - s là tập các bộ thuộc r nhưng
không thuộc s :
r-s = { t : t  r và t  s }
Phép chiếu (Projection)
Phép chiếu trên một quan hệ thực chất là giữ lại một số thuộc tính, cịn
các thuộc tính khác loại bỏ đi.
Giả sử r là quan hệ n ngôi trên tập thuộc tính R = {Al,...,An} và giả sử t
là một bộ của r, AR. Ký hiệu t[A] là giá trị của bộ t tại thuộc tính A. Như
vậy nếu X = {Bl,...,Bm} thì t[X]=(t[Bl],t[B2],;..,t[Bm]).
Gọi X là một tập con của tập thuộc tính R = {Al,...,An}. Phép chiếu π

Số hóa bởi Trung tâm Học liệu – Đại học Thái Nguyên





22

trên tập X của quan hệ r được định nghĩa như sau:
πx(r)={t[x] | t  r}
Phép chọn (Selection)
Phép chọn dùng để tạo một tập con các bộ trong quan hệ r thoả mãn biểu
thức F nào đó. Các phép tốn trong biểu thức F là <, =, >, <=, >= và ≠ cùng
với các phép toán logic là  (và),  (hoặc), ¬ (phủ định) định nghĩa phép chọn
σ như sau:
σ F(r) = {t  r | F(t) = .T.} (trong đó .T. = TRUE (đúng))
1.3.2. Các phép biến đổi tương đương trong đại số quan hệ
Xét r,s và T là những quan hệ, E là mệnh đề logic, với quan hệ r được
định nghĩa trên các thuộc tính {A1 , A2,…, An} và quan hệ s được định nghĩa
trên các thuộc tính {B1 ,B2 ,…, Bn } và X là tập thuộc tính.
- Tính giao hốn của phép tốn hai ngơi
Tích Đềcác của hai quan hệ r và s có tính giao hốn: r × s = s × r
Nối của hai quan hệ có tính giao hốn: r ⋈ s = s ⋈ r
Quy tắc này áp dụng được cho phép hợp nhưng không áp dụng cho phép
tập hợp hay nối nửa.
- Tính kết hợp của các phép tốn hai ngơi
Tích Đềcác và nối là phép tốn có tính kết hợp
(r × s) × T ⟺ r × (s × T)
(r ⋈ s) ⋈ T ⟺ r ⋈ (s ⋈ T)
- Tính lũy đẳng của các phép tốn đơn ngôi
Nhiều phép chiếu liên tiếp trên cùng một quan hệ có thể được nhóm lại,
ngược lại một phép chiếu trên nhiều thuộc tính có thể được tách ra thành
nhiều phép chiếu liên tiếp nhau. Nếu r được định nghĩa trên tập thuộc tính A
và A’ ⊆ A, A” ⊆ A’ thì: (r.(A’)).A” =r.A”

Số hóa bởi Trung tâm Học liệu – Đại học Thái Nguyên





23

Nhiều phép chọn liên tiếp theo thứ tự p1, p2,…. pk trên cùng một quan hệ
r, trong đó pi là một vị từ được áp dụng cho thuộc tính Ai có thể được nhóm
lại như sau: r.p1A1(r.p2A2) ⟺ r.p1A1∧p2A2
Ngược lại, một phép chọn qua một hội các vị từ có thể được tách ra
thành nhiều phép chọn liên tiếp nhau.
- Giao hoán chọn với chiếu
Phép chọn và phép chiếu trên cùng một quan hệ có thể được giao hốn
như sau: Chiếu xong chọn bằng chọn xong chiếu (r.X)(E) = (r(E).X) với E là
mệnh đề logic có các thuộc tính ra khỏi tập thuộc tính X thì phép chọn đầu ở
vế trái của hệ thức khơng có tác dụng.
- Giao hốn phép chọn với phép tốn hai ngơi
Phép chọn và Tích Đềcác có thể giao hốn bằng các quy tắc sau:
(r × s)(E) ⟺ r(E) × s(E) nếu E thỏa mãn trong r và s
Chọn và nối cũng có thể giao hốn
(r ⋈ s)(E) ⟺ r(E) ⋈ s(E)
Chọn và hợp có thể giao hốn nếu r và T có lược đồ giống nhau
(r + T)(E) ⟺ r(E) + T(E)
Chọn và hiệu cũng có phép tốn tương tự
(r - T)(E) ⟺ r(E) – T(E)
- Giao hoán phép chiếu với phép toán hai ngơi
Phép chiếu và Tích Đềcác có thể được giao hốn nếu C= A’ ∪ B’ trong đó
A’ ⊆ A, B’ ⊆B và A,B là các tập thuộc tính tương ứng với các quan hệ r, s ta
có: (r × s).C ⟺ r.C × s.C
Chiếu và nối có thể giao hốn

(r ⋈ s).C ⟺ r.C ⋈ s.C
Chiếu và hợp có thể giao hốn

Số hóa bởi Trung tâm Học liệu – Đại học Thái Nguyên




24

(r + s).C = r.C + s.C
Chiếu và hiệu cũng có thể giao hốn tương tự
(r - s). C = r.C – s.C
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 tốn một ngơi
được thực hiện trước các phép tốn hai ngơi, do các phép tố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 khác:
Tách điều kiện trong phép chọn
σc1 ∧ c2 (E) = σc1(σc2 (E))
Tính chất giao hốn của phép chọn
σc1(σc2 (E)) = σc2(σc1 (E))
Dãy các phép chiếu liên tiếp
πL1 (π L2(…(π Ln(E))…)) π L1 (E), L1 ⊆ L2 …⊆ Ln
Phép chọn - Phép tích đề các và phép nối
σθ (E1 × E2) = E1 ⋈θ E2
σθ1 (E1 ⋈θ2 E2) = E1 ⋈θ1 ∧ θ2 E2
Tính chất giao hốn của phép kết nối
E1 ⋈θ E2 = E2 ⋈θ E1
Tính chất giao hốn của phép kết nối tự nhiên

E1 * E2 = E2 * E1
Tính chất kết hợp của phép kết nối tự nhiên
(E1 * E2) * E3 = E1 * (E2 * E3)
Tính chất kết hợp của phép nối
(E1 ⋈θ1 E2) ⋈θ2 ∧ θ3 E3 = E1 ⋈θ1∧ θ3 ( E2 ⋈θ2 E3), nếu các thuộc tính
trong

2

chỉ thuộc E2 và E3.

Số hóa bởi Trung tâm Học liệu – Đại học Thái Nguyên