Bài giảng Cơ sở dữ liệu quan hệ

CHƯƠNG II CƠ SỞ DỮ LIỆU QUAN HỆ 2.1. Khái niệm về CSDL Xét hệ thống bán vé máy bay bằng máy tính. Dữ liệu lưu trữ trong máy tính gồm: Thông tin về hành khách (Họ và tên, Quốc tịch, Nước cư trú, Giới tính, Ngày sinh,...), Thông tin về chuyến bay (Ký hiệu chuyến bay, Giờ bay, Giờ đến, ...), Thông tin về đường bay (Tên đường bay, Nơi đổi má bay hoặc nghỉ tiếp nhiên liệu...),....Mọi thông tin về mối quan hệ này được biểu diễn trong máy thông qua việc đặt chỗ của khách hàng. Hãy biểu diễn dữ liệu đó đảm bảo để hành khách đi đúng chuyến bay của mình. Có 3 nông trại của các ông Thông, Xuân, Cúc. Mỗi nông trại có một số công trình kiến trúc: một căn nhà, một trại bò và một trại gà. Mỗi công trình kiến trúc là một nơi ở cho một số người hay súc vật. Dữ liệu trên được lưu trong máy theo một quy định nào đó để có thể khai thác được các thông tin cần thiết như để biết số bò cái trong trại bò ông Xuân, số người trong cả 3 nông trại ,....sẽ được gọi là CSDL 2.2. Các mô hình cơ sở dữ liệu 2.2.1. Mô hình đẳng cấp Các nông trại Thông Xuân Cúc Bò cái Con trai Vợ Ngựa Chồng Cần Trại bò Nhà ở Trại bò Nhà ở Trại bò Nhà ở Trại gà Bò cái Hình 2.2.1-1. Mô hình đẳng cấp Mô hình đẳng cấp được thiết kế theo dạng hình cây (Tree) nên đôi khi còn gọi là mô hình cây xem hình 2.2.1-1. Qua cây cấu trúc ta sẽ gặp một con bò cái trong chuồng bò của nông trại ông Xuân. Mỗi bậc cha mẹ trong cây đẳng cấp có thể có nhiều con, song mỗi con chỉ có một bậc cha mẹ. Khi dùng một cây như vậy, ta có thể dễ dàng thêm một con gà vào chuồng gà của ông Cúc, hoặc đếm số nhân khẩu trong nhà ông Xuân. Tuy vậy nếu ta muốn biết tất cả bò hoặc gà, hoặc cả hai,... thì phức tạp hơn 2.2.2. Mô hình mạng Thông Xuân Cúc Trại bò Nhà ở Trại bò Trại bò Nhà ở Nhà ở Trại gà Bò cái Bò cái Ngựa Con trai Vợ Chồng Cần Các nông trại Các cấu trúc Súc vật Con người Hình 2.2.2-1. Mô hình Mạng (network) Mô hình mạng – xem hình 2.2.2-1, tỏ ra mạnh hơn song lại phức tạp hơn. Một CSDL mạng là một tập hợp các mắt xích (nodes) và các mối nối (links), như thế một mắt xích bất kỳ có thể được nối với một mắt xích khác, và có thể nối nhiều lần. Các mối nối lập thành các xâu qua đó ta có thể nhanh chóng trả lời không những có bao nhiêu con bò trong chuồng bò của ông Xuân mà còn có thể trả lời ngay có bao nhiêu con bò trong CSDL. Tuy nhiên các tác vụ như nhập dữ liệu và xuất dữ liệu trong trường hợp này sẽ rất phức tạp. 2.2.3. Mô hình quan hệ Thông Nhà ở Thông Trại bò Xuân Nhà ở Xuân Trại bò Cúc Nhà ở Cúc Trại bò Cúc Trại gà Hình 2.2.3-1. Các nông trại Thông Trại bò Bò cái Xuân Trại bò Bò cái Xuân Trại bò Ngựa Cúc Nhà ở Hình 2.2.3-2. Súc vật Các dữ liệu của cùng cấp sẽ được tổ chức thành một bảng, các bảng sẽ được đặt quan hệ bới các khoá. Khi gọi đến một khoá của bảng mẹ, dữ liệu của các bảng con tương ứng với khoá đó sẽ được tham chiếu đến. Các cấu trúc Ví dụ khi ta cần xem Thông ở nông trại, tham chiếu đến bảng cấu trúc thì biết Thông có nhà ở và có trại bò, tham chiếu đến bảng súc vật thì biết Thông có trại bò và bò cái, ... Thông Nhà ở Con trai Xuân Nhà ở Vợ Cúc Nhà ở Chồng Cúc Trại bò Cần Hình 2.2.3-3. Gia súc và người 2.3. Kiến trúc một hệ cơ sở dữ liệu Một CSDL được phân thành các mức - Hình 2.3-1 Mức vật lý, là các tệp dữ liệu theo một cấu trúc nào đó và được lưu trên các thiết bị nhớ thứ cấp: đĩa từ, băng từ,... Mức khái niệm là sự biểu diễn trừu tượng của CSDL Vật lý, USER1 USEn VIEW1 VIEW21 VIEWn CSDL mức khái niệm (logic) CSDL mức vật lý USER2 ………………………… Hình 2.3-1 Các mức của CSDL Mức khung nhìn, là cách nhìn và là quan niệm sử dụng đối với CSDL mức khái niệm. Một CSDL đã được thiết kế, người ta thường quan tâm đến bộ khung (Structure) của CSDL đó. 2.4. Mô hình cơ sở dữ liệu quan hệ 2.4.1. Các khái niệm cơ bản Miền (domain): Là tập hợp các phần tử (giá trị) thoả mãn những tính chất nào đó. Ví dụ: Tập hợp các số tự nhiên là một miền, tập hợp các số nguyên là một miền, tập hợp các xâu ký tự tạo thành tên người có độ dài không quá 20 ký tự là một miền, tập hợp 2 số{0,1} cũng là một miền. Miền ký hiệu là D1, D2, .... Tích Đề – Các các miền D1, D2, ....,Dn là một miền ký hiệu là D D = D1xD2x....xDn. Các phần tử (giá trị) của nó là những bộ có độ dài n như sau: d = (d1,d2,...,dn) trong đó d1 Î D1, d2 Î D2,..., dn Î Dn Có thể viết: di Î Di với i =1, 2, ..., n Ví dụ: D1 = {0,1}, D2 = {a, b, c} thì D = D1xD2 là D = {(0,a), (0,b), (0,c), (1,a), (1,b), (1,c)} Quan hệ Quan hệ n ngôi là một tập con của tích Đề – Các D1xD2x....xDn. Khi đó mỗi bộ quan hệ có n thành phần (gọi là n cột), cột thứ i được gọi là có thuộc tính Ai. Định nghĩa 2.4.1-1 Gọi R = {A1, A2, ..., An} là tập hữu hạn các thuộc tính. Miền giá trị của thuộc tính Ai là dom(Ai). Quan hệ r - n ngôi trên tập thuộc tính R là tập con của tích Đề – Các: r Í dom(A1) ´ dom(A) ´, ...,´dom(An) Ví dụ Ta có bảng NHAN_VIEN sau: HO_VA_TEN NAM_SINH CQ_CT LUONG t1 Lê Văn Tám 1960 Viện CNTT 1200000 t2 Hoàng thị Thẹo 1970 Trường CĐ DLPĐ 1000000 t3 Ngô Quốc Công 1948 Trường ĐH DLPĐ 1250000 Hình 2.4.1-1. Quan hệ NHAN_VIEN Quan hệ NHAN_VIEN là quan hệ 4 ngôi có 4 cột (4 thuộc tính): A1 = HO_VA_TEN ; Họ và tên nhân viên A2 = NAM_SINH ; Năm sinh A3 = CQ_CT ; Cơ quan công tác A4 = LUONG ; Lương hằng tháng t1, t2, t3 là các bộ của quan hệ NHAN_VIEN. Còn các chuỗi Lê Văn Tám Hoàng thị Thẹo Ngô Quốc Công Là miền giá trị của thuộc tính A1 (HO_VA_TEN) 1960 1970 1948 Là miền giá trị của thuộc tính A2 (NAM_SINH) Viện CNTT Trường CĐ DLPĐ Trường ĐH DLPĐ Là miền giá trị của thuộc tính A3 (CQ_CT) 1200000 1000000 1250000 Là miền giá trị của thuộc tính A4 (LUONG) 2.4.2. Khái niệm về khoá Khoá (key) của một quan hệ r trên tập thuộc tính R = {A1, A2, ..., An} là một tập con K Í {A1, A2, ..., An} thoả mãn các tính chất: Với bất kỳ hai bộ ti, tj Î r vơi i ¹j đều tồn tại một thuộc tính A Î K sao cho ti(A) ¹ tj(A), nghĩa là không tồn tại hai bộ khác nhau mà có giá trị bằng nhau trên mọi thuộc tính thuộc tập con K. Điều kiện này có thể ký hiệu ti(K)¹tj(K) với " i¹j do vậy mỗi giá trị của K được xác định duy nhất. Ví dụ xét quan hệ: SINH_VIEN (SO_THE_SV, HO_VA_TEN, NGAY_SINH, LOP) SO_THE_SV HO_VA_TEN NGAY_SINH LOP 00001 Lê Hồng Ngọc 7/10/1968 A 00002 Võ Văn Hầu 12/12/1971 B 00003 Lê Hồng Ngọc 15/ 9/1969 A Hình 2.4.2-1. Quan hệ sinh viên Trong quan hệ trên K = {A1} = {SO_THE_SV} là tập khoá. K’ = {A1, A2} ={SO_THE_SV, HO_VA_TEN} cũng là tập khoá K” = {A1, A2, A4} = { SO_THE_SV, HO_VA_TEN, LOP} cũng là tập khoá. Dễ dàng chứng minh rằng mọi tập thuộc tính K’ chứa tập khoá K đều là tập khoá. Suy ra định nghĩa về tập khoá như sau: A1 A2 A3 1 2 3 3 2 1 1 3 2 3 3 3 3 3 1 1 3 3 Hình 2.4.2-1. Các thuộc tính và giá trị khóa Định nghĩa 2.4.2-1 Khoá của quan hệ r trên tập thuộc tính R = {A1,....,An} là tập con K Í R sao cho bất kỳ hai bộ ti, tj Î r, i¹j luôn luôn thoả mãn ti(K)¹ti(K) và bất kỳ tập con thực sự K’nào của K đều không có tính chất đó. Tập K như vậy được gọi là siêu khoá (Superkey) của quan hệ rtrên tập đặc tính R. Ví dụ: {A1,A2,A3} là một tập khoá vì không có bộ nào giống nhau. {A1,A2} không phải là một tập khoá vì có các bộ thứ 4 và thứ 5 giống nhau. {A1,A3} không phải là một tập khoá vì có các bộ thứ nhất và thứ 6 giống nhau. {A2,A3} không phải là một tập khoá vì có các bộ thứ 4 và thứ 6 giống nhau. {A1}, {A2},{A3} đều không phải là tập khoá vì có các bộ giống nhau. 2.4.3. Các phép tính trên CSDL quan hệ Các phép tính cơ bản mà nhờ đó một CSDL được thay đổi như là chèn (Insert), loại bỏ (Delete), thay thế (Change). Trong mô hình CSDL quan hệ các phép tính này tác động lên từng bộ ti của quan hể r lưu trữ trong máy. Việc tổ chức ra quan hệ và các bộ của nó có thể xem như biểu diễn tương ứng một – một qua các tệp (File) và các bản ghi (Record). 2.4.3.1. Phép tính chèn Phép chèn là thêm một bộ t = (d1, d2, ...,dn) mới vào quan hệ r{A1, A2,...,An} có dạng sau: r = rÈt Cú pháp: INSERT ( r ; A1 = d1, A2 = d2, ...., An = dn) Trong đó Ai, i =1,2,...n là các thuộc tính và di Î dom(Ai) Ví dụ: Thêm t4 = (1004, Tống Khánh Linh, 14/2/1974, B) vào quan hệ SINH_VIEN: INSERT( SINH_VIEN; SO_THE_SV= 1004, HO_VA_TEN = Tống Khánh Linh, NGAY_SINH = 14/2/1974, LOP = B) Trong trường hợp thứ tự sắp xếp của thuộc tính là cố định thì người ta chỉ viết đơn giản như sau: INSERT( r; d1, d2, ...., dn) Kết quả của phép tính chèn có thể gây ra các lỗi sau đây: Bộ thêm vào không theo đúng lược đồ quan hệ cho trước. Một số giá trị của một số thuộc tính nằm ngoài miền giá trị của thuộc tính đó. Giá trị khoá của bộ mới có thể trùng với giá trị đã có trong quan hệ. Do đó tuỳ theo từng lỗi, chúng ta cần tìm ra để khắc phục. 2.4.3.2. Phép xóa bộ (DEL) Phép loại bỏ là rút bỏ đi một bộ t = (d1, d2, ...,dn) khỏi quan hệ r{A1, A2,...,An} có dạng sau: r = r - t Cú pháp: DEL ( r ; A1 = d1, A2 = d2, ...., An = dn) Trong đó Ai, i =1,2,...n là các thuộc tính và di Î dom(Ai) Ví dụ: cần loại bỏ t4 = (1004, Tống Khánh Linh, 14/2/1974, B) khỏi quan hệ SINH_VIEN: DEL( SINH_VIEN; SO_THE_SV= 1004, HO_VA_TEN = Tống Khánh Linh, NGAY_SINH = 14/2/1974, LOP = B) Trong trường hợp thứ tự sắp xếp của thuộc tính là cố định thì người ta chỉ viết đơn giản như sau: DEL( r; d1, d2, ...., dn) Giá sử ta có tập khoá K là K = {B1, B2,...,Bm} Í R = {A1, A2, ..., An} trong đó m £ n và biết giá trị khoá của bộ cần xoá là B1 = b1, B2 = b2, ..., Bm = bm, khi đó chỉ cần viết DEL (r ; B1 = b1, B2 = b2, ..., Bm = bm) Ví dụ xét quan hệ: SINH_VIEN (SO_THE_SV, HO_VA_TEN, NGAY_SINH, LOP) SO_THE_SV HO_VA_TEN NGAY_SINH LOP 00001 Lê Hồng Ngọc 7/10/1968 A 00002 Võ Văn Hầu 12/12/1971 B 00003 Lê Hồng Ngọc 15/ 9/1969 A Hình 2.4.3-1. Quan hệ SINH_VIEN Cần xoá hàng thứ 2 chẳng hạn, ta viết DEL ( SINH_VIEN ; SO_THE_SV = 00002) 2.4.3.3. Phép thay đổi (CH) Đôi khi người ta chỉ cần sửa đổi một vài giá trị của bộ nào đó trong qua hệ chứ không phải loại bỏ hay chèn (sẽ tốn thời gian) thì chỉ cần dùng phép tính thay đổi CH. Gọi C = {C1, ...,Ck} Í {A1, ..., An} là tập thuộc tính mà tại đó ta cần thay đổi C1 = c1, ..., Ck = ck. Khi đó phép thay đổi có dạng r = r\tÈt’ CH (r ; A1 = a1, ..., Am = an ; C1 = c1, ..., Ck = ck) Giá sử ta có tập khoá K là K = {B1, B2,...,Bm} Í R = {A1, A2, ..., An} trong đó m £ n và biết giá trị khoá của bộ cần xoá là B1 = b1, B2 = b2, ..., Bm = bm, khi đó chỉ cần viết CH (r ; B1 = b1, B2 = b2, ..., Bm = bm ; C1 = c1,..., Ck = ck) Ví dụ cần đổi Lê Hồng Ngọc thành Lê Hồng Hạnh ở hàng thứ 3 chẳng hạn, ta viết CH ( SINH_VIEN ; SO_THE_SV = 00003; HO_VA_TEN = Lê Hồng Hạnh) 2.5. Ngôn ngữ thao tác dữ liệu Đối tượng của ngôn ngữ thao tác dữ liệu quan hệ hay còn gọi là “Ngôn ngữ hỏi” (query langguage) thường lien hệ chặt chẽ với các phép toán chèn, loạ bỏ và sửa đổi các bộ quan hệ. Mặt khác các câu hỏi có thể xem trong trường hợp tổng quát là những hàm số áp dụng lên các quan hệ. Ngôn ngữ hỏi cho mô hình quan hệ được chia thành hai lớp: Ngôn ngữ đại số, trong đố câu hỏi được biểu diễn nhờ áp dụng các phép tính đặc biệt đối với quan hệ và Ngôn ngữ tính toán tân từ, trong đó câu hỏi được biểu diễn là một tập các bộ thoả mãn các tân từ xác định. Sẽ trình bày chi tiết đại số quan hệ như là cơ sở của ngôn ngữ bậc cao để thao tác trên quan hệ, và giới thiệu một số ngôn ngữ con dữ liệu phổ cập hiện nay. 2.5.1. Đại số quan hệ Gọi r là quan hệ trên tập thuộc tính R = {A1, ...,An}. Ta luôn giả thiết rằng quan hệ r là tập hữu hạn các bộ. Đối với các phép hợp ( ký hiệu È) phép giao (ký hiệu Ç), phép trừ (ký hiệu -) hai quan hệ tham gia phải là khả hợp 2.5.1.1. Phép hợp È Hợp của hai quan hệ r và s ký hiệu là rÈs là tập các bộ hợa thuộc r hoặc thuộc s hoặc thuộc cả r lẫn thuộc s: rÈs = { t : t Î r hoặc t Î s hoặc t Î r và t Î s} Ví dụ: r(A, B, C) s(A, B, C) rÈs(A, B, C) a1b1c1 a2b1c2 a2b2c1 a1b1c1 a2b2c2 a1b1c1 a2b1c2 a2b2c1 a1b1c1 a2b2c2 2.5.1.2. Phép giao Ç Hợp của hai quan hệ r và s ký hiệu là rÇs là tập các bộ phải vừa thuộc r phải vừa thuộc s rÇs = { t : t Î r và t Î s } Ví dụ: r(A, B, C) s(A, B, C) rÇs(A, B, C) a1b1c1 a2b1c2 a2b2c1 a1b1c1 a2b2c2 a1b1c1 2.5.1.3. Phép trừ - Hiệu của hai quan hệ r và s 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 và t Ï s } Ví dụ: r(A, B, C) s(A, B, C) r-s(A, B, C) a1b1c1 a2b1c2 a2b2c1 a1b1c1 a2b2c2 a2b1c2 a2b2c1 Chú ý: Dễ dàng chứng minh rằng rÇs = r - (r - s) 2.5.1.4. Tích Đề - Các Gọi r là quan hệ xác định trên tập thuộc tính {A1,...,An} và s là quan hệ xác định trên tập thuộc tính {B1,...,Bm}. Tích Đề - Các r´s là một tập có (n+m) bộ với n thành phần đầu là bộ của r và m thành phần sau là bộ của s r´s = { t : t có dạng (a1,...,an , b1,...,bm} Ví dụ: r(A, B, C) s(D, E, F) r´s (A, B, C) a1b1c1 a2b2c2 d1e1f d2e2f a1b1c1d1e1f a1b1c1d2e2f a2b2c2d1e1f a2b2c2d2e2f 2.5.1.5. Phép chiếu (Projection) Phép chiếu trên một quan hệ thực chất là giữ lại một số thuộc tính, còn các thuộc tính khác loại bỏ đi. Giả sử r là quan hệ n ngôi trên tập thuộc tính R = {A1,...,An} và giả sử t là một bộ của r, AÍR. Ký hiệu t[A] là giá trị của bộ t tại thuộc tính A. Như vậy nếu X = {B1,...,Bm} thì t[X]=(t[B1],t[B2],...,t[Bm]. Gọi X là một tập con của tập thuộc tính R = {A1,...,An}. Phép chiếu P trên tập X của quan hệ r được định nghĩa như sau: PX(r) = {t[X] | t Î r} Ví dụ: R = {A,B,C,D} X = {A,B} Y = {A,D} Z = {B,D} r(A, B, C,D) PX(r) PY(r) PZ(r) a1b1c1d1 a1b1c1d2 a2b2c2d2 a2b2c3d3 a1b1 a2b2 a1c1 a2c2 a2c3 b1d1 b1d2 b2d2 b2d3 2.5.1.6. Phép chọn (Selection) Phép chọn dùng để tạo một tập con các bộ trong quan hệ r thoả mãn biểu thức F nào đó. Các phép toán trong biểu thức F là , = và ¹ cùng với các phép toán Logic là Ù (và), Ú (hoặc), Ø (phủ định) định nghĩa phép chọn s như sau: sF (r) = { t Î r | F(t) = .T.} (trong đó .T. = TRUE (đúng)) Ví dụ: r(A, B, C,D) sA = a1 (r) s(A = a1) Ù (D = d2) (r) a1b1c1d1 a1b1c1d2 a2b2c2d2 a2b2c3d3 a1b1c1d1 a1b1c1d2 a1b1c1d2 2.5.1.7. Phép kết nối (Join) Cho hai bộ d = (d1,..,dm) và e = (e1,..,em) phép xếp cạnh nhau ký hiệu là Ç được định nghĩa như sau d Ç e = (d1,...,dm,e1,...,em). Gọi q là một trong những phép toán , = và ¹. Phép kết nối của quan hệ r đối với thuộc tính A với quan hệ s đối với thuộc tính B được định nghĩa như sau: r wv s = { (t Ç u) | t Î r; u Î s và t[A]q s[B]} AqB Dĩ nhiên, ở đây cần giả thiết rằng mỗi gía trị của cột t[A] đều có thể so sánh (qua phép q) với mỗi giá trị của cột s[B]. Trong trường hợp phép q là “ = ” gọi là kết nối bằng. Trường hợp kết nối bằng tại thuộc tính cùng tên của hai quan hệ và một trong hai thuộc tính đó được loại bỏ qua phép chiếu, thì phép kết nối được gọi là phép “kết nối tự nhiên” và ký hiệu “ * ”. Khi đó phép kết nối tự nhiên của hai quan hệ r(ABC) và s(CDE) biếu diễn như sau: r(ABC)*s(CDE) = { t[ABCDE] | t[ABC] Î r, t[CDE] Î s} Ví dụ: r(ABC) s(CDE) r wv s =(ABCCDE) B >=C Nối tự nhiên r(ABC)*s(CDE)=(ABCDE) a1 1 1 a2 2 1 a2 2 2 1 d1 e1 2 d2 e2 3 d3 e3 a1 1 1 1 d1 e1 a2 2 1 1 d1 e1 a2 2 1 2 d2 e2 a2 2 2 1 d1 e1 a2 2 2 2 d2 e2 a1 1 1 d1 e1 a2 2 1 d1 e1 a1 2 2 d2 e2 2.5.1.8. Phép chia Gọi r là quan hệ n-ngôi và s là quan hệ m-ngôi (m>n và s #Æ). Phép chia r cho s viết r¸s là tập của tất cả (n-m)-bộ t sao cho với mọi bộ u Îs ta đều có t Çu Î r. Ví dụ: r(ABCD) s(CD) r¸s = (A B) a b c d a b e f a c e f e d c d e d e f a b d e c d e f a b e f 5.1.9. Các ví dụ về tìm kiếm bằng đại số quan hệ Ví dụ có ba quan hệ S(S#, SNAME, STATUS, CITY) là các hãng cung ứng S# SNAME STATUS CITY Thành Phố S1 S2 S3 S4 Cao sao vàng Điện tử Tân Bình Xi măng Hải Phòng Vietronic Đang hoạt động Đang hoạt động Đang hoạt động Đang hoạt động Hà nội Tân Bình Hải Phòng Hà nội P(P#, PNAME, COLOR, WEIGHT) các mặt hàng P# COLOR PNAME P1 P2 P3 P4 Đỏ Xanh Tím Vàng Lốp xe máy Đầu Vedeo Xi măng Tivi SP(S#, P#, PNAME, QTY) các mặt hàng đã cung cấp S# P# WEIGH S1 S2 S2 S1 S3 P1 P2 P3 P4 P2 100000 120000 456000 3200 4000 Giả sử cần tìm số hiệu của các hãng đã đã cung ứng mặt hàng P2 chẳng hạn. Trước hết dùng phép chọn s(P# = ‘P2’)(SP) để chọn trong quan hệ SP các bộ có P# = P2. Sẽ được các bộ SP S# P# WEIGHT = Số lượng S2 S3 P2 P2 120000 4000 Sau đó chiếu các bộ này lên X = {S#} sẽ được các số hiệu S2 và S3 PX(s(P# = ‘P2’)(SP)) = (S2, S3) Tương tự tìm số hiệu của những hãng đã cung ứng ít nhất một mặt hàng màu xanh. Có hai cách: a/ Trước hết làm phếp kết nối tự nhiên P*SP của P(P#, PNAME, COLOR, WEIGHT) các mặt hàng P# = Mã mặt hàng COLOR = Màu PNAME = Tên hàng P1 P2 P3 P4 Đỏ Xanh Tím Vàng Lốp xe máy Đầu Vedeo Xi măng Tivi Và của SP(S#, P#, PNAME, QTY) các mặt hàng đã cung cấp S# P# WEIGHT = Số lượng S1 S2 S2 S1 S3 P1 P2 P3 P4 P2 100000 120000 456000 3200 4000 Ta được P*SP P# = Mã mặt hàng COLOR = Màu PNAME = Tên hàng S# WEIGHT = Số lượng P1 P2 P3 P4 P2 Đỏ Xanh Tím Vàng Xanh Lốp xe máy Đầu Vedeo Xi măng Tivi Đầu Vedeo S1 S2 S2 S1 S3 100000 120000 456000 3200 4000 Bây giờ ta chọn các bộ có màu xanh s(Color = ‘xanh’ )(P*SP) sẽ được các bộ P# = Mã mặt hàng COLOR = Màu PNAME = Tên hàng S# WEIGHT = Số lượng P2 P2 Xanh Xanh Đầu Vedeo Đầu Vedeo S2 S3 120000 4000 Sau đó chiếu các bộ này lên X = {S#} PX(s(COLOR = ‘Xanh’)(P*SP)) sẽ được các số hiệu S2 và S3. Hoặc ta dùng: PX((s(COLOR = ‘Xanh’)(P))*SP) sẽ được các số hiệu S2 và S3 kết quả như trên. Nói chung các phép tính của đại số quan hệ là khá đơn giản có tính đầy đủ, không cần thủ tục. Tuy nhiên chủ yếu là làm cơ sở cho việc thiết lập các ngôn ngữ con dữ liệu bậc cao hơn. 2.5.2. Ngôn ngữ con dữ liệu DSL – ALPHA Các ký hiệu: {} là tập hợp : là “sao cho” hoặc “trong đó” 2.5.3. Biểu thức Alpha Định nghĩa 2.5.3-1. Biểu thức Alpha được ký hiệu là { : P} trong đó Ti i = 1,...,n là tên của các thuộc tính và P là biểu thức điều kiện. Biểu thức nhằm xác định quan hệ của những bộ (n1,..., nn ), n1Î dom(Ti) i=1,...,n sao cho bộ đó thoả mãn điều kiện P. Danh sách gọi là danh sách đích. P còn gọi là biểu thức đánh giá. Các phép tính dùng trong P gồm: , = và ¹ cùng với các phép toán Logic là and (và), or (hoặc), not (phủ định). Miền làm việc là miền liên lạc giữa người sử dụng và Database (CSDL). Giả thiết trong ngôn ngữ DSL_ALPHA người sử dụng được dùng một số vùng làm việc tuỳ ý. Vùng làm việc sẽ ký hiệu là W Ví dụ câu lệnh tìm tất cả sinh viên sinh sau ngày 30/5/1979 GET W (HS_SV.SO_THE_SV, HS_SV.HO_VA_TEN, HS_SV.GIOI_TINH, HS_SV.NGAY_SINH, HS_SV.QUE_QUAN): HS_SV.NGAY_SINH > 30/5/1979 Thì câu lệnh trong DSL_ALPHA được viết như sau: {: HS_SV.NGAY_SINH > 30/5/1979} 2.6. LÝ THUYẾT THIẾT KẾ CƠ SỞ DỮ LIỆU QUAN HỆ 2.6.1. Khái niệm Khi thiết kế cơ sở dữ liệu , chúng ta cần phải chọn ra các lược đồ quan hệ . Tuy nhiên, việc chọn ra một lược đồ phù hợp và tốt không dễ chút nào. Trong quá trình thiết kế , đôi khi ta không tránh khỏi những sai sót làm nảy sinh một số vấn đề như : Dư thừa dữ liệu (Redundancy ) . Không nhất quán (Inconsistency ) . Dị thường khi thêm bộ (Insertion anomalies ) Dị thường khi xóa bộ (Deletion anomalies ) 2.6.2. Phụ thuộc hàm Định nghĩa 2.6.2-1 Cho R( U ) là một lược đồ quan hệ với U = { A1, ... , An} là tập thuộc tính . X và Y là tập con của U . Nói rằng X ® Y ( đọc là X xác định hàm cho Y hoặc Y phụ thuộc hàm vào X ) nếu r là một quan hệ xác định trên R(U) sao cho bất kỳ hai bộ s1,s2 Î r mà s1[X] = s2[X] thì s1[Y] = s2[Y] 2.6.2.1. Hệ tiên đề cho phụ thuộc hàm: Gọi F là tập tất cả các phụ thuộc hàm đối với lược đồ quan hệ R(U) và X ® Y là một phụ thuộc hàm , X,Y Í U . Gọi F+ là bao đóng ( Closure ) của F , tức là tập tất cả các phụ thuộc hàm được suy diễn logic từ F . Nếu F = F+ thì F là họ đầy đủ ( full family ) của các phụ thuộc hàm . Gọi R(U) là lược đồ quan hệ với U = { A1, ... , An} là tập các thuộc tính X , Y , Z ,W