Giáo trình

Giáo trình Cơ Sở Dữ Liệu

Science and Technology

Mô hình dữ liệu quan hệ - Các khái niệm cơ bản

Tác giả: unknown

Các khái niệm và các phép toán về tập hợp

  • Tập hợp là khái niệm đầu tiên của toán học, không định nghĩa. Ví dụ: Tập hợp các số nguyên; Tập hợp các sinh viên trong một lớp; Tập hợp các nghiệm của một phương trình..
  • Tập hợp được tạo thành từ các phần tử của nó, phần tử cũng là một khái niệm không định nghĩa. Người ta thường dùng các chữ cái viết hoa để kí hiệu cho tập hợp, chữ cái viết thường để chỉ một phần tử của tập hợp.

Các phép toán về tập hợp.

Cho hai tập hợp A và B, khi đó ta có các phép toán trên hai tập hợp như sau:

Phép giao: Giao của hai tập hợp A và B là một tập hợp, ký hiệu AB size 12{A intersection B} {}gồm những phần tử vừa thuộc A vừa thuộc B

A B = x x A x B size 12{A intersection B= left lbrace x \lline x in A` `"và"```x in B right rbrace } {}

Phép hội: Hội của hai tập hợp A và B là một tập hợp, ký hiệu AB size 12{A union B} {} gồm những phần tử thuộc A hay thuộc B.

A B = x x A x B size 12{A union B= left lbrace x \lline x in A`" và"``x in B right rbrace } {}

Phép hiệu: Hiệu của hai tập hợp A và B là một tập hợp, ký hiệu A \ B, gồm những phần tử thuộc A và không thuộc B

A = x x A x B size 12{A\B= left lbrace x \lline x in A`" và"`x notin B right rbrace } {}

Ví dụ

A=1,2,3,4,5 size 12{A= left lbrace 1,2,3,4,5 right rbrace } {}; B=2,4,6,8 size 12{B= left lbrace 2,4,6,8 right rbrace } {}

AB=1,2,3,4,5,6,8 size 12{A union B= left lbrace 1,2,3,4,5,6,8 right rbrace } {}; AB=2,4 size 12{A intersection B= left lbrace 2,4 right rbrace } {}; A=1,3,5 size 12{A\B= left lbrace 1,3,5 right rbrace } {}

Phép tích đề các: Tích đề các của hai tập A và B là một tập hợp, ký hiệu AxB, được định nghĩa như sau:

A × B = ( x , y ) x A y B size 12{A times B= left lbrace \( x,y \) \lline x in A`" và"`y in B right rbrace } {}

Ví dụ: A=1,2,3 size 12{A= left lbrace 1,2,3 right rbrace } {}; B=a,b size 12{B= left lbrace a,b right rbrace } {}

A × B = ( 1, a ) , ( 1, b ) , ( 2, a ) , ( 2, b ) , ( 3, a ) , ( 3, b ) size 12{A times B= left lbrace \( 1,a \) , \( 1,b \) , \( 2,a \) , \( 2,b \) , \( 3,a \) , \( 3,b \) right rbrace } {}

Ví dụ : A=1,2,3 size 12{A= left lbrace 1,2,3 right rbrace } {}; B=a,b size 12{B= left lbrace a,b right rbrace } {}; C=α,β size 12{C= left lbrace α,β right rbrace } {} lúc đó:

A × B × C = ( 1, a , α ) , ( 1, b , β ) , ( 2, a , α ) , ( 2, b , β ) , ( 3, a , α ) , ( 3, b , β ) size 12{A times B times C= left lbrace \( 1,a,α \) , \( 1,b,β \) , \( 2,a,α \) , \( 2,b,β \) , \( 3,a,α \) , \( 3,b,β \) right rbrace } {}

Mô hình dữ liệu quan hệ và các khái niệm cơ bản

Định nghĩa mô hình dữ liệu quan hệ

Mở đầu

Mô hình dữ liệu quan hệ là một mô hình được sử dụng rộng rãi trong đời sống xã hội của mọi tổ chức, cơ quan, xí nghiệp, doanh nghiệp, nơi nào cần quản lý và xử lý thông tin.Ta xét một vài ví dụ minh hoạ

Ví dụ 1: Xét hồ sơ cán bộ của 1 cơ quan

TT Mã Số Tên Năm Sinh TĐộ Quê GT Lương
1 01 Huy 1945 Đại Học T.Bình Nam 3000000
2 02 Hoàng 1965 Cao Học H.Nội Nam 5000000
3 03 Minh 1970 Trung Học H.Nội Nữ 2000000

Ví dụ 2: Xét sổ theo dõi khách của một khách sạn

MK Đến Đi MãP Số người Tiền
101 1/10/98 5/10/98 301 2 40000
102 5/10/98 20/11/98 302 2 20000

Trong các vấn đề trên tuy quản lý các mảng thông tin khác nhau nhưng cả 2 đều có chung một đặc thù là dữ liệu để mô tả dưới dạng bảng, mỗi bảng có một dòng đầu tiên gọi là dòng thuộc tính. Mỗi thuộc tính có một miền giá trị của nó

Vi dụ3 :

  • Các thuộc tính là (MK, Đến, Đi......)
  • Miền giá trị của thuộc tính năm sinh là: 1900....1986
  • Trong mỗi ví dụ ở trên mỗi bảng đều có một số phần tử như bản hồ sơ nhân sự có 3 phần tử, bảng theo dõi khách sạn có hai phần tử, mỗi 1 phần tử trong bảng gọi là một bộ(1 bản ghi).

Các dữ liệu được lưu dưới dạng bảng như vậy được gọi là mô hình CSDL quan hệ.

Sau đây chúng ta sẽ định nghĩa chính xác mô hình cơ sở dữ liệu quan hệ

Định nghĩa quan hệ dưới dạng hình thức

Trong mô hình cơ sở dữ liệu, mỗi quan hệ là một bảng.

Định nghĩa quan hệ dưới dạng toán học

Gọi U={A1, A2, ..., An}là tập hữu hạn các thuộc tính, mỗi thuộc tính Ai (i=1..n) có miền giá trị tương ứng là Dom(Ai). Người ta gọi r là quan hệ trên tập thuộc tính U nếu r là tập con của tích Đề-các của n miền Dom(Ai):

r Dom ( A1 ) × Dom ( A2 ) × . . . Dom ( An ) size 12{r subseteq ` ital "Dom" \( A1 \) times ital "Dom" \( A2 \) times "." "." "." ital "Dom" \( ital "An" \) } {}

Lược đồ quan hệ

Một lược đồ quan hệ (relational scheme) là một cặp có thứ tự:

R =< U , F > size 12{R"=<"U,F>} {}

Trong đó U là tập hữu han các thuộc tính của quan hệ và F là tập các ràng buộc của quan hệ (tập phụ thuộc hàm). Ở đây một ràng buộc trên tập các thuộc tính {A1, A2,...An} được hiểu là một tính chất trên tập tất cả các quan hệ xác đinh trên tập thuộc tính này.

Đại số quan hệ

Ngôn ngữ đại số quan hệ là cơ sở quan trọng của một ngôn ngữ bậc cao được sử dụng để thao tác trên các quan hệ. Ngôn ngữ này bao gồm hai nhóm phép toán:

  • Các phép toán tập hợp (phép giao, phép trừ, phép hợp, và tích Đề-các).
  • Các phép toán đặc biệt trên quan hệ(phép chọn, phép chiếu, phép kết nối và phép chia.

Định nghĩa: Hai quan hệ gọi là khả hợp nếu chúng có số thuộc tính bằng nhau và thuộc tính thứ i của quan hệ này có miền giá trị bằng miền giá trị thuộc tính thứ i của quan hệ kia.

Giả thiết r là quan hệ xác định trên tập thuộc tính U = {A1, A2, ..., AN}, với r là tập hữu hạn các bộ. Khi đó ta có các phép toán trên quan hệ r như sau:

Phép hợp:

Hợp của hai quan hệ r1 và r2 khả hợp, ký hiệu rs size 12{r union s} {}là tập tất cả các bộ thuộc r hoặc s hoặc thuộc cả hai quan hệ r và s.

Biểu diễn phép hợp có dạng:

r1r2=(ttr1 size 12{r1 union r2= \( t \lline t in r1``} {}hoặc tr2 size 12{t in r2} {} hoặc tr1 size 12{t in r1} {}tr2) size 12{t in r2 \) } {}

Ví dụ:

Phép giao:

Giao của hai quan hệ r1 và r2 khả hợp, ký hiệu r1r2 size 12{r1 intersection r2} {} là tập tất cả các bộ thuộc cả r1 và r2.

Biểu diễn hình thức:

r1 r2 = { t t r1 t r2 } size 12{r1 intersection r2= left lbrace t \lline t in r1``"và "` right none t in r2 left none right rbrace } {}

Ví dụ: Với r1 và r2 là hai quan hệ ở ví dụ trên, khi đó ta có:

Phép trừ:

Hiệu của hai quan hệ r1 và r2 ký hiệu r1- r2 là tập tất cả các bộ thuộc r không thuộc s.

Tích Đề-các:

Gọi r là quan hệ xác định trên tập thuộc tính {A1,A2,....,An} và s là quan hệ xác định trên tập thuộc tính {B1,B2,....,Bm}. Tích Đề_các của r và s là tập (n + m) bộ sao cho n thành phần đầu có dạng một bộ thuộc r và m thành phần sau có dạng của một bộ thuộc s.

r x s = {t | t có dạng (a1,a2,....,an,b1,b2,....,bm}. trong đó: (a1,a2,....,an) ∈ r và (b1,b2,....,bm) ∈ s}

Ví dụ:

Phép chiếu:

Gọi X là tập con của tập thuộc tính R = ( A1,A2,....,An). Phép chiếu trên tập X của quan hệ r, ký hiệu là πX (r) và được định nghĩa như sau:

π X ( r ) = { t X / t r } size 12{π rSub { size 8{X} } \( r \) = left lbrace ``t left [X right ] right none /t in r left none right rbrace } {}

- Ví dụ: R = { A, B, C, D}, X = { A, B}, Y = { A, C}

Phép chọn:

Phép chọn là phép tính để xây dựng một tập con các bộ của quan hệ đã cho thoả mãn biểu thức q xác định.

Có thể diễn đạt như sau: Cho r là một quan hệ trên lược đồ quan hệ, một phép chọn trên r thoả mãn điều kiện q là một tập hợp được định nghĩa và ký hiệu như sau.

σ q ( r ) = { t / t r q ( t ) = true } size 12{σ rSub { size 8{q} } \( r \) = left lbrace ````t right none /t in r` \lline " q" \( t \) size 8{``}="true" left none right rbrace } {}

Biểu thức q được diễn tả bằng một tổ hợp Boolean của các toán hạng, mỗi toán hạng là một phép so sánh đơn giản giữa 2 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 hằng, cho giá trị đúng sai đối với mỗi bộ đã kiểm tra.Các phép so sánh trong biểu thức q là <, =, >=, <=, >, ≠. Các phép toán logic là ¬ (không), ∨ (hoặc), ∧ (và).

R = { A, B, C, D}, q = {A = a1}

Phép nối tự nhiên:

Cho hai lược đồ quan hệ R1(U1), R2(U2). Gọi S = U1  U2 và U = U1  U2. Phép kết nối tự nhiên trên hai quan hệ r1, r2 là một quan hệ r trên U được ký hiệu và định nghĩa:

r 1 r 2 = { t ( U ) t 1 r 1 t 2 r 2 t ( U 1 ) = t 1 , t ( U 2 ) = t 2 } size 12{r rSub { size 8{1} } *r rSub { size 8{2} } = left lbrace `t \( U \) \lline exists `t rSub { size 8{1} } in r rSub { size 8{1} } `"và"`` exists `t rSub { size 8{2} } in r rSub { size 8{2} } " và "` right none t \( U rSub { size 8{1} } \) =`t rSub { size 8{1} } ,t \( U rSub { size 8{2} } \) =`t rSub { size 8{2} } left none right rbrace } {}

Ví dụ:

Phép trừ

Hiệu của hai quan hệ r và s khả hợp , 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 t s } size 12{r - s= lbrace `t/t in r`" và"```t notin " s"` rbrace } {}

Ví dụ: