ĐẠI HỌC QUỐC GIA HÀ NỘI
TRƯỜNG ĐẠI HỌC CÔNG NGHỆ
Đào Thị Thu Vân
XỬ LÝ TRUY VẤN VÀ QUẢN LÝ GIAO TÁC
LUẬN VĂN THẠC SĨ
Hà Nội – 2005
1
LỜI CẢM ƠN
Em xin bày tỏ lòng biết ơn sâu sắc tới Thầy hƣớng dẫn
TS. Nguyễn Tuệ đã có những chỉ dẫn quý báu trong quá trình
em làm luận văn. Em xin chân thành cảm ơn các Thầy Cô thuộc
Trƣờng Đại học công nghệ đã tận tình giảng dạy, truyền đạt
kiến thức trong suốt thời gian học tập nghiên cứu tại trƣờng.
Cuối cùng xin bày tỏ lòng cảm ơn tới những ngƣời thân trong
gia đình, bạn bè đã động viên và giúp đỡ để tôi hoàn thành bản
luận văn này.
2
MỤC LỤC
Më ®Çu ............................................. 6
xö lý vµ tèi -u truy vÊn .......... 7
ch-¬ng 1
1.1
ChuyÓn c¸c truy vÊn SQL thµnh ®¹i sè quan
hÖ.......................................... 8
1.2
C¸c thuËt to¸n c¬ b¶n thùc hiÖn phÐp to¸n
truy vÊn......... Error! Bookmark not defined.
1.2.1
S¾p xÕp ngoµi ...... Error! Bookmark not
defined.
1.2.2
Thùc thi phÐp chän (SELECT) Error! Bookmark
not defined.
1.2.3
Thùc thi phÐp nèi (JOIN) ... Error! Bookmark
not defined.
1.2.4 ....... Thùc thi phÐp chiÕu vµ c¸c phÐp to¸n tËp
hîp
Error! Bookmark not defined.
1.2.5 ................................... Thùc thi c¸c phÐp to¸n kÕt hîp
Error! Bookmark not defined.
1.2.6 .................. Thùc thi phÐp nèi ngoµi - Outer Join
Error! Bookmark not defined.
1.2.7 .......... C¸c phÐp to¸n kÕt hîp sö dông ®-êng èng
Error! Bookmark not defined.
1.3
Sö dông c¸c luËt dù ®o¸n trong tèi -u truy
vÊn.............. Error! Bookmark not defined.
1.3.1 ............ C¸c ký hiÖu víi c©y truy vÊn vµ ®å thÞ
truy vÊn ............ Error! Bookmark not defined.
1.3.2 .......... Tèi -u kinh nghiÖm cña c¸c c©y truy vÊn
Error! Bookmark not defined.
1.3.3. .... ChuyÓn c©y truy vÊn thµnh ph-¬ng ¸n thùc
thi truy vÊn ........ Error! Bookmark not defined.
3
1.4
Sö dông -íc l-îng chän läc vµ -íc l-îng chi
phÝ trong tèi -u truy vÊn. Error! Bookmark not
defined.
1.4.1
.......... C¸c thµnh phÇn chi phÝ cho viÖc thùc
thi truy vÊn ........ Error! Bookmark not defined.
1.4.2 ....... Th«ng tin danh môc sö dông trong c¸c hµm
gi¸
Error! Bookmark not defined.
1.4.3 . VÝ dô cña c¸c hµm gi¸ ®èi víi
phÐp SELECT
Error! Bookmark not defined.
1.4.4 .......... VÝ dô cña c¸c hµm gi¸ ®èi víi phÐp JOIN
Error! Bookmark not defined.
1.4.5 . C¸c truy vÊn cã quan hÖ vµ thø tù nèi phøc
t¹p
Error! Bookmark not defined.
1.4.6
VÝ dô minh ho¹ cho viÖc tèi -u truy
vÊn dùa trªn gi¸ .... Error! Bookmark not defined.
1.5
Tèi -u truy vÊn ng÷ nghÜa Error! Bookmark not
defined.
1.6
Tæng kÕt ........ Error! Bookmark not defined.
Ch-¬ng 2
xö lý giao t¸c ........ Error! Bookmark not
defined.
2.1 Giíi thiÖu vÒ xö lý giao t¸c ... Error! Bookmark
not defined.
2.1.1 HÖ thèng ®¬n ng-êi dïng - hÖ thèng ®a
ng-êi dïng .......... Error! Bookmark not defined.
2.1.2 C¸c giao t¸c, thao t¸c ®äc - ghi vµ c¸c
vïng ®Öm DBMS ....... Error! Bookmark not defined.
2.1.3 T¹i sao ®iÒu khiÓn ®ång thêi lµ cÇn thiÕt
Error! Bookmark not defined.
4
2.1.4 T¹i sao kh«i phôc lµ cÇn thiÕt ...... Error!
Bookmark not defined.
2.2 C¸c kh¸i niÖm hÖ thèng vµ giao t¸c ...... Error!
Bookmark not defined.
2.2.1 C¸c tr¹ng th¸i giao t¸c vµ c¸c phÐp to¸n
bæ xung ............. Error! Bookmark not defined.
2.2.2 File log hÖ thèng ...... Error! Bookmark not
defined.
2.2.3 §iÓm x¸c nhËn cña mét giao t¸c ...... Error!
Bookmark not defined.
2.3 C¸c ®Æc tÝnh mong muèn cña giao t¸c ..... Error!
Bookmark not defined.
2.4 LÞch biÓu vµ sù kh«i phôc .. Error! Bookmark not
defined.
2.4.1 LÞch biÓu cña c¸c giao t¸c . Error! Bookmark
not defined.
2.4.2 Miªu t¶ ®Æc tÝnh c¸c lÞch biÓu dùa trªn
viÖc kh«i phôc ...... Error! Bookmark not defined.
2.5 XÕp thø tù cña lÞch biÓu ... Error! Bookmark not
defined.
2.5.1 C¸c lÞch biÓu theo thø tù, kh«ng theo thø
tù vµ lÞch biÓu cã thø tù xung ®ét ........ Error!
Bookmark not defined.
2.5.2. KiÓm tra thø tù xung ®ét cña mét lÞch
biÓu
Error! Bookmark not defined.
2.5.3 Sö dông tÝnh thø tù .... Error! Bookmark not
defined.
2.5.4 T-¬ng ®-¬ng khung nh×n vµ trËt tù khung
nh×n
Error! Bookmark not defined.
2.5.5 C¸c kiÓu t-¬ng ®-¬ng kh¸c cña c¸c lÞch
biÓu
Error! Bookmark not defined.
5
2.6 Tæng kÕt .......... Error! Bookmark not defined.
KÕt luËn ................ Error! Bookmark not defined.
Tµi liÖu tham kh¶o ................................ 11
6
MỞ ĐẦU
Khi dữ liệu đƣợc lƣu trữ trên máy tính thì việc sử dụng nó nhƣ thế nào
để có hiệu quả là một thách thức đối với ngƣời sử dụng. Để khai thác một cơ
sở dữ liệu tốt cần phải có một hệ quản trị cơ sở dữ liệu tốt. Việc xử lý các truy
vấn, quản lý giao tác là hai chức năng quan trọng của một hệ quản trị cơ sở dữ
liệu. Tìm hiểu về lý thuyết và thực tiễn của hai chức năng này có ý nghĩa
trong việc xây dựng các hệ quản trị cơ sở dữ liệu. Thông qua việc nghiên cứu
một số tài liệu khoa học có liên quan, trong luận văn này chúng tôi đã đi sâu
tìm hiểu các vấn đề với đề tài “xử lý truy vấn và quản lý các giao tác”.
Luận văn bao gồm hai chƣơng:
Chƣơng 1: Xử lý và tối ƣu truy vấn
Một truy vấn trên cơ sở dữ liệu là một biểu thức đại số quan hệ, thực
hiện một loạt các thao tác trên cơ sở dữ liệu quan hệ để lấy ra các thông tin
cần thiết cho việc quản lý. Nghiên cứu về xử lý và tối ƣu truy vấn là nghiên
cứu các thuật toán thực hiện các phép toán đại số quan hệ cũng nhƣ tìm cách
thực hiện biểu thức đại số quan hệ theo một trật tự nào đó để có câu trả lời
nhanh nhất.
Chƣơng 2: Quản lý giao tác
Quản lý giao tác là rất cần thiết, đặc biệt khi các giao tác xẩy ra đồng
thời và có cạnh tranh nhau một số khoản mục dữ liệu trong cơ sở dữ liệu, tính
nhất quán có thể không còn đƣợc bảo toàn nữa. Do vậy hệ thống cần điều
khiển sự tƣơng tác giữa các giao tác đồng thời.
Do kinh nghiệm làm việc với cơ sở dữ liệu còn ít, chắc chắn trong luận
văn còn nhiều thiếu sót. Chúng tôi chân thành mong đƣợc các thầy, các cô, và
bạn bè đóng góp ý kiến.
7
CHƢƠNG 1
XỬ LÝ VÀ TỐI ƯU TRUY VẤN
Trong chƣơng này trình bầy các kỹ thuật mà hệ quản trị cơ sở dữ liệu
(DBMS) sử dụng để xử lý, tối ƣu hoá và thực thi các truy vấn bậc cao. Một
truy vấn đƣợc trình bầy trong một ngôn ngữ bậc cao, nhƣ SQL, đầu tiên phải
đƣợc kiểm tra, phân tích và xác nhận tính hợp lệ. Bộ quét sẽ xác định các dấu
hiệu ngôn ngữ, nhƣ các từ khóa SQL, tên các thuộc tính và tên các quan hệ
trong nội dung câu truy vấn, trong khi đó bộ phân tích sẽ kiểm tra cú pháp của
truy vấn để xác định xem nó có đƣợc trình bầy phù hợp với các luật cú pháp
của ngôn ngữ truy vấn hay không. Một truy vấn cũng phải đƣợc xác nhận tính
hợp lệ bằng cách kiểm tra tất cả các tên quan hệ và thuộc tính là hợp lệ, và các
tên có ý nghĩa trong lƣu đồ cơ sở dữ liệu cụ thể đƣợc truy vấn. Sau đó một
biểu diễn bên trong của truy vấn đƣợc tạo ra, thƣờng là nhƣ một cấu trúc dữ
liệu cây gọi là một cây truy vấn. Cũng có thể biểu diễn truy vấn bằng cách sử
dụng một cấu trúc dữ liệu đồ thị gọi là đồ thị truy vấn. Sau đó DBMS sẽ phải
đƣa ra một chiến lƣợc thực hiện để lấy ra kết quả của truy vấn từ các file cơ
sở dữ liệu. Một truy vấn thƣờng có nhiều chiến lƣợc thực hiện, và quá trình
chọn một chiến lƣợc phù hợp để xử lý một truy vấn gọi là tối ƣu truy vấn. [1,
3, 4, 5, 6, 7]
Hình 1.1 thể hiện các bƣớc khác nhau của việc xử lý một truy vấn bậc
cao. Bộ tối ƣu truy vấn có nhiệm vụ tạo ra một phƣơng án thực hiện và bộ tạo
mã tạo ra chƣơng trình để thực hiện phƣơng án đó. Bộ xử lý cơ sở dữ liệu thời
gian chạy có nhiệm vụ chạy chƣơng trình truy vấn trong kiểu thông dịch hoặc
biên dịch để tạo ra kết quả của truy vấn. Nếu có một lỗi chạy chƣơng trình
đƣợc tạo ra thì bộ xử lý cơ sở dữ liệu thời gian chạy sẽ sinh ra một thông báo
lỗi.
Thuật ngữ tối ƣu đƣợc sử dụng ở đây là không chính xác vì trong một
vài trƣờng hợp, phƣơng án thực hiện đƣợc lựa chọn không phải là chiến lƣợc
tốt nhất, nó chỉ là một chiến lƣợc hiệu quả và hợp lý cho việc thực hiện truy
vấn. Việc tìm ra một chiến lƣợc tốt nhất thƣờng phải mất nhiều thời gian,
ngoại trừ những truy vấn đơn giản, và có thể yêu cầu thông tin về việc các file
đƣợc cài đặt nhƣ thế nào và ngay cả nội dung của các file, những thông tin đó
8
có thể không có trong từ điển hệ quản trị cơ sở dữ liệu. Vì vậy, lập kế hoạch
của một chiến lƣợc thực hiện là chính xác hơn tối ƣu truy vấn.
Truy vấn viết trong ngôn ngữ bậc cao
Scanning, parsing,
validating
Dạng biểu diễn bên trong
Query Optimiser
Phƣơng án thực hiện
Query Code
Generator
Chƣơng trình thực hiện truy vấn
Runtime Database
Processor
Kết quả của truy vấn
Hình 1.1 Các bước điển hình khi xử lý một truy vấn bậc cao
1.1
Chuyển các truy vấn SQL thành đại số quan hệ
Một truy vấn SQL đầu tiên chuyển đổi thành một biểu thức đại số quan
hệ mở rộng tƣơng đƣơng, đƣợc biểu diễn nhƣ là cấu trúc dữ liệu cây truy vấn,
và sau đó đƣợc tối ƣu. Thông thƣờng các truy vấn SQL đƣợc phân tích thành
các khối truy vấn, tạo nên các đơn vị cơ sở mà có thể chuyển đổi thành những
phép toán đại số và đƣợc tối ƣu. Một khối truy vấn chứa một biểu thức
SELECT – FROM – WHERE đơn và có thể có các mệnh đề Group by và
9
Having nếu chúng là một phần của biểu thức. Vì vậy các truy vấn đƣợc lồng
bên trong một truy vấn đƣợc xác định nhƣ các khối truy vấn riêng rẽ. [6]
Xét các quan hệ sau: EMPLOYEE, DEPARTMENT, WORKS-ON và
PROJECT.
EMPLOYEE
FNAME LNAME SSN
ADDESS
BDATE
SEX SALAR
Y
DNO
DEPARTMENT
DNAME
DNUMBER
MGRSSN
MGRSTARTDATE
PROJECT
PNAME
PNUMBER
PLOCATION
DNUM
WORKS-ON
ESSN
PNO
HOURS
Bảng 1.1 Các quan hệ
Trong đó:
Quan hệ EMPLOYEE chứa thuộc tính của các nhân viên:
FNAME: tên của các nhân viên
LNAME: họ và tên đệm của nhân viên
SSN: mã nhân viên
BDATE: ngày sinh của mỗi nhân viên
ADDESS: địa chỉ của nhân viên
SEX: giới tính của nhân viên
SALARY: mức lƣơng của từng nhân viên
DNO: mã số phòng ban mà nhân viên đó làm việc
Quan hệ DEPARTMENT chứa thông tin về các phòng ban:
DNAME: tên của mỗi phòng ban
DNUMBER: mã số của mỗi phòng ban
10
MGRSSN: mã số của ngƣời quản lý từng phòng
MGRSTARTDATE: ngày bắt đầu làm quản lý của ngƣời
quản lý phòng ban
Quan hệ PROJECT chứa thông tin về các dự án:
PNAME: tên của dự án
PNUMBER: mã số dự án
PLOCATION: nơi thực hiện dự án
DNUM: mã số của phòng thực hiện dự án
Quan hệ WORKS-ON chứa thông tin về thời gian làm việc của mỗi
nhân viên:
ESSN: mã số của nhân viên
PNO: mã số dự án mà nhân viên đó tham gia
HOURS: số giờ mà nhân viên đó thực hiện
Xét truy vấn SQL sau trên quan hệ EMPLOYEE trong bảng 1.1
SELECT
LNAME, FNAME
FROM
EMPLOYEE
WHERE
SALARY > (SELECT
MAX(SALARY)
FROM
EMPLOYEE
WHERE
DNO=5);
Truy vấn này chứa một truy vấn con lồng bên trong và vì vậy có thể
đƣợc tách thành 2 khối:
Khối trong là:
SELECT
MAX (SALARY)
FROM
EMPLOYEE
WHERE
DNO=5
SELECT
LNAME, FNAME
FROM
EMPLOYEE
WHERE
SALARY > c
Và khối ngoài là:
Với c biểu diễn kết quả do khối trong trả lại. Khối trong có thể đƣợc
chuyển thành biểu thức quan hệ mở rộng nhƣ sau:
11
TÀI LIỆU THAM KHẢO
Tài liệu tiếng Việt:
[1]. Nguyễn Kim Anh, Nguyên lý của các hệ cơ sở dữ liệu, NXB ĐH
Quốc Gia Hà Nội, 2004
[2]. Trần Tiến Dũng, Giáo trình lý thuyết và thực hành ORACLE, NXB
Giáo Dục, 2000
[3]. Phạm Hữu Khang, SQL Server 2000, NXB Giáo Dục, 2002
[4]. Trần Đức Quang, Hồ Thuần, Nguyên lý các hệ cơ sở dữ liệu và cơ sở
tri thức, NXB Thống Kê, 1998
[5]. Lê Tiến Vƣơng, Nhập môn cơ sở dữ liệu quan hệ, NXB Khoa Học
và Kỹ Thuật, 1996
Tài liệu tiếng Anh:
[6].
Elmasri, Navathe, Fundamentals of Database systems
[7].
Jarke, M and J.Koch (1984). Query optimization in database
systems, Computing surveys 16:2,pp.1 11-152.
[8]. Keller, A. (1985), Algorithms for transtating view updates into
database for view involving selections, projections and joins, Pro.,
Fourth ACM Symp. on Principles of Database Systems, pp. 154163.
[9].
Swami, A. and A. Gupta (1988), Optimizing large join queries,
ACM SIGMOD Intl. Conf. on Management of Data, pp. 8-17.
12
- Xem thêm -