Mô hình quan hệ

Mô hình quan hệ (Relational model)

EE4509, EE6133 – HK2 2011/2012 TS. Đào Trung Kiên – ĐH Bách khoa Hà Nội

Giới thiệu

Họ tên Tuổi Giới tính

 Mô hình quan hệ sử dụng lý thuyết tập hợp và logic bậc nhất để biểu diễn dữ liệu

Trần Khánh Linh 25 Nam

 CSDL được biểu diễn bằng một tập

Bill Gates 50 Nam

Lý Liên Kiệt 45 Nam

Lưu Diệc Phi 25 Nữ

các bảng:  Mỗi bảng là tập hợp các các bộ giá trị  Mỗi cột đều có cùng một kiểu dữ liệu  Mỗi hàng trong bảng là bộ các giá trị có

Nguyễn Văn Bố 37 Nam

Lê Thị Mẹ 30 Nữ

quan hệ với nhau  So sánh với mô hình ER:

… … …

 Mỗi bảng tương ứng với một tập thực

… … …

thể

 Mỗi cột tương ứng một thuộc tính  Mỗi hàng trong bảng tương ứng với

một thực thể

… … …

EE4509, EE6133 – HK2 2011/2012 TS. Đào Trung Kiên – ĐH Bách khoa Hà Nội

Các định nghĩa

 Một mô hình quan hệ là tập hợp các quan hệ (relation)  Mỗi quan hệ gồm 2 phần:

 Thể hiện (instance): là bảng các bộ giá trị (tuples)  Lược đồ (schema): chứa tên của quan hệ, cùng với tên và kiểu

từng cột của bảng  VD: Book(id: integer, title: string, author: string, pub-year: integer)  Số dòng của bảng: lực lượng (cardinality) của quan hệ  Số cột của bảng: bậc (degree) của quan hệ  VD:

id title author pub-year

 Lực lượng: 3  Bậc: 4

1 The call of the wild Jack London 1903

3 The universe in a nutshell Stephen Hawking 2001

4 Hồng lâu mộng Tào Tuyết Cần 1791

EE4509, EE6133 – HK2 2011/2012 TS. Đào Trung Kiên – ĐH Bách khoa Hà Nội

Định nghĩa bằng toán học

 Lược đồ quan hệ R là tích Đề-các các miền giá trị của

các thuộc tính  Đầy đủ: Book(id: int, title: string, author: string, pub-year: int)  Ngắn gọn: Book(id, title, author, pub-year)

Book = dom(int) × dom(string) × dom(string) × dom(int) (trong đó dom(…) ký hiệu tập giá trị của một kiểu)

 Quan hệ r trên R: ký hiệu bằng r(R) là một tập con của R

my-books = my-books(Book) ⊂ Book

 Một phần tử của r gọi là một thể hiện, một hàng, hay một

bộ giá trị

 Chú ý: người ta thường gọi tắt “quan hệ” thay cho “thể

hiện của quan hệ”

EE4509, EE6133 – HK2 2011/2012 TS. Đào Trung Kiên – ĐH Bách khoa Hà Nội

Khoá (key)

 Các khái niệm về khoá của quan hệ cũng tương tự như

với thực thể trong mô hình ER

 Siêu khoá (superkey): tập các thuộc tính mà bộ giá trị

không lặp lại  Nếu K là một siêu khoá thì K’ = K ∪ a cũng là một siêu khoá, với a

là một thuộc tính của quan hệ

 Khoá ứng viên (candidate key): là siêu khoá không cố thuộc tính dư thừa (không tồn tại siêu khoá là tập con)  Một quan hệ có thể có 0, 1 hoặc nhiều siêu khoá

 Khoá chính (primary key): là một khoá ứng viên được

người thiết kế CSDL lựa chọn  Mỗi quan hệ chỉ có nhiều nhất một khoá chính

EE4509, EE6133 – HK2 2011/2012 TS. Đào Trung Kiên – ĐH Bách khoa Hà Nội

Ví dụ

 K1 = {A} không phải khoá vì các giá trị có

A B C

lặp lại

1 aa x

 K2 = {A, B} là siêu khoá vì không có bộ giá

trị nào lặp lại

1 ab x

 K3 = {A, B, C} là siêu khoá vì K2 là siêu

2 ab y

khoá và K2 ⊂ K3

2 bb y

 K2 là khoá ứng viên vì không có tập con

3 ab x

nào của K2 là siêu khoá

3 bb x

 K3 không phải khoá ứng viên vì K2 ⊂ K3 là

4 aa y

một siêu khoá

5 bb x

EE4509, EE6133 – HK2 2011/2012 TS. Đào Trung Kiên – ĐH Bách khoa Hà Nội

Khoá ngoài (foreign key)

 Một quan hệ r1 có chứa khoá chính K của quan hệ r2 thì K gọi là khoá ngoài của r1 tham chiếu tới r2  Với mỗi thể hiện của r1, tồn tại ít nhất một thể hiện

của r2 có giá trị của K giống ở r1

 Ví dụ:

o sv ⊂ SinhVien(id-sinh-vien, ten, nam-sinh) diem ⊂ Diem(id-sinh-vien, mon-hoc, diem) o id-sinh-vien là khoá ngoài của quan hệ diem tham chiếu

tới quan hệ sv

o mỗi giá trị của id-sinh-vien tồn tại trong quan hệ diem

cũng tồn tại trong quan hệ sv

EE4509, EE6133 – HK2 2011/2012 TS. Đào Trung Kiên – ĐH Bách khoa Hà Nội

Sơ đồ CSDL

 Một mô hình quan hệ cũng có thể được biểu diễn

dưới dạng sơ đồ

EE4509, EE6133 – HK2 2011/2012 TS. Đào Trung Kiên – ĐH Bách khoa Hà Nội

Biến thực thể  quan hệ

 Customer(cid, name, address, phone)

EE4509, EE6133 – HK2 2011/2012 TS. Đào Trung Kiên – ĐH Bách khoa Hà Nội

Thực thể yếu

 Book(bid, name, author, publisher, pub_date) Chapter(ch_num, bid, title)

EE4509, EE6133 – HK2 2011/2012 TS. Đào Trung Kiên – ĐH Bách khoa Hà Nội

Quan hệ 1-n

 Book(bid, name, author_id, publisher, pub_date) Author(aid, name)

EE4509, EE6133 – HK2 2011/2012 TS. Đào Trung Kiên – ĐH Bách khoa Hà Nội

Quan hệ n-n

 Sinh ra một quan hệ phụ

 Student(sid, name, birthday) Class(cid, name, room, teacher) Registration(sid, cid)

EE4509, EE6133 – HK2 2011/2012 TS. Đào Trung Kiên – ĐH Bách khoa Hà Nội

Ngôn ngữ truy vấn (query language)

 Để thao tác trên các quan hệ, chúng ta cần đến

ngôn ngữ truy vấn

 Ngôn ngữ truy vấn thường là ngôn ngữ cấp cao hơn

so với các ngôn ngữ lập trình  VD: SQL

 Trong phần tiếp theo, chúng ta tìm hiểu về ngôn ngữ

truy vấn ở dạng lý thuyết hình thức

EE4509, EE6133 – HK2 2011/2012 TS. Đào Trung Kiên – ĐH Bách khoa Hà Nội

Đại số quan hệ (Relational algebra)

EE4509, EE6133 – HK2 2011/2012 TS. Đào Trung Kiên – ĐH Bách khoa Hà Nội

Khái niệm

 Đại số quan hệ là một ngôn ngữ truy vấn dạng thủ

tục (procedural query language), là một tập hợp các phép toán:  Có một hoặc hai đầu vào là các quan hệ  Đầu ra (kết quả) là một quan hệ mới

 Các phép toán cơ bản: select (chọn), project (chiếu), union (hợp), set-diffrence (trừ), Cartesian-product (tích Đề-các) và rename (đổi tên)

 Một số phép toán khác: set-intersection (giao),

natural-join (gộp), division (chia), assignment (gán)  Được định nghĩa dựa vào các phép toán cơ bản

EE4509, EE6133 – HK2 2011/2012 TS. Đào Trung Kiên – ĐH Bách khoa Hà Nội

Select (phép chọn) σ

 Phép select nhận đầu vào là một quan hệ, và cho phép lựa chọn những bộ giá trị trong quan hệ đó thoả mãn một điều kiện (vị ngữ)

 Ký hiệu: σvị ngữ(r)  VD:

id

sản phẩm

tiền …

1 máy tính

20 …

3 điện thoại

10 …

4 máy tính

22 …

 σnăm-sinh <= 1950(tác-giả)  σsản-phẩm = “máy tính”(hoá-đơn)

σsản-phẩm = “máy tính”(hoá-đơn)

tivi

5 …

id sản phẩm tiền …

tủ lạnh

8 …

1 máy tính 20 …

4 máy tính 22 … 11 máy tính 13 …

11 máy tính 13 …

EE4509, EE6133 – HK2 2011/2012 TS. Đào Trung Kiên – ĐH Bách khoa Hà Nội

Project (phép chiếu) Π

 Phép project nhận đầu vào là một quan hệ, và cho

phép chỉ giữ lại những thuộc tính mong muốn

title author

 Ký hiệu: Πcác thuộc tính giữ lại(r)  VD:

The call of the wild Jack London

The universe in a nutshell Stephen Hawking

 Πid, tên(tác-giả)  Πsản-phẩm, tiền(hoá-đơn)

Πtitle, author(sách)

Hồng lâu mộng Tào Tuyết Cần

id title author pub-year

1 The call of the wild Jack London 1903

3 The universe in a nutshell Stephen Hawking 2001

4 Hồng lâu mộng Tào Tuyết Cần 1791

EE4509, EE6133 – HK2 2011/2012 TS. Đào Trung Kiên – ĐH Bách khoa Hà Nội

Union (phép hợp) ∪

 Phép union nhận đầu vào là hai quan hệ tương thích với nhau và kết quả là quan hệ bao gồm những bộ giá trị có mặt ở một trong hai quan hệ

 Ký hiệu: r1 ∪ r2  VD:

 thành-phố-Mỹ ∪ thành-phố-VN  sách-văn-học ∪ sách-lịch-sử

tên món

giá

tên món

giá

phở 30 phở 30

đồ-ăn ∪ đồ-uống

bún 25 bún 25

cơm 40 cơm 40

cafe 30

tên món

giá

nước cam 25 30 cafe

coca 40 25 nước cam

EE4509, EE6133 – HK2 2011/2012 TS. Đào Trung Kiên – ĐH Bách khoa Hà Nội

40 coca 18

Set-difference (trừ) –

 Phép set-difference nhận đầu vào là hai quan hệ tương

thích với nhau, và trả về kết quả là những bộ giá trị trong quan hệ thứ nhất mà không có trong quan hệ thứ hai

 Ký hiệu: r1 – r2  VD:

sản phẩm giá

Xoom 15

Galaxy Tab 13

 thực-đơn – đồ-ăn  máy-tính – laptop  điện-thoại – sản-phẩm-Apple

Desire S 10

điện-thoại – sản-phẩm-Apple

sản phẩm giá

Xoom 15

iPhone

Galaxy Tab 13 sản phẩm giá

Desire S 10 Macbook 30

iPad 17 iPad 17

EE4509, EE6133 – HK2 2011/2012 TS. Đào Trung Kiên – ĐH Bách khoa Hà Nội

19 iPod 5

Cartesian-product (tích Đề-các) ×

 Phép Cartesian-product nhận đầu vào là hai quan hệ, và

trả về kết quả là tập tất cả các bộ giá trị giữa chúng

 Ký hiệu: r1 × r2  VD:

id chi nhánh id nhân viên nhân- viên.tên chi- nhánh.tên

123

Lê Đức Thọ

Sài Gòn

123 Lê Đức Thọ 2 Hà Nội

 ca-sĩ × bài-hát  nhân-viên × chi-nhánh

123 Lê Đức Thọ 3 Đà Nẵng

427 Bùi Văn Hải 2 Hà Nội

427

Bùi Văn Hải

Đà Nẵng

427 Bùi Văn Hải 1 Sài Gòn id nhân viên tên

123 Lê Đức Thọ

nhân-viên × chi-nhánh

427 Bùi Văn Hải

id chi nhánh tên

2 Hà Nội

Để tránh trùng tên, dùng ký hiệu: tên-quan-hệ.tên-thuộc-tính

1 Sài Gòn

3 Đà Nẵng

EE4509, EE6133 – HK2 2011/2012 TS. Đào Trung Kiên – ĐH Bách khoa Hà Nội

Biểu thức quan hệ và phép rename (đổi tên)

 Các phép toán quan hệ có thể được lồng nhau tạo thành biểu thức  VD:

 Πtên, giá(σcalo <=100(món-ăn) ∪ σgiá < 30(đồ-uống))  Πtác-giả.tên, bài-hát.tên(σid-tác-giả = bài-hát.id-tác-giả(σtên=“Trịnh Công Sơn”(tác-giả) × bài-hát))

 Kết quả các biểu thức quan hệ là các quan hệ không có tên, phép

toán rename cho phép đặt tên cho kết quả một biểu thức

 Ký hiệu: có 2 dạng

 ρtên-quan-hệ(E) đặt tên cho quan hệ kết quả của biểu thức E  ρtên-quan-hệ(tên các thuộc tính)(E) đặt tên cho quan hệ và các thuộc tính

kết quả của biểu thức E

 VD:

 ρđồ-uống-rẻ(σgiá < 30(đồ-uống))  ρnv-cn(tên-nhân-viên, tên-chi-nhánh)(Πnhân-viên.tên, chi-nhánh.tên

(σnhân-viên.id-chi-nhánh = chi-nhánh.id(nhân-viên × chi-nhánh)))

EE4509, EE6133 – HK2 2011/2012 TS. Đào Trung Kiên – ĐH Bách khoa Hà Nội

Set-intersection (giao) ∩

 Phép set-intersection nhận đầu vào là hai quan hệ tương thích với nhau và kết quả là quan hệ bao gồm những bộ giá trị có mặt ở đồng thời trong hai quan hệ

 Ký hiệu: r1 ∩ r2  VD:

 món-ăn-Tàu ∩ món-ăn-VN  khách-mua-máy-tính ∩ khách-mua-điện-thoại

 Phép set-intersection có thể được định nghĩa thông qua

phép trừ:

r1 ∩ r2 = r1 – (r1 – r2)

EE4509, EE6133 – HK2 2011/2012 TS. Đào Trung Kiên – ĐH Bách khoa Hà Nội

Natural-join (gộp) ⋈

 Trong việc khai thác CSDL, một câu hỏi rất hay gặp như sau: “Xuất ra danh sách các tác giả cùng với các bài hát được sáng tác”  sử dụng Cartesian- product và select:  σtác-giả.id-tác-giả = bài-hát.id-tác-giả(tác-giả × bài-hát)

 Phép natural-join nhận hai quan hệ và thực hiện Cartesian-product giữa

chúng, sau đó select những bộ giá trị dựa trên các thuộc tính chung và trả về tập kết quả

id-sp

sản phẩm

giá

id-hđ

id-sp

khách-hàng

Xoom

333

Jobs

 Ký hiệu: r1 ⋈ r2

Galaxy Tab

565

Obama

 VD:

iPhone

792

Bill



tác-giả ⋈ bài-hát

898

Paul

 hoá-đơn ⋈ sản-phẩm

⋈

id-hđ

id-sp

khách-hàng

sản phẩm

giá

333

Jobs

Xoom

565

Obama

Galaxy Tab

792

Bill

Xoom

898

Paul

Galaxy Tab

EE4509, EE6133 – HK2 2011/2012 TS. Đào Trung Kiên – ĐH Bách khoa Hà Nội

Division (chia) ÷

 Phép division dùng để giải quyết câu hỏi dạng: “Liệt kê các khách

hàng đã đăng ký tất cả các dịch vụ của hãng”

 Đáp án cảu câu hỏi này là kết quả của phép division:

đăng-ký(id-khách, id-dịch-vụ) ÷ khách-hàng(id-khách)

 Định nghĩa: Cho các quan hệ r(R) và s(S) với S ⊆ R. Kết quả của

phép division r ÷ s là một quan hệ trên R – S, trong đó một phần tử t thuộc r ÷ s khi và chỉ khi:

t ∈ ΠR – S(r)

  Với mọi ts ∈ S, có một tr ∈ R thoả mãn: ts[S] = tr[R] và tr[R – S] = t

 Định nghĩa thông qua các phép toán cơ bản:

r ÷ s = ΠR – S(r) – ΠR – S((ΠR – S(r) × s) – ΠR – S, S(r))

EE4509, EE6133 – HK2 2011/2012 TS. Đào Trung Kiên – ĐH Bách khoa Hà Nội

Assignment (gán) ←

 Phép assignment dùng để gán kết quả của một biểu thức

vào một biến (tương tự như trong các ngôn ngữ lập trình)

 Ký hiệu: r1 ← r2  VD:

 u ← ΠR – S(r) v = ΠR – S(u × s) – ΠR – S, S(r))

r ÷ s = u – v

 Phép assignment chỉ giúp thu gọn và đơn giản hoá biểu

thức

EE4509, EE6133 – HK2 2011/2012 TS. Đào Trung Kiên – ĐH Bách khoa Hà Nội

Sửa đổi dữ liệu

EE4509, EE6133 – HK2 2011/2012 TS. Đào Trung Kiên – ĐH Bách khoa Hà Nội

Giới thiệu

 Đại số quan hệ chỉ giúp trích xuất thông tin từ CSDL.

Phần này giúp tìm hiểu về việc thay đổi thông tin trong CSDL.

 Các phép toán bao gồm:

 Insert (thêm)  Delete (xoá)  Update (cập nhật)  View (tạo khung nhìn)

 Việc thay đổi thông tin đều dựa vào phép

assignment

EE4509, EE6133 – HK2 2011/2012 TS. Đào Trung Kiên – ĐH Bách khoa Hà Nội

Insert (thêm)

 Thêm dữ liệu mới vào một quan hệ được định nghĩa

thông qua phép hợp:

r ← r ∪ E

trong đó r là quan hệ được thay đổi, E là quan hệ

được thêm vào

EE4509, EE6133 – HK2 2011/2012 TS. Đào Trung Kiên – ĐH Bách khoa Hà Nội

Delete (xoá)

 Xoá dữ liệu mới từ một quan hệ được định nghĩa

thông qua phép trừ:

r ← r – E

trong đó r là quan hệ được thay đổi, E là quan hệ

được xoá bớt từ r

EE4509, EE6133 – HK2 2011/2012 TS. Đào Trung Kiên – ĐH Bách khoa Hà Nội

Update (cập nhật)

 Phép update được định nghĩa dựa trên phép chiếu: r ← Πf1,f2,...,fn(r) trong đó fi là thuộc tính thứ i của r nếu thuộc tính đó không muốn bị thay đổi, hoặc là giá trị cần cập nhật cho thuộc tính đó

 Phép update sẽ cập nhật toàn bộ các hàng của r  Nếu chỉ muốn cập nhật một số hàng nhất định, dùng

biểu thức như sau:

r ← Πf1,f2,...,fn (σP(r)) ∪ (r − σP(r))

EE4509, EE6133 – HK2 2011/2012 TS. Đào Trung Kiên – ĐH Bách khoa Hà Nội

View (tạo khung nhìn)

 Trong thực thế làm việc với CSDL, vì lý do bảo mật hoặc để thuận tiện thao tác, một phần CSDL có thể được ẩn đi với những người dùng nhất định

 Người dùng có thể không có thông tin tổng thể về sơ đồ của toàn bộ CSDL

 VD:

 một người dùng có thể chỉ biết danh sách nhân viên của công ty, mà không biết

được lương của từng người. Ta có thể tạo một quan hệ như sau:

view1 ← Πtên, tuổi(nhân-viên)

và chỉ để người dùng thao tác với view1

 Câu lệnh: create view v as E

trong đó v là tên view được tạo ra, và E là biểu thức quan hệ

 Phân biệt tạo view và phép gán: với phép gán, sau khi gán xong, nếu ta cập nhật các quan hệ trong biểu thức thì quan hệ được gán không thay đổi (còn với view thì có)

 Chú ý: một view cũng là một quan hệ, nên có thể dùng view trong biểu thức

để định nghĩa view khác

EE4509, EE6133 – HK2 2011/2012 TS. Đào Trung Kiên – ĐH Bách khoa Hà Nội

Bài tập

Dùng mô hình quan hệ để biểu diễn các CSDL sau: 1. Giáo viên, sinh viên, khoá học, môn học, lớp học 2. Công ty, nhân viên, dự án, chi nhánh 3. Thư viện, người đọc, sách 4. Cửa hàng, khách hàng, hàng, nhà phân phối Dùng đại số quan hệ để thực hiện các yêu cầu sau: 5. Tìm các học sinh lớp C có điểm trung bình lớn hơn 5 6. Tìm mã và tên những người đã mượn cuốn sách

“CSDL”

EE4509, EE6133 – HK2 2011/2012 TS. Đào Trung Kiên – ĐH Bách khoa Hà Nội