Giáo trình Bài tập Cơ sở dữ liệu
Nguyễn Xuân Huy - Lê Hoài Bắc
Bài tập
Cơ sở dữ liệu
Xuất bản lần thứ bai, có sửa chữa
Hà Nội, 2006
1
1
2
Nguyễn Xuân Huy, Lê Hoài Bắc
Bài tập Cơ sở Dữ liệu
Mục lục
2
3
4
Nguyễn Xuân Huy, Lê Hoài Bắc
Bài tập Cơ sở Dữ liệu
3
5
6
Nguyễn Xuân Huy, Lê Hoài Bắc
Bài tập Cơ sở Dữ liệu
tập, cuối cùng là các bài giải. Dấu * được dùng để ghi chú các bài tập
ở mức nâng cao.
Phần cuối sách chúng tôi tuyển chọn và giới thiệu một số đề thi tuyển
cao học và nghiên cứu sinh để bạn đọc làm quen với các nội dung
tổng hợp.
Lời nói đầu
Mục tiêu cuối cùng của việc ra bài tập là giúp cho người học hiểu sâu
và kỹ hơn về các khái niệm đã học. Để đạt được điều này mong bạn
đọc đừng bỏ qua bài tập nào. Với các bài dễ, bạn có thể giải trong
một vài phút. Với các bài khó, trong lần luyện tập thứ nhất bạn có thể
bỏ qua. Sau một vài lần thử sức, tin rằng bạn sẽ hoàn toàn làm chủ
được các khái niệm liên quan đến cơ sở dữ liệu.
Khác với toán học, trong tủ sách tin học nước nhà, ta chỉ thấy một số
sách bài tập lập trình. Đó chắc chắn là một thiệt thòi cho sinh viên và
các bạn tự học.
Chúng tôi cho rằng các tài liệu sau đây sẽ giúp ích bạn đọc tra cứu
các nguồn tri thức cơ sở:
Cuốn Bài tập cơ sở dữ liệu này là một thử nghiệm nhằm trợ giúp các
bạn trẻ một phương thức tự kiểm tra và đánh giá tri thức ban đầu,
mức nhập môn, về một lĩnh vực chiếm vị trí đáng nói trong quá trình
phát triển của công nghệ thông tin.
1. Date C. J., Nhập môn các hệ cơ sở dữ liệu, Những người
dịch: Hồ Thuần, Nguyễn Quang Vinh, Nguyễn Xuân Huy, NXB Thống
Kê, Hà Nội, Tập I (1985), Tập II (1986).
2. Nguyễn Xuân Huy, Thuật toán, NXB Thống Kê, Hà Nội, 1987.
Những năm gần đây, trong các kỳ thi tốt nghiệp đại học, thi chuyển
đổi, thi tuyển cao học và nghiên cứu sinh đều có mảng về cơ sở dữ
liệu. Đó là điều dễ hiểu, vì cơ sở dữ liệu là phần không thể thiếu trong
các hệ thống tin học hoá.
3. Vũ Đức Thi, Cơ sở dữ liệu:Kiến thức và thực hành, NXB
Thống Kê, Hà Nội, 1997.
4. Lê Tiến Vương, Nhập môn cơ sở dữ liệu quan hệ, Tái bản lần
thứ 4, NXB Thống Kê, Hà Nội, 1999.
Trong phương án đầu tiên của cuốn sách chúng tôi chọn lọc và đề
xuất một số bài tập thuộc năm mảng tri thức sau đây: đại số quan hệ,
các phép toán trên bộ, ngôn ngữ hỏi SQL, phụ thuộc hàm và chuẩn
hoá. Mỗi mảng tri thức được trình bày thành ba phần: Phần thứ nhất
bao gồm một số điều tóm tắt về lý thuyết. Phần tiếp theo là các bài
5. Garcia-Molina H., Ullman J., Widom J., Database System: The
Complete Book, Prentice Hall, 2002.
6. Maier D., The Theory of Relational Database, Computer
Science Press, Rockville, Md, 1983.
4
7
8
Nguyễn Xuân Huy, Lê Hoài Bắc
Bài tập Cơ sở Dữ liệu
7. Ullman, J., Principles of Data-base and Knowledge-base
Systems, (Second Edition), Computer Science Press, Potomac, Md.,
1982, (Có bản dịch tiếng Việt của Trần Đức Quang.)
Chúng tôi chân thành cảm ơn những đóng góp vô giá của các đồng
nghiệp.
Chúng tôi mong rằng sẽ tiếp tục nhận được những ý kiến chỉ giáo của
bạn đọc gần xa về nội dung và cấu trúc của tập sách.
Người đầu tiên định hướng cho chúng tôi tìm hiểu về cơ sở dữ liệu và
luôn luôn khuyến khích chúng tôi học tập và trao đổi kiến thức là giáo
sư Hồ Thuần, Viện Công nghệ Thông tin.
Cát Bà, Mùa Hoa Phượng, 2003
Các tác giả
Nguyễn Xuân Huy - Lê Hoài Bắc
Cuốn sách này được khởi thảo và hoàn thành theo phương án
đầu tiên là nhờ nhiệt tình đóng góp về ý tưởng, nội dung và thẩm định
của các đồng nghiệp của chúng tôi. Giáo sư Lê Tiến Vương, Tổng cục
Địa chính, giáo sư Hoàng Kiếm, giáo sư Trần Vĩnh Phước, Đại học
Quốc gia thành phố Hồ Chí Minh đã thảo luận chi tiết về những nội
dung cơ bản và kiến trúc cho tập sách.
Đặc biệt, các đồng nghiệp trẻ, giáo sư Vũ Ngọc Loãn, Đại học
Quốc gia Hà Nội, giáo sư Nguyễn Thanh Thuỷ, Đại học Bách khoa Hà
Nội, tiến sỹ Trịnh Đình Thắng, Đại học Sư phạm Hà Nội II, tiến sỹ
Dương Anh Đức, tiến sỹ Đỗ Văn Nhơn, thạc sỹ Nguyễn Tấn Trần
Minh Khang, Đại học Quốc gia thành phố Hồ Chí Minh, thạc sỹ
Nguyễn Xuân Tùng, Trung tâm Tin học Bưu điện Hà Nội, thạc sỹ
Nguyễn Ngọc Hà, Trung tâm Tin học Bưu điện Hải Phòng, thạc sỹ
Trịnh Thanh Lâm, Intel, thạc sỹ Nguyễn Xuân Hoàng, Misa Group đã
có những góp ý cụ thể về nội dung chương trình đào tạo và các yêu
cầu thực tiễn của cơ sở dữ liệu. Các cử nhân Bùi Thuý Hằng và Trần
Quốc Dũng, Viện Công nghệ Thông tin đã giúp chúng tôi đọc lại và
chỉnh sửa các trang bản thảo.
5
9
10
Nguyễn Xuân Huy, Lê Hoài Bắc
Bài tập Cơ sở Dữ liệu
7
13
14
Nguyễn Xuân Huy, Lê Hoài Bắc
Bài tập Cơ sở Dữ liệu
Chú ý
Chương 1
Vì mỗi quan hệ là một tập các bộ nên trong quan hệ không có hai bộ trùng
lặp.
Các ký hiệu cơ bản
Quan hệ và Đại số quan hệ
Theo truyền thống của lý thuyết cơ sở dữ liệu chúng ta chấp nhận các quy
định sau đây:
Các thuộc tính được ký hiệu bằng các chữ LATIN HOA đầu bảng chữ
A, B, C,...
Tập thuộc tính được ký hiệu bằng các chữ LATIN HOA cuối bảng chữ
X, Y, Z,...
Tóm tắt lý thuyết
Quan hệ
Các thuộc tính trong một tập được liệt kê như một xâu ký tự, không có
các dấu biểu diễn tập, chẳng hạn ta viết X = ABC thay vì viết
X = A, B, C . XY biểu diễn hợp của hai tập thuộc tính X và Y,
X Y. Phép trừ hai tập hợp X và Y được ký hiệu là X-Y hoặc X \ Y.
Cho tập hữu hạn U = {A1, A2 , ... , An } khác trống (n 1). Các phần tử của
U
được gọi là thuộc tính. ứng với mỗi thuộc tính Ai U,
i = 1,2, ..., n có một tập không rỗng dom(Ai) được gọi là miền trị của thuộc
tính Ai.
Các bộ được biểu diễn bằng các chữ Latin thường có thể kèm chỉ số t,
u, v, t1 ...
n
Đặt D dom(A )
Với mỗi bộ t trong quan hệ R(U) và mỗi tập con các thuộc tính
i
i1
X U ta ký hiệu t[X] hoặc t.X là hạn chế của bộ t trên tập thuộc tính
X.
Một quan hệ R với các thuộc tính U = A1, A2 , ... , An , ký hiệu là R(U), là
một tập các ánh xạ t : U D sao cho với mỗi Ai U ta có t(Ai) dom(Ai).
Mỗi ánh xạ được gọi là một bộ của quan hệ R.
Hàm Attr(R) cho tập thuộc tính của quan hệ R.
Hàm Card(R) cho lực lượng (số bộ) của quan hệ R.
Mỗi quan hệ R(U) có hình ảnh là một bảng, mỗi cột ứng với một thuộc tính,
Trong trường hợp tập thuộc tính U đã cho trước ta có thể viết đơn giản
R thay cho R(U).
mỗi dòng là một bộ.
Ký hiệu REL(U) là tập toàn thể các quan hệ trên tập thuộc tính U.
Ta ký hiệu t(U) hoặc t / U là một bộ trên tập thuộc tính U.
Một quan hệ rỗng, ký hiệu , là quan hệ không chứa bộ nào.
8
15
16
Nguyễn Xuân Huy, Lê Hoài Bắc
Bài tập Cơ sở Dữ liệu
Hai quan hệ R và S được gọi là tương thích nếu chúng có cùng một tập thuộc
tính, tức là nếu Attr(R) = Attr(S).
Trong các biểu thức chọn ta sử dụng ký hiệu cho các phép toán logic như sau:
Tích: & hoặc AND
Tổng: | hoặc OR
Với mỗi bộ u trong quan hệ R(U) và mỗi bộ v trong quan hệ S(V) ta ký hiệu
uv là phép dán bộ. uv cho ta bộ t trên tập thuộc tính UV thoả điều kiện
t.U = u và t.V = v.
Phủ định: ! hoặc NOT
Kéo theo: hoặc IMPLY
Với mỗi bộ u trong quan hệ R(U) và với mỗi quan hệ S(V) ta ký hiệu uS là
phép dán bộ u với quan hệ S. uS cho ta quan hệ
Phép chiếu
P(UV) = { uv | v S }
Phép chiếu quan hệ R(U) trên tập con thuộc tính X U, ký hiệu R[X], cho ta
quan hệ
Để thể hiện các phép toán quan hệ ta sẽ dùng các ký pháp tựa như ký pháp
của hệ ISBL (Information System Base Language).
P(X) = R[X] = { t.X | t R }
R[X] được tính theo 2 bước như sau:
Đại số quan hệ
1. Xoá các cột không thuộc X của bảng R,
Phép chọn (phép lọc)
2. Xoá bớt các dòng giống nhau trong bảng kết quả: chỉ giữ lại một
dòng trong số các dòng giống nhau.
Cho quan hệ R(U) và biểu thức điều kiện (còn gọi là biểu thức lọc hay biểu
thức chọn) e. Phép chọn trên quan hệ R theo điều kiện e, ký hiệu R(e) cho ta
quan hệ:
Phép kết nối tự nhiên
Phép kết nối (tự nhiên) hai quan hệ R(U) và S(V), ký hiệu RS, cho ta quan hệ
chứa các bộ được dá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 trị trên miền thuộc tính chung (nếu có) của hai bộ này giống
nhau.
P(U) = R(e) = { t R | Sat(t, e) }
trong đó hàm logic Sat(t, e) kiểm tra bộ t thoả điều kiện e được xác định như
sau:
1. Thay mọi xuất hiện của mỗi thuộc tính A trong biểu thức chọn e
bằng trị tương ứng của A trong bộ t, t.A, ta thu được một mệnh đề
logic b.
P(UV) = RS = { uv | u R, v S, u.M = v.M, M = U V }
Nếu M = U V = , RS sẽ cho ta tích Descartes trong đó mỗi bộ của quan
hệ R sẽ được ghép với mọi bộ của quan hệ S.
2. Tính trị của b. Nếu là đúng (True) thì bộ t thoả điều kiện e; ngược
lại, nếu trị của b là sai (False) thì bộ t không thoả điều kiện e.
Phép cộng (hợp)
9
17
18
Nguyễn Xuân Huy, Lê Hoài Bắc
Bài tập Cơ sở Dữ liệu
Phép cộng (hợp theo lý thuyết tập hợp hoặc kết nối dọc) hai quan hệ tương
thích R(U) và S(U), ký hiệu R+S, cho ta quan hệ chứa các bộ của mỗi quan hệ
thành phần,
trừ. Thứ tự ưu tiên từ cao đến thấp của các phép toán quan hệ được liệt kê
như sau:
( ) , [ ]
, & , :
+ , -
P(U) = R+S = { t | t R t S }
Phép trừ
Phép trừ (theo lý thuyết tập hợp hoặc lấy phần riêng) hai quan hệ tương thích
R(U) và S(U), ký hiệu R-S, cho ta quan hệ chứa các bộ của quan hệ R không
có trong quan hệ S,
Dãy các phép toán cùng thứ tự ưu tiên được thực hiện lần lượt từ trái qua
phải. Nếu biểu thức quan hệ có chứa các cặp ngoặc ( ) thì các biểu thức con
trong các cặp ngoặc được thực hiện trước.
P(U) = R-S = { t | t R, t S }
Một số hàm tiện ích
Phép giao
1. Sum(R,A): cho tổng các giá trị số trong thuộc tính (cột) A của quan hệ R,
Sum(R,A) = ( t.A | t R )
Phép giao (theo lý thuyết tập hợp hoặc lấy phần chung) hai quan hệ tương
thích R(U) và S(U), ký hiệu R&S, cho ta quan hệ chứa các bộ xuất hiện đồng
thời trong cả hai quan hệ thành phần,
2. Avg(R,A): cho trung bình cộng các giá trị trong thuộc tính (cột) A của quan
hệ R,
P(U) = R&S = { t | t R, t S }
Avg(R,A) = Sum(R,A) / Card(R) nếu Card(R) 0
3. Max(R ,A): cho giá trị lớn nhất trong thuộc tính (cột) A của quan hệ R.
4. Min(R,A): cho giá trị nhỏ nhất trong thuộc tính (cột) A của quan hệ R.
Các phép toán cộng, trừ và giao đựơc gọi là các phép toán tập hợp trên các
quan hệ (tương thích).
Phép chia
Cho hai quan hệ R(U) và S(V). Phép chia quan hệ R cho quan hệ S, ký hiệu
R : S, cho ta quan hệ
Nếu trong biểu thức quan hệ có chứa các hàm tiện ích thì các hàm này được
thực hiện sớm nhất trong ngữ cảnh cho phép.
P(M) = R : S = { t.M | tR, (t.M)S R, M = U - V }
Thí dụ
Thứ tự thực hiện các phép toán quan hệ
Biểu thức quan hệ P = SR(A > Avg(S,A))[AB] sẽ được thực hiện theo trật tự
sau đây:
Trong một biểu thức quan hệ các phép toán một ngôi có độ ưu tiên cao hơn
(do đó được thực hiện sớm hơn) các phép toán hai ngôi. Tiếp đến là nhóm
các phép toán kết nối, giao và chia, cuối cùng là nhóm các phép toán cộng và
1. Tính hàm c = Avg(S,A)
10
19
20
Nguyễn Xuân Huy, Lê Hoài Bắc
Bài tập Cơ sở Dữ liệu
2. Thực hiện phép chọn P1 = R(A > c)
3. Thực hiện phép chiếu P2 = P1 [AB]
4. Thực hiện phép kết nối P = SP2
SV# - mã số sinh viên
HT - họ và tên sinh viên
NS - năm sinh của sinh viên
QUE - quê (tỉnh)
Chú ý: Trong một số tài liệu có sử dụng ký pháp khác cho các phép toán
quan hệ như sau
HL - học lực thể hiện qua điểm trung bình
Quan hệ DT(DT#, TDT, CN, KP) chứa thông tin về các đề tài nhà
Phép toán
Ký hiệu
R(e)
Ký hiệu khác
e(R)
trường quản lý,
Chọn
DT - tên quan hệ đề tài
DT# - mã số đề tài
Chiếu
R[X]
X(R)
Kết nối tự nhiên
R S
R + S
R & S
R - S
R ⋈ S
R S
TDT - tên đề tài
Cộng
Giao
Trừ
R S
CN - họ và tên chủ nhiệm đề tài
KP - kinh phí cấp cho đề tài (triệu đồng).
R \ S
Chia
R : S
R S
Quan hệ SD(SV#, DT#, NTT, KM, KQ) chứa thông tin về tình hình
thực tập của các sinh viên theo các đề tài,
Cơ sở dữ liệu minh họa: CSDL Thực tâp
Hầu hết bài tập trong chương này liên quan đến CSDL Thực tập gồm ba
SD - tên quan hệ sinh viên - đề tài
SV# - mã số sinh viên
quan hệ sau đây:
SV(SV#, HT, NS, QUE, HL)
DT(DT#, TDT, CN, KP)
DT# - mã số đề tài mà sinh viên đó tham gia
NTT - nơi thực tập để triển khai đề tài (tỉnh)
KM - khoảng cách từ nơi thực tập đến trường
KQ - kết quả thực tập theo đề tài đã chọn
SD(SV#, DT#, NTT, KM, KQ)
Quan hệ SV(SV#, HT, NS, QUE, HL) chứa thông tin về các sinh viên
trong một lớp của một trường đại học,
Giả thiết là một sinh viên có thể tham gia nhiều đề tài, mỗi đề tài
SV - tên quan hệ sinh viên
sinh viên đó thực tập tại một điạ điểm.
11
21
22
Nguyễn Xuân Huy, Lê Hoài Bắc
Bài tập Cơ sở Dữ liệu
1.3. Cho danh sách các tỉnh có sinh viên đến thực tập?
Với mỗi câu hỏi, yêu cầu trả lời bằng một biểu thức của đại số
quan hệ. Tuổi được tính đến năm 2003. Thí dụ,
1.4. Cho biết các địa điểm thực tập xa trường (KM > 100) của đề tài số 7?
1.5. Cho thông tin về việc thực tập tại Nha Trang của các sinh viên?
*1.6. Cho danh sách sinh viên thực tập tại quê nhà?
Câu hỏi
Cho danh sách các sinh viên trẻ (dưới 18 tuổi tính đến năm 2003), học và
thực tập đều đạt loại khá/giỏi (điểm không dưới 8.5)
1.7. Cho thông tin về các đề tài có sinh viên thực tập?
Trả lời
1.8. Cho biết mã của các đề tài không có sinh viên nào tham gia?
(SD(KQ >= 8.5)[SV#]SV)(2003-NS < 18 & HL >= 8.5)[HT]
1.9. Cho biết mã của những đề tài có kinh phí 1.5 triệu và những đề tài có
kinh phí trên 2 triệu?
1.10. Cho biết mã của những sinh viên dưới 20 tuổi, thực tập khá (có điểm
Bài tập
kết quả trên 7)?
*1.11. Cho biết mã của những đề tài có địa bàn thực tập ít ra là như đề tài 1.
1.1. Cho hai quan hệ R(A,B,C,D) và S(C,D) như sau
*1.12. Cho danh sách những đề tài được triển khai thực tập ở tất cả các tỉnh
có sinh viên thực tập.
Hãy xác định:
a) R[AB]
*1.13. Cho danh sách những sinh viên thực tập theo đề tài có kinh phí lớn
hơn một phần năm tổng kinh phí cấp cho các đề tài.
b) R(3-B+D >1)
c) R(B < 4) + R(D > 3)
d) R(B >= 1 & B <= 5)
e) RS[C]
*1.14. Cho danh sách các sinh viên có điểm học tập cao hơn điểm thực tập
trung bình của đề tài mã số 4.
1.15. Một phép toán 2 ngôi có tính chất giao hoán nếu:
( R, S): R S = S R
f) R(B < 4) - R(D > 3)
g) R(B < 4) & R(D > 3)
h) R : S
hoặc cả hai vế đồng thời không có nghĩa.
Chứng minh rằng các phép toán quan hệ kết nối, cộng và giao có tính giao
hoán.
1.2. Cho thông tin về những sinh viên sinh trước năm 1983, quê ở Hải
Phòng?
12
23
24
Nguyễn Xuân Huy, Lê Hoài Bắc
Bài tập Cơ sở Dữ liệu
1.16. Tìm thí dụ chứng tỏ các phép toán trừ và chia không có tính giao
hoán.
1.20. Phép toán quan hệ được gọi là đóng nếu với mọi quan hệ đầu vào ta đều
thu được đầu ra là một quan hệ. Cho biết tính đóng (ghi có / không) của các
phép toán quan hệ
1.17. Cho quan hệ R(U) và hai biểu thức chọn e và h. Chứng minh
a) R(e & h) = R (h & e)
b) R(e & h) = R (e) & R(h) R(e)
c) R(e & h) = R(h) & R(e) R(h)
d) R(e & h) = R(e)(h)
e) R(e | h) = R(h | e)
Phép toán
Ký hiệu
Tính đóng
Chọn
Chiếu
( )
[ ]
Kết nối tự nhiên
Cộng
Giao
Trừ
+
&
-
f) R(e | h) = R(e) + R(h)
g) R(! e) = R - R(e)
h) R(True) = R
Chia
:
i) R(False) =
1.18. Cho quan hệ R(U), các biểu thức chọn e, h trên U và tập con các thuộc
tính X U. Ký hiệu Attr(e) là tập các thuộc tính của U có mặt trong e.
Chứng minh, nếu Attr(e) X thì
1.21. Phép toán 2 ngôi có tính chất kết hợp nếu:
( R, S, T): (R S) T = R (S T)
a) R(e)[X] = R[X](e)
hoặc cả hai vế đồng thời không có nghĩa.
b) R(h & e)[X] = R(h)(e)[X] = R(h)[X](e)
Chứng minh rằng các phép toán kết nối, cộng và giao của đại số quan hệ có
tính chất kết hợp.
1.22. Tìm thí dụ chứng tỏ các phép toán trừ và chia không có tính kết hợp.
1.23. Chứng minh rằng với mọi cặp quan hệ tương thích R và S ta có
R - (R - S) = R & S
*1.19. Chứng minh rằng phép chia có thể được biểu diễn qua các phép chiếu,
kết nối và trừ như sau,
R : S = R[M] - (R[M]S - R)[M]
trong đó M = Attr(R) - Attr(S).
1.24. Chứng minh rằng với mọi quan hệ R(U), mọi tập con X trong U và
mọi biểu thức điều kiện e ta có
13
25
26
Nguyễn Xuân Huy, Lê Hoài Bắc
Bài tập Cơ sở Dữ liệu
a) R(e)(e) = R(e)
b) R[X][X] = R[X]
Phép toán
Ký hiệu
Nở/Co ngang
Nở/Co dọc
Chọn
Chiếu
( )
[ ]
1.25. Chứng minh rằng với mọi quan hệ R(U) ta có
a) R R = R
Kết nối tự nhiên
Cộng
b) R + R = R
+
&
-
c) R & R = R
Giao
d) R - R =
Trừ
e) R : R = , Attr(R : R) = .
Chia
:
1.26. Phép toán quan hệ được gọi là nở (co) ngang nếu quan hệ kết quả có số
thuộc tính nhiều hơn (ít hơn) các quan hệ đầu vào, được gọi là nở (co) dọc
nếu quan hệ kết quả có số bộ nhiều hơn (ít hơn) các quan hệ đầu vào. Hãy
đánh dấu (+), (-) hoặc (=) để khẳng định tính nở hoặc co hoặc không nở/co
của mỗi phép toán tương ứng.
1.27. Cho quan hệ R(U) và e và h là hai biểu thức chọn trên U. Chứng minh,
nếu e h thì:
a) R(e)(h) = R(e)
b) R(e) R(h)
1.28. Gọi T và F lần lượt là các công thức logic hằng đúng và hằng sai.
Chứng minh rằng với mọi quan hệ R ta có:
a) R(T) = R
b) R(F) =
*1.29. Cho quan hệ R(U). Hãy dùng một phép toán quan hệ để sinh ra quan
hệ rỗng S(U).
1.30. Chứng minh rằng với mọi quan hệ R(U) và mọi tập thuộc tính X và Y
thoả điều kiện X Y U thì
14
27
28
Nguyễn Xuân Huy, Lê Hoài Bắc
Bài tập Cơ sở Dữ liệu
Cho tập thuộc tính U. Cố định các tập con X1, X2,..., Xk của U thoả điều kiện
X1 X2 ... Xk = U.
R[Y][X] = R[X]
1.31. Cho hai quan hệ R(U) và S(V) và hai biểu thức chọn e trên U, h trên V.
Xét ánh xạ : REL(U) REL(U)
Chứng minh
R REL(U): (R) = R[X1] R[X2] ... R[Xk]
Chứng minh là một ánh xạ đóng trên REL(U).
(RS)(e & h) = R(e)S(h)
1.32. Cho các quan hệ R(U), S(V) và các tập thuộc tính X U, Y V. Biết Z
= U V. Chứng minh
*1.36. (Nghịch lý giao hoán-kết hợp) Ta đã biết phép kết nối tự nhiên () có
tính kết hợp và giao hoán. Xét các quan hệ SV, DT và SD trong cơ sở dữ liệu
Thực tập. Hai quan hệ SV và DT không có thuộc tính chung, trong khi hai
quan hệ SV và SD chung nhau thuộc tính SV# và hai quan hệ SD và DT
chung nhau thuộc tính DT#. Giải thích vì sao
(RS)[XZY] = R[XZ]S[ZY]
*1.33. Cho quan hệ R(U) và các tập con X1, X2, ..., Xk thoả điều kiện
X1 X2 ... Xk = U . Chứng minh
R[X1] R[X2] ... R [Xk] R
Tìm thí dụ chứng tỏ R[X1] R[X2] ... R [Xk] R
*1.34. Cho quan hệ R(U) và hai tập con thuộc tính X Y U. Chứng minh
a) R[U] = R
SV (SD DT) = (SV SD) DT = (SV DT) SD
Cho biết kết quả của phép kết nối (SV DT) trong biểu thức phải.
_______________________
b) R [X] R [X] = R[X]
c) R[Y] R[X] = R[Y]
d) R R[X] = R
*1.35. Cho tập hữu hạn các phần tử M. Ký hiệu P(M) là tập các tập con của
M. Ánh xạ f: P(M) P(M) được gọi là đóng nếu f thoả ba tính chất sau:
X, Y P(M):
(C1) Tính phản xạ: f(X) X
(C2) Tính đồng biến: nếu X Y thì f(X) f(Y)
(C3) Tính luỹ đẳng: f(f(X)) = f(X)
15
29
30
Nguyễn Xuân Huy, Lê Hoài Bắc
Bài tập Cơ sở Dữ liệu
(T6) t [not_]in R
Hàm cho giá trị True nếu bộ t [không] có trong quan hệ R, ngược lại hàm cho
giá trị False.
Chương 2
(T7) add t to R
Nạp bộ t vào quan hệ R.
(T8) t[X]hoặc t.X
Các thao tác trên bộ và quan hệ
Tạo bộ mới từ bộ t với tập thuộc tính X. Bộ mới bao gồm các giá trị của mỗi
thuộc tính A trong t, A X.
(T9) t/X
Tạo bộ mới từ bộ t bằng cách bỏ đi những giá trị của mỗi thuộc tính A trong t,
A X.
Tóm tắt lý thuyết
Trong phần trình bày cú pháp của các cấu trúc điều khiển (câu lệnh) và các
hàm thao tác trên bộ và quan hệ dưới đây phần viết trong [ ] là tuỳ chọn.
(T10) uv
Tạo bộ mới bằng phép dán bộ v với bộ u. Các giá trị trên miền thuộc tính
chung của hai bộ u và v phải bằng nhau và chỉ lấy một trong hai trị bằng nhau
trên mỗi thuộc tính chung.
(T1) for each t in R [with e] do P endfor
Thực hiện toán tử P trên những bộ t của quan hệ R [nếu thoả điều kiện e].
(T2) if e then P[else Q] endif
Nếu điều kiện e thoả thì thực hiện P [nếu không, thực hiện Q]
(T3) Create(R,X)
Các thuật toán được diễn đạt thông qua ngôn ngữ quy ước sau đây:
Algorithm <tên thuật toán>
Format
Input
Output
Method
Tạo lập quan hệ rỗng R (không chứa bộ nào) với tập thuộc tính X cho trước.
(T4) Attr(R)
// Chú thích được viết sau hai gạch nghiêng
End.
Hàm cho tập thuộc tính của quan hệ R.
(T5) Card(R)
Hàm cho biết lực lượng (số bộ) của quan hệ R.
16
31
32
Nguyễn Xuân Huy, Lê Hoài Bắc
Bài tập Cơ sở Dữ liệu
2.12. Cài đặt hàm Avg(R,A): cho trung bình cộng các giá trị trong thuộc tính
(cột) A của quan hệ R,
Bài tập
Avg(R,A) = Sum(R,A) / Card(R), nếu Card(R) 0
2.13. Cài đặt hàm Max(R, A): cho giá trị lớn nhất trong thuộc tính (cột) A của
quan hệ R.
2.1. Viết thuật toán thực hiện phép chọn trên quan hệ: R(e).
2.2. Viết thuật toán thực hiện phép chiếu trên quan hệ: R[X].
2.3. Viết thuật toán thực hiện phép kết nối tự nhiên hai quan hệ: RS.
2.4. Viết thuật toán thực hiện phép hợp hai quan hệ tương thích: R+S.
2.5. Viết thuật toán thực hiện phép giao hai quan hệ tương thích: R&S.
2.6. Viết thuật toán thực hiện phép trừ hai quan hệ tương thích: R-S.
2.7. Viết thuật toán thực hiện phép chia hai quan hệ: R:S.
2.14. Cài đặt hàm Min(R, A): cho giá trị nhỏ nhất trong thuộc tính (cột) A của
quan hệ R.
2.15. Cài đặt hàm Sum(R,A,e): cho tổng các giá trị trong thuộc tính (cột) A
của quan hệ R xét trên những bộ thoả điều kiện e,
Sum(R,A,e) = Sum(R(e),A) =
t.A
.
tR
sat(t,e)
2.8. Phép chọn_chiếu quan hệ R(U) theo biểu thức chọn e và trên tập con
thuộc tính X U cho ta quan hệ
2.16. Cài đặt hàm Count(R,e): cho số lượng các bộ thoả điều kiện e trong
quan hệ R.
P(X) = R(e,X) = R(e)[X] = { t.X | t R, Sat(t,e) }
2.17. Cài đặt hàm Avg(R,A,e): cho trung bình cộng của các giá trị không nhất
thiết khác nhau trong thuộc tính (cột) A của quan hệ R xét trên những bộ thoả
điều kiện e.
Viết thuật toán thực hiện trực tiếp phép chọn_chiếu.
2.9. Phép kết_nối_chọn_chiếu hai quan hệ R(U) và S(V) theo biểu thức chọn
e và trên tập con thuộc tính X UV cho ta quan hệ
2.18. Cài đặt hàm Maxe(R, A, e): cho giá trị lớn nhất trong thuộc tính (cột) A
của quan hệ R xét trên những bộ thoả điều kiện e.
P(X) = (RS)(e,X) = (RS)(e)[X] =
= { (uv).X | uR, vS, u.M = v.M, M = U V, Sat(uv,e) }
Viết thuật toán thực hiện trực tiếp phép kết_nối_chọn_chiếu.
2.10. Cài đặt hàm Card(R): cho lực lượng (số bộ) của quan hệ R.
2.11. Cài đặt hàm Sum(R,A): cho tổng các giá trị trong thuộc tính (cột) A của
2.19. Cài đặt hàm Mine(R, A, e): cho giá trị nhỏ nhất trong thuộc tính (cột) A
của quan hệ R xét trên những bộ thoả điều kiện e.
_________________________________
quan hệ R: Sum(R,A) =
t.A
.
tR
17
33
34
Nguyễn Xuân Huy, Lê Hoài Bắc
Bài tập Cơ sở Dữ liệu
(R1 R2. . .Rp)(e)[X]
trong đó phép được hiểu là phép kết nối có điều kiện. Điều kiện này được
xác định trong mục WHERE.
Khi liệt kê tên các thuộc tính, để tránh hiện tượng trùng tên của hai thuộc tính
trong hai quan hệ khác nhau ta có thể chỉ rõ quan hệ chứa thuộc tính đó. Thí
dụ, R.A nói về thuộc tính A của quan hệ R. Từ khoá DISTINCT là chỉ thị
lược bớt các bộ trùng lặp ở kết quả.
Chương 3
Ngôn ngữ hỏi SQL
Các từ khóa và ký hiệu
* - danh sách đầy đủ các thuộc tính
IN - là phần tử của
NOT IN - không phải là phần tử của
ANY - một phần tử, một xuất hiện
ALL - với mọi
(Structured Query Language)
AND - phép nhân logic
Tóm tắt lý thuyết
OR - phép cộng logic
SQL là ngôn ngữ hỏi thuộc lớp ngôn ngữ các phép tính trên bộ.
Cấu trúc chính của SQL có dạng
NOT - phép phủ định
ORDER BY DESC/ASC - sắp giảm/tăng
GROUP BY - nhóm theo
SELECT [DISTINCT/UNIQUE]
FROM R1, R2,...,Rp
WHERE e;
X
CONTAINS - chứa
UNION - hợp hai quan hệ tương thích
INTERSECTION - giao hai quan hệ tương thích
DIFFERENCE/MINUS - trừ hai quan hệ tương thích
trong đó X là danh sách các thuộc tính của quan hệ kết quả, R1, R2,...,Rp là
các quan hệ, e là điều kiện. Cấu trúc trên tương đương với biểu thức đại số
quan hệ sau đây
18
35
36
Nguyễn Xuân Huy, Lê Hoài Bắc
Bài tập Cơ sở Dữ liệu
EXISTS - cho giá trị True nếu biểu thức sau nó chứa
3.5. Danh sách các sinh viên học giỏi hơn các sinh viên Hà Nội.
ít nhất một bộ, ngược lại cho giá trị False.
3.6. Điểm trung bình của các sinh viên Hà Nội.
3.7. Tổng số đoạn đường thực tập theo đề tài 5.
Các hàm trên cột
3.8. Tổng số sinh viên đi thực tập.
COUNT - cho số lượng phần tử của cột
SUM - cho tổng các trị trong cột
3.9. Số tỉnh có sinh viên đến thực tập theo đề tài 5.
3.10. Danh sách các tỉnh và số sinh viên quê ở tỉnh đó, nhóm theo QUE.
MIN - cho giá trị nhỏ nhất trong cột
MAX - cho giá trị lớn nhất trong cột
AVG - cho giá trị trung bình cộng của cột
3.11. Các đề tài có trên 10 sinh viên đăng ký tham gia:
*3.12. Dùng SQL để biểu thị các phép toán của đại số quan hệ:
a) R(e)
b) R[X]
c) RS
d) R+S
e) R&S
f) R-S
Bí danh là các định danh đặt thêm cho một quan hệ để tiện dùng
Bài tập
Các bài tập liên quan đến CSDL Thực tập gồm ba quan hệ như đã mô tả
trong chương về đại số quan hệ.
3.13. Cho thông tin về những sinh viên sinh trước năm 1973 và quê ở Hải
SV(SV#, HT, NS, QUE,HL)
Phòng?
DT(DT#,TDT,CN,KP)
3.14. Cho danh sách các tỉnh có sinh viên đến thực tập?
3.15. Cho biết các địa điểm thực tập xa trường (KM > 100) của đề tài số 7?
3.16. Cho thông tin về việc thực tập tại Nha Trang của các sinh viên?
*3.17. Cho danh sách sinh viên thực tập tại quê nhà?
SD(SV#,DT#,NTT,KM, KQ)
Với mỗi câu hỏi, yêu cầu trả lời bằng một biểu thức SQL.
3.1. Danh sách các sinh viên trẻ (dưới 18 tuổi) và học khá/giỏi (HL > 8.5)
3.2. Thông tin về các đề tài được cấp kinh phí trên 10 triệu đồng
3.18. Cho thông tin về các đề tài có sinh viên thực tập?
3.19. Cho biết mã của các đề tài không có sinh viên nào tham gia?
3.3. Danh sách các sinh viên trẻ (dưới 18 tuổi), học và thực tập đều đạt loại
khá/giỏi (HL > 8.5 và KQ > 8.5)
3.20. Cho biết mã của những đề tài có kinh phí 1.5 triệu và những đề tài có
kinh phí trên 2 triệu?
3.4. Danh sách các chủ nhiệm đề tài có các sinh viên quê ở Hà Nội tham gia.
19
37
38
Nguyễn Xuân Huy, Lê Hoài Bắc
Bài tập Cơ sở Dữ liệu
3.21. Cho biết mã của những sinh viên dưới 24 tuổi, thực tập khá (có điểm
kết quả trên 6)?
*3.22. Cho danh sách các đề tài có sinh viên học giỏi nhất lớp tham gia.
*3.23. Cho danh sách các đề tài không có sinh viên học kém nhất lớp tham
gia.
*3.24. Cho danh sách những sinh viên thực tập theo đề tài có kinh phí lớn
hơn một phần năm tổng kinh phí cấp cho các đề tài.
*3.25. Cho danh sách các sinh viên có điểm học tập cao hơn điểm thực tập
trung bình của đề tài mã số 4.
*3.26. Cho quan hệ R(U). Hãy dùng SQL để sinh ra quan hệ rỗng S(U).
__________________
20
39
40
Tải về để xem bản đầy đủ
134 trang
18101
Free
Bạn đang xem 20 trang mẫu của tài liệu "Giáo trình Bài tập Cơ sở dữ liệu", để tải tài liệu gốc về máy hãy click vào nút Download ở trên
File đính kèm:
- giao_trinh_bai_tap_co_so_du_lieu.pdf
