Cấp bậc tác giả:

DATABASE

Lý thuyết Cơ sở Dữ liệu - Phần 3 (Ngôn ngữ đại số quan hệ)

Được viết bởi Võ Hoài Sơn ngày 13/08/2012 lúc 09:05 PM
Ngôn ngữ đại số quan hệ
  • 0
  • 5466

Lý thuyết Cơ sở Dữ liệu - Phần 3 (Ngôn ngữ đại số quan hệ)


Ngôn ngữ đại số quan hệ

I.    Các phép tính trên các lược đồ khả hợp

Hai quan hệ r và s được gọi là tương thích (khả hợp/giao/hiệu) nếu chúng cùng xác định trên một tập thuộc tính. Nói cách khác, lược đồ khả hợp/giao/hiệu là các lược đồ có cùng thuộc tính.

Đối với các phép toán hợp, giao, hiệu thì 2 quan hệ tham gia phải khả hợp.

Gọi   r là quan hệ trên tập thuộc tính R= { A, A, … , A}

          s là quan hệ trên tập thuộc tính R= { A, A, … , A}

Kết quả thực hiện phép tính giữa r và s là một quan hệ với tập các bộ gọi là t

          Ta có   t[A1]    : giá trị của các bộ tại thuộc tính A1 ; …v.v.

                        t2[A1]  : giá trị của bộ thứ 2 tại thuộc tính A1 ; …v.v.

1.   Phép hợp

Với r và s là 2 quan hệ khả hợp

r∪s = { t / tÎr hoặc tÎs }

Ví dụ:

r (A B C)                       s ( A B C)             è             rs =  (    A B             C)

      1 1 1                               2 2 2                                                 0 0 0

      2 2 2                               3 3 3                                                 1 1 1

      B F D                               0 0 0                                                 2 2 2

                                                1 1 1                                                 3 3 3

                                                                                                            B F D

2.   Phép giao

Với r và s là 2 quan hệ khả giao

r∩s = { t / tÎr và tÎs }

Ví dụ:

r (A B C)                       s ( A B C)             è             r∩s = ( A B C)

      1 1 1                               2 2 2                                                 1 1 1

      2 2 2                               3 3 3                                                 2 2 2

      B F D                               0 0 0                                                

                                                1 1 1                                                

                                                                                                           

3.   Phép hiệu

Với r và s là 2 quan hệ khả hiệu

r-s = { t / tÎr và tÏs }

Hệ quả:    r∩s = r-(r-s)

Ví dụ:

r (A B C)                       s ( A B C)             è             r-s = (   A B C)

      1 1 1                               2 2 2                                                 B F D

      2 2 2                               3 3 3                                                        

      B F D                               0 0 0                                                        

                                                1 1 1                                                        

II.   Các phép tính đặc biệt

Gọi   r là quan hệ trên lược đồ R = { A, A, … , A}

          s là quan hệ trên lược đồ S = { B, B, … , B}

                X là lược đồ con của R, kí hiệu: X⊆R

Kết quả thực hiện phép tính giữa r và s là một quan hệ với tập các bộ gọi là t

          Ta có   t[A1]    : giá trị của các bộ tại thuộc tính A1 ; …v.v.

                        t2[A1]  : giá trị của bộ thứ 2 tại thuộc tính A1 ; …v.v.

F là tập biểu thức điều kiện logic, vị từ logic mà t cần phải thoả mãn.

Mỗi biểu thức điều kiện có dạng AqB với:

A: thuộc tính

B: thuộc tính hoặc giá trị

q: các toán tử  > , < , = , ≥ , ≤ , <> hoặc ≠

Để kết hợp nhiều biểu thức điều kiện ta có các toán tử logic: and Ù , or Ú , not ⏋

1.   Phép chọn (cắt ngang)

sF(r) = { t / tÎr và F(t)=true }

Ví dụ:

R(A B C D E)         

      1 2 A B 5                

      6 7 C E 6                

      2 3 C B 4                

è     sB≥3ÙE>5 (r) =    A B C D              E                                         s(C='C'ÙB<5)ÚE=6 (r) =        A             B             C             D            E          sA>2ÙB<5 (r) = Æ

                                          6 7 C E 6                                                       6 7 C E 6

                                                                                                                    2 3 C B 4

Cho biết những mẫu tin có B>3 hoặc E>5

è     sB>3ÚE>5 (r)                 

2.   Phép chiếu (cắt dọc)

PX(r) =  { t(X) / tÎr }

Chú ý: sau khi chiếu, nếu có bộ trùng lặp thì ta chỉ để lại 1 bộ trong số các bộ trùng lặp đó

Ví dụ:

R(A B C D E)        S (A K L)

      1 2 A B 5                 1 2 B

      6 7 C E 6                 1 3 F

      2 3 C B 4                 2 2 B

è    PC (r) = C                  PCD (r) = C D            PA(r) - PA(s) =   A -  A = A

                            A                                       A B                                               1     1     6

                            C                                       C E                                               6     2

                                                                      C B                                               2  

Cho biết thông tin của A trong mẫu tin có D='B' và E≥5

è     PA ( sD='B'ÙE≥5 (r) )

Cho biết thông tin của CD trong các mẫu tin có A=1 hoặc E=4

è     PCD ( sA=1ÚE=4 (r) )

Cho biết thông tin của B trong các mẫu tin thoả mãn (A>1 và B=C) hoặc E>5

è     PB ( s(A>1ÙB=C)ÚE>5 (r) )

3.   Phép tích đề các

r×s = { (t,u) / tÎr và uÎs }

Ví dụ:

R(A B C D E)        S (A K L)                         è                    r × s =  (    A B C D    E A         K             L)

      1 2 A B 5                 1 2 B                                                                       1 2 A B 5 1 2 B

      6 7 C E 6                 1 3 F                                                                       6 7 C E 6 1 2 B

      2 3 C B 4                 2 2 B                                                                       2 3 C B 4 1 2 B

                                                                                                                            1 2 A B 5 1 3 F

                                                                                                                            6 7 C E 6 1 3 F

                                                                                                                            2 3 C B 4 1 3             F

                                                                                                                            1 2 A B 5 2 2 B

                                                                                                                            6 7 C E 6 2 2 B

                                                                                                                            2 3 C B 4 2 2 B

4.   Phép kết nối

Quan hệ r của lược đồ R kết nối với quan hệ s của lược đồ S qua điều kiện AqB là:

r⋈s = {(t,u) / tÎr , uÎs và t[A]qu[B]=true}

   AqB

Nếu q là phép so sánh bằng thì ta có phép kết nối bằng. Nếu kết nối bằng tại các thuộc tính cùng tên của 2 quan hệ và 1 trong 2 thuộc tính đó được loại bỏ qua phép chiếu thì phép kết nối đó gọi là kết nối tự nhiên. Kí hiệu là r*s

Ghi chú: Phép kết nối tương tự phép tích đề các, nhưng có thêm điều kiện để lọc. Ta có thể thấy
r⋈s      
ó   sAqB(r×s) 
 
AqB

Ví dụ:

R(A B C D E)        S (A K L)

      1 2 A B 5                 1 2 B

      6 7 C E 6                 1 3 F

      2 3 C B 4                 2 2 B

è     r⋈s =  A B C D    E A K             L           r⋈s =    A B C D                    E         A K L r*s =  A B   C             D            E             K          L

           K>A       1 2 A B 5 1 2 B             A=A       1 2 A B 5 1 2 B                                 1 2 A B 5 2 B

                        1 2 A B 5 1 3 F                           1 2 A B 5 1 3 F                                 1 2 A B 5 3 F

                        2 3 C B 4 1 3             F                   2 3 C B 4 2 2                 B                 2 3 C B 4 2 B

Cho biết thông tin của A B C K L trong các mẫu tin thoả K>2          

è     PABCKLsK>2(r⋈s) )

                                                         A=A


5.   Phép chia

Cho 2 quan hệ           r/u={A1, A2, …, Ai, Ai+1, …, An}                

                                        s/v={Ai+1, …, An}

                                        u & v lần lượt là tập thuộc tính của r & s, v⊆u

Giả sử s≠Æ ; phép chia quan hệ r cho quan hệ s kí hiệu là r÷s, được kết quả là 1 quan hệ xác định trên tập thuộc tính (u-v) và được biểu diễn dưới hình thức như sau:

r÷s = {t / "uΠ   , (t,u)Îr}

Để tìm quan hệ r÷s ta thực hiện các bước sau:

b1: Tính T1 = PA1,…,Ai(r)

b2: Tính T2 = T1×s

b3: Tính T3 = T2 – r

b4: Tính T4 = PA1,…,Ai(T3)

b5: r÷s = T1–T4

Ví dụ:

r(A    B C             D)    s(     C             D)

    a  b c  d                   c  d

    a  b e  f                    e  f

    e  d c  d

    b c  c  d

    e  d e  f

è              

b1:

T1 = PA,B(r) = (   A       B)

                                a  b

                                e  d

                                b c

b2:

T2 = T1×s = (    A B C   D)

                            a  b c  d

                            a  b e  f

                            e  d c  d

                            e  d e  f

                            b c  c  d

                            b c  e  f

b3:

T3 = T2–r = (    A B C   D)

                            b c  e  f

b4:

T4 = PA,B(T3) =  (   A   B)

                                    b c

b5:

r÷s = T1-T4 = (    A       B)

                                a  b

                                e  d


Xem tiếp: Phần 4 (...Đang viết)

Nguồn bài viết: Sưu tầm

BÌNH LUẬN BÀI VIẾT

Bài viết mới nhất

LIKE BOX

Bài viết được xem nhiều nhất

HỌC HTML