Tài liệu Phụ thuộc logic trong cơ sở dữ liệu

i BỘ GIÁO DỤC VÀ ĐÀO TẠO TRƢỜNG ĐẠI HỌC CÔNG NGHỆ TP. HCM --------------------------- NGÔ VIỆT TRƯỜNG PHỤ THUỘC LOGIC TRONG CƠ SỞ DỮ LIỆU LUẬN VĂN THẠC SĨ Chuyên ngành: CÔNG NGHỆ THÔNG TIN Mã số ngành: 60480201 TP. HỒ CHÍ MINH, THÁNG 9 NĂM 2014 ii BỘ GIÁO DỤC VÀ ĐÀO TẠO TRƢỜNG ĐẠI HỌC CÔNG NGHỆ TP. HCM --------------------------- NGÔ VIỆT TRƯỜNG PHỤ THUỘC LOGIC TRONG CƠ SỞ DỮ LIỆU LUẬN VĂN THẠC SĨ Chuyên ngành: CÔNG NGHỆ THÔNG TIN Mã số ngành: 60480201 CÁN BỘ HƢỚNG DẪN KHOA HỌC: PGS TSKH NGUYỄN XUÂN HUY TP. HỒ CHÍ MINH, THÁNG 9 NĂM 2014 i LỜI CAM ĐOAN Tôi xin cam đoan đây là công trình nghiên cứu của riêng tôi. Các số liệu, kết quả nêu trong Luận văn là trung thực và chưa từng được ai công bố trong bất kỳ công trình nào khác. Tôi xin cam đoan rằng mọi sự giúp đỡ cho việc thực hiện Luận văn này đã được cảm ơn và các thông tin trích dẫn trong Luận văn đã được chỉ rõ nguồn gốc. Học viên thực hiện Luận văn (Ký và ghi rõ họ tên) NGÔ VIỆT TRƢỜNG ii LỜI CẢM ƠN g h g g Th truyề h họ h gi h ọ g h h h i h i gi h i i os - ng d n è ời ns o ồng nghiệ h h ạt những ki n thức rất bổ ích cho tôi trong quá trình học t Khoa Công Nghệ h g i h g h i i ọc Nguyễn Xuân Huy, th h t sức t n tình trong quá trình hoàn thành lu h ng d n . n lý khoa họ - ờ g ại Học Công Nghệ Thành Ph Hồ Ch Mi h gi ạ h ạ ại họ ạo mọi iều kiện thu n l i tôi trong quá trình học t p và hoàn thành lu Toàn thể quý th hiệt tình gi ng dạy và truyề ạt những ki n thức bổ ích cho tôi trong su t khóa học vừa qua. Cu i cùng xin c ồng nghiệ gi n tất c nhữ g g ời h g gi h tôi trong su i quá trình học t p và th c hiện lu NGÔ VIỆT TRƢỜNG ạn bè và iii MỤC LỤC Danh mục các kí hiệu, các từ viết tắt Danh mục các hình minh họa Mở đầu ....................................................................................................................... 1 Chƣơng 1. Tổng quan về lý thuyết cơ sở dữ liệu quan hệ ..................................... 6 1.1 Các khái niệm cơ bản........................................................................................ 6 1.1.1 Thuộc tính ............................................................................................. 6 1.1.2 Quan hệ n ngôi ...................................................................................... 7 1.1.3 Bộ .......................................................................................................... 8 1.1.4 Lược đồ quan hệ.................................................................................... 9 1.1.5 Khóa của một quan hệ......................................................................... 10 1.2 Phụ thuộc hàm ................................................................................................ 12 1.2.1 Khái niệm phụ thuộc hàm ................................................................... 12 1.2.2 Định nghĩa ........................................................................................... 12 1.2.3 Hệ luật dẫn Armstrong ........................................................................ 13 1.2.4 Thuật toán tìm bao đóng của tập thuộc tính........................................ 15 1.2.5 Bài toán thành viên ............................................................................. 16 1.2.6 Phủ tối thiểu của một tập phụ thuộc hàm............................................ 16 1.3 Khóa ................................................................................................................ 17 1.3.1 Định nghĩa ........................................................................................... 17 1.3.2 Thuật toán tìm khóa ............................................................................ 18 1.4 Kết chương ...................................................................................................... 19 Chƣơng 2. Một số khái niệm cơ sở trong phụ thuộc Boole dƣơng ..................... 20 2.1 Các công thức Boole ....................................................................................... 20 2.2 Phụ thuộc Boole dương .................................................................................. 23 2.2.1 Công thức Boole dương ...................................................................... 23 2.2.2 Bảng chân lý của quan hệ ................................................................... 24 2.2.3 Phụ thuộc Boole dương ....................................................................... 25 iv 2.2.4 Một số tính chất của phụ thuộc Boole dương ..................................... 25 2.2.5 Định lý tương đương ........................................................................... 27 2.3 Bài toán suy dẫn cho lớp PTBD ..................................................................... 28 2.4 Biểu diễn PTBD dưới dạng hội suy dẫn ......................................................... 31 2.4.1 Công thức suy dẫn............................................................................... 31 2.4.2 Bài toán biểu diễn PTBD dưới dạng hội suy dẫn ............................... 32 2.4.3 Tập TR của PTBD ............................................................................... 37 2.4.4 Xây dựng tập PTBD từ quan hệ R cho trước ...................................... 40 2.5 Kết chương ...................................................................................................... 41 Chƣơng 3. Ứng dụng lớp phụ thuộc Boole dƣơng giải một số lớp bài toán ...... 42 3.1 Bài toán thành viên ......................................................................................... 42 3.1.1 Phương pháp chứng minh một công thức là hằng đúng ..................... 45 3.1.2 Chuẩn hóa dạng chuẩn hội (CNF) ...................................................... 47 3.1.3 Phương pháp chứng minh công thức suy dẫn bằng phép hợp giải ..... 48 3.2 Bài toán bao đóng ........................................................................................... 48 3.3 Một số thí dụ minh họa ................................................................................... 49 3.4 Môi trường xây dựng chương trình ................................................................ 51 3.4.1 Phần cài đặt chương trình ................................................................... 51 3.4.2 Dữ liệu áp dụng cho chương trình ...................................................... 51 3.5 Kết quả đạt được ............................................................................................. 52 3.9 Kết chương ...................................................................................................... 52 Kết luận và kiến nghị hƣớng phát triển ................................................................ 53 Phụ lục ...................................................................................................................... 54 Tài liệu tham khảo .................................................................................................. 61 v DANH MỤC CÁC KÝ HIỆU, CÁC TỪ VIẾT TẮT CSDL Cơ sở dữ liệu CTB Công thức Boole CTBD Công thức Boole dương CTSD Công thức suy dẫn HSD Hội suy dẫn I(U) Tập các công thức suy dẫn trên tập biến U L(U) Tập các CTB xây dựng trên tập các biến U P(U) Tập toàn bộ các công thức dương trên U PTBD Phụ thuộc Boole dương PTBDTQ Phụ thuộc Boole dương tổng quát PTH Phụ thuộc hàm R(U) Quan hệ R với tập thuộc tính U REL(U) Tập toàn thể các quan hệ trên tập thuộc tính U REL_p(U) Tập toàn thể các quan hệ có không quá p bộ trên tập thuộc tính U, p ≥ 1 SAT(F) Tập toàn thể các quan hệ trên U thỏa tập ràng buộc F SAT_p(F) Tập toàn thể các quan hệ có không quá p bộ trên U thỏa tập ràng buộc F, p ≥ 1 SubSet(U) Tập các tập con của U  Khi và chỉ khi  suy ra, kéo theo vi ├ suy dẫn theo quan hệ ╞ suy dẫn logic ├2 suy dẫn theo quan hệ có không quá 2 bộ vii DANH MỤC CÁC HÌNH MINH HOẠ Hình 1.1 Thể hiện của quan hệ khoa ...................................................................... 9 Hình 1.2 Thể hiện của quan hệ lophoc ................................................................... 9 Hình 2.1 Bảng chân lý Tf,Tg ................................................................................. 22 Hình 2.2 Bảng trị Vf,Vg ........................................................................................ 22 Hình 2.3 Bảng chân lý TG,Th ................................................................................ 23 Hình 2.4 Quan hệ R(A,B,C) ................................................................................. 24 Hình 2.5 Bảng chân lý TR ..................................................................................... 24 Hình 3.1 Các kí hiệu phép toán ............................................................................ 42 Hình phụ lục 1 Gọi thủ tục go1 ............................................................................ 54 Hình phụ lục 2 Gọi thủ tục go2 ............................................................................ 55 Hình phụ lục 3 Gọi thủ tục go3 ............................................................................ 55 Hình phụ lục 4 Gọi thủ tục go .............................................................................. 56 Hình phụ lục 5 Gọi tiếp thủ tục go ....................................................................... 56 Hình phụ lục 6 Gọi tiếp thủ tục go ....................................................................... 57 Hình phụ lục 7 Gọi tiếp thủ tục go ....................................................................... 57 Hình phụ lục 8 Gọi tiếp thủ tục go ....................................................................... 58 Hình phụ lục 9 Tính trị a + b ................................................................................ 58 Hình phụ lục 10 Tính trị a & b ............................................................................. 59 Hình phụ lục 11 Tính trị a  b ............................................................................. 59 Hình phụ lục 12 Tính trị a ^ b ............................................................................... 60 Hình phụ lục 13 Tính trị a  b ............................................................................ 60 1 MỞ ĐẦU Với sự phát triển ngày càng hiện đại của khoa học kĩ thuật trên thế giới, song bên cạnh đó là sự phát triển về xã hội con người, do mối liên quan giữa công nghệ và cuộc sống, mối quan hệ đó ngày càng đa dạng, phát triển với số lượng lớn và rộng vì thế việc xử lý khối lượng dữ liệu lớn đó luôn là vấn đề đáng được nghiên cứu để đáp ứng phù hợp với sự phát triển của các quan hệ trên, cũng nhằm giải quyết chính xác hơn, phù hợp hơn các giá trị thực tiển, mối liên kết ràng buộc của thực tiễn cuộc sống. Việc tổ chức lưu trữ, quản lý và khai thác dữ liệu ta có thể dùng nhiều mô hình tổ chức dữ liệu khác nhau từ những mô hình truyền thống như mô hình mạng, mô hình phân cấp, mô hình quan hệ đến các mô hình hiện đại, được dùng nhiều hiện nay như mô hình cơ sở dữ liệu phân tán, mô hình cơ sở dữ liệu hướng đối tượng … Trong các mô hình dữ liệu, việc nghiên cứu lý thuyết và ứng dụng của các ràng buộc dữ liệu hay còn gọi là các phụ thuộc dữ liệu là một yêu cầu cấp thiết đặt ra. Phụ thuộc dữ liệu đầu tiên được Codd [13] tác giả của mô hình dữ liệu quan hệ đặt nền móng từ những năm 1970 với khái niệm phụ thuộc hàm. Tiếp sau đó R. Fagin và Zaniolo đã đưa ra phụ thuộc đa trị vào năm 1976. Cùng với sự phát triển của lớp phụ thuộc hàm, một số phụ thuộc dữ liệu bậc cao cũng như hệ tiên đề cho lớp các phụ thuộc - tức là đặt nền móng cơ sở lý thuyết về phụ thuộc dữ liệu, cũng được giới thiệu sau đó như phụ thuộc đối ngẫu, phụ thuộc mạnh, phụ thuộc yếu do J. Demetrovics và Gy. Gyepesy đề xuất năm 1981, phụ thuộc Boole dương do Berman đề xuất năm 1985, 1987, phụ thuộc Boole dương tổng quát được Nguyễn Xuân Huy, Lê Thị Thanh [6] phát triển năm 1992, … Gần đây, trên cơ sở lớp phụ thuộc hàm là phụ thuộc dữ liệu truyền thống có một số công trình nghiên cứu của nhiều nhóm về các phụ thuộc dữ liệu mở rộng cho nhiều các loại dữ liệu khác nhau. Với dữ liệu xác định, năm 2004, Ilya và các đồng nghiệp đã nghiên cứu phụ thuộc hàm nhẹ (Soft Functional Dependencies – Soft FD) là phụ thuộc hàm mà giá trị của X xác định giá trị của Y với độ không chắc chắn 2 nhất định hay phụ thuộc hàm có điều kiện (Conditional functional dependencies CFDs) được Bohannon [8] cùng các đồng nghiệp đề xuất năm 2007 để làm sạch dữ liệu. Với dữ liệu mờ, phụ thuộc hàm đối sánh (Matching dependencies - MDs), phụ thuộc hàm độ đo (Metric Functional Dependencies - MFD) đã lần lượt được Fan nghiên cứu, đề xuất năm 2008,2009. Hay phụ thuộc tuần tự (Sequential dependencies - SD) được Golab và đồng nghiệp đưa ra để khái quát dữ liệu theo thứ tự và biểu diễn mối quan hệ giữa các thuộc tính có thứ tự. Gần đây, đầu năm 2011 nhóm nghiên cứu Song S. và Chen L. [12] đã đề xuất phụ thuộc sai khác (Differential Dependencies - DDs) để giải quyết một số vấn đề như đảm bảo tính toàn vẹn, tối ưu truy vấn tốt hơn so với phụ thuộc hàm. Lớp các PTH và hầu hết các phụ thuộc bậc cao phát triển sau đó như phụ thuộc đối ngẫu, phụ thuộc mạnh, phụ thuộc yếu, phụ thuộc hàm nhẹ, phụ thuộc hàm có điều kiện … đều dựa trên quan hệ đẳng thức khi so sánh các trị của các thuộc tính xuất hiện trong các bộ. Trong thực tế, ngoài so sánh theo đẳng thức còn tồn tại những loại hình so sánh khác. Ta xét một số thí dụ sau: 1. Trong CSDL quản lý giao dịch thẻ tín dụng, số thẻ giao dịch sẽ xác định vị trí giao dịch. Để xác định một giao dịch có gian lận hay không ta có thể kết hợp các điều kiện giữa số thẻ với vị trí để xác định thời gian giao dịch, thí dụ nếu cùng một thẻ tín dụng giao dịch ở hai vị trí cách nhau hơn 40km (ở hai thành phố khác nhau), thì thời gian truyền sai lệch phải lớn hơn 20 phút.Nếu hai giao dịch không thỏa điều kiện trên thì một trong hai phiên giao dịch đó là gian lận. Như vậy, ta thấy phụ thuộc [sothe (=0) vitri (≥40)]  [thoigian(≥20)] có ngữ nghĩa rộng hơn PTH sothe → vitri. 2. Trong số luận, độ cao của một số tự nhiên n, H(n) là tổng các chữ số của số đó, thí dụ, H(2006) = H(125) = 8. Nếu ta phân loại các số theo độ cao thì hai số khác nhau có thể thuộc cùng một lớp. Như vậy phụ thuộc H(N)→CLASS có ngữ nghĩa rộng hơn PTH N → CLASS. 3 Trong thực tế với một số cơ sở dữ liệu lớn, biến động, phân tán ở nhiều nơi, trên địa bàn rộng, phục vụ nhiều người dùng với nhiều ứng dụng khác nhau thì các yêu cầu như đồng nhất dữ liệu (theo khóa và theo trọng số thông tin ), xử lý các yêu cầu tra cứu thông tin với các điều kiện khác nhau một cách nhanh chóng, đảm bảo dữ liệu không bị mất mát trên đường truyền, tổ chức, thiết kế, quản lý dữ liệu sao cho việc lưu trữ tốn ít bộ nhớ nhất, khai thác hiệu quả và thời gian truyền dữ liệu được giảm tối đa… cũng luôn là yêu cầu cần thiết đặt ra. Một trong các giải pháp để thực hiện việc này là mở rộng khái niệm đối sánh các trị của các thuộc tính xuất hiện trong các bộ, tìm tập các phụ thuộc dữ liệu thu gọn tương đương với tập phụ thuộc dữ liệu ban đầu.. Đây cũng chính là mục đích và ý nghĩa của việc mở rộng khái niệm so sánh trong lớp các phụ thuộc dữ liệu như phụ thuộc Boole dương hay các phụ thuộc có bản chất là phụ thuộc Boole dương như phụ thuộc sai khác, phụ thuộc đối sánh được nghiên cứu sau này. Mục tiêu của luận văn là tìm hiểu về lý thuyết phụ thuộc dữ liệu và ứng dụng lý thuyết này trong một số ứng dụng. Đây là vấn đề nghiên cứu đã và đang được nhiều nhà khoa học quan tâm. 4 Mục đích nghiên cứu - Nghiên cứu và tìm hiểu các lớp phụ thuộc Boole dương trong đó tập trung chủ yếu việc vào tìm hiểu một số khái niệm, tính chất của lớp phụ thuộc Boole dương và một số khía cạnh ứng dụng của lớp phụ thuộc này. Phƣơng ph p nghiên cứu - Tìm hiểu các tài liệu và kết quả nghiên cứu có liên quan đến đề tài. Vận dụng chủ yếu các phương pháp và cấu trúc của toán học rời rạc kết hợp với việc phát triển lớp các phụ thuộc logic nhằm đảm bảo ngữ nghĩa của dữ liệu trong cơ sở dữ liệu theo hướng tiếp cận logic. Bố cục của luận văn Về cấu trúc, luận văn được trình bày trong 3 chương, phần mở đầu, phần kết luận, phần mục lục, phần phụ lục, tài liệu tham khảo. Các nội dung của luận văn trình bày theo cấu trúc như sau: C ơn 1. ổn qu n về lý t uy t cơ sở dữ l ệu qu n ệ Trình bày một số khái niệm chung về mô hình quan hệ và lớp phụ thuộc đầu tiên của phụ thuộc logic là phụ thuộc hàm. C ơn 2. Một số k n ệm cơ sở tron p ụ t uộc Bool d ơn Trình bày một số khái niệm về phụ thuộc Bool dương và các vấn đề liên quan đến việc tìm bao đóng, bài toán thành viên của lớp phụ thuộc Boole dương. Biểu diễn phụ thuộc Boole dương dưới dạng hội các công thức suy dẫn và thuật toán xây dựng xây dựng tập PTBD thỏa mãn quan hệ R cho trước cũng được trình bày trong chương này. C ơn 3. Ứn dụn p ụ t uộc Bool d ơn ả một số lớp bà to n Trong chương trình bày quy trình chuẩn hóa một công thức về dạng chuẩn hội (CNF), phương pháp chứng minh một công thức bằng phép hợp giải, phương pháp chứng minh một công thức là hằng đúng cũng như thuật toán tìm phủ không 5 dư của một công thức. Từ đó, vận dụng các kỹ thuật này vào việc giải một số bài toán thông qua các ví dụ minh họa. Những kết quả trong luận văn là bước đầu tìm hiểu về lý thuyết các phụ thuộc logic trong cơ sở dữ liệu. Kết hợp với một số thuật toán có thể xây dựng các ứng dụng phục vụ trong một số lĩnh vực chẳng hạn như cơ sở dữ liệu. Do điều kiện về thời gian và trình độ còn hạn chế, những vấn đề trình bày trong luận văn không tránh khỏi những thiếu sót. Tác giả rất mong được sự thông cảm và góp ý của các nhà khoa học, đồng nghiệp và bạn bè để luận văn được hoàn thiện tốt hơn. 6 Chƣơng 1 TỔNG QUAN VỀ LÝ THUYẾT CƠ SỞ DỮ LIỆU QUAN HỆ Lý thuyết về các phụ thuộc dữ liệu đóng vai trò quan trọng trong việc mô tả thế giới thực, phản ánh ngữ nghĩa dữ liệu của cơ sở dữ liệu. Trong quản lý các cơ sở dữ liệu (CSDL), phụ thuộc dữ liệu được hiểu là những mệnh đề mô tả các ràng buộc mà dữ liệu phải đáp ứng trong thực tế. Nhờ có những mô tả phụ thuộc này mà hệ quản trị cơ sở dữ liệu có thể quản lý tốt được chất lượng dữ liệu. Phụ thuộc dữ liệu được Codd [13] tác giả của mô hình dữ liệu quan hệ đặt nền móng từ những năm 70 với khái niệm phụ thuộc hàm. Sau đó một loạt tác giả khác tiếp tục phát triển các dạng phụ thuộc bậc cao, phụ thuộc mờ cũng như xây dựng các hệ tiên đề cho các lớp phụ thuộc - tức là đặt cơ sở lý thuyết về phụ thuộc dữ liệu. Một điều khá tự nhiên là ngay từ những ngày đầu phát triển lý thuyết thiết kế cơ sở dữ liệu, logic đã được chọn như một ngôn ngữ hữu hiệu để đặc tả phụ thuộc dữ liệu, do đó trong số các loại hình phụ thuộc dữ liệu rất đa dạng được đề xuất và phát triển sau này, các phụ thuộc logic luôn luôn là trọng tâm chú ý của các nhóm nghiên cứu. Chương này sẽ trình bày một cách tổng quan quá trình phát triển của lớp phụ thuộc logic đầu tiên là phụ thuộc hàm. Phần đầu tiên của chương trình bày một số khái niệm cơ bản của lý thuyết cơ sở dữ liệu quan hệ, khái niệm về phụ thuộc hàm và lược đồ quan hệ. 1.1 Các khái niệm cơ bản 1.1.1 Thuộc tính Thuộc tính (attribute) là một tính chất riêng biệt của một đối tượng cần được lưu trữ trong CSDL để phục vụ cho việc khai thác dữ liệu về đối tượng. 7 Thí dụ 1.1 • Đối tượng LOPHOC có các thuộc tính mã lớp, tên lớp, khóa, số học viên. • Đối tượng SINHVIEN có các thuộc tính mã sinh viên, họ tên, ngày sinh, quê quán. Các thuộc tính được đặc trưng bởi một tên thuộc tính, kiểu giá trị (data type) và miền giá trị (domain). Trong các ứng dụng thực tế, người phân tích – thiết kế thường đặt tên thuộc tính một cách gợi nhớ, tuy nhiên không nên đặt tên quá dài (vì làm cho việc viết câu lệnh truy vấn vất vả hơn) nhưng cũng không nên quá ngắn (vì không thể hiện được ngữ nghĩa một cách rõ ràng). Thí dụ 1.2 Nếu có hai đối tượng HỌCVIEN và GIAOVIEN đều có thuộc tính tên thì nên đặt tên một cách rõ ràng là Tên_học_viên và Tên_giáo _viên vì chúng mang ngữ nghĩa hoàn toàn khác nhau. Mỗi một thuộc tính đều phải thuộc một kiểu dữ liệu. Kiểu dữ liệu có thể là vô hướng - là các kiểu dữ liệu cơ bản như chuỗi, số, logic, ngày tháng… hoặc các kiểu có cấu trúc được định nghĩa dựa trên các kiểu dữ liệu đã có sẵn. Mỗi một thuộc tính có thể chỉ chọn lấy những giá trị trong một tập hợp con của kiểu dữ liệu. Tập hợp các giá trị mà một thuộc tính A có thể nhận được gọi là miền giá trị của thuộc tính A, thường được ký hiệu là MGT(A) hoặc Dom(A). Thí dụ 1.3 Điểm của sinh viên là một số, nhưng luôn nằm trong đoạn từ 0 đến 10. Với kiểu dữ liệu cấu trúc thì miền giá trị chính là tích đề các (hoặc tập con của tích đề các) của các miền giá trị thành phần. 1.1.2 Quan hệ n ngôi Một quan hệ R có n ngôi được định nghĩa trên tập các thuộc tính U = {A1, A2,...An} và kèm theo nó là một tân từ, để xác định mối quan hệ giữa các thuộc tính Ai , và được ký hiệu là R(A1, A2,...An ). Tập thuộc tính của quan hệ R còn được ký hiệu là R+. 8 Với Ai là một thuộc tính có miền giá trị là MGT(Ai), như vậy R(A1, A2,...An ) là tập con của tích đề các: MGT(A1)x MGT(A2)x…x MGT(An) Quan hệ còn được gọi là bảng (table). Thí dụ 1.4 KHOA(Mã_khoa, Tên_khoa) là một quan hệ 2 ngôi với tân từ : “Mỗi khoa có một mã khoa duy nhấ SINHVIEN ể phân biệt v i các khoa khác, có một tên gọi”. (Mã_sinh_viên, Tên_sinh_viên, Ngày_sinh, Quê_quán, Khoa) là một quan hệ 5 ngôi với tân từ : “Mỗi sinh viên có một mã sinh viên duy nhất ể phân biệt v i các sinh viên khác, có họ ê quê quán và học tại mộ h g g h g i h ờng ”. 1.1.3 Bộ Một bộ (tuple) giá trị là các thông tin của một đối tượng thuộc quan hệ. Bộ giá trị cũng thường được gọi là một mẫu tin hay bản ghi (record), dòng của bảng (row). Một bộ q là một vecto gồm n thành phần thuộc tập hợp con của tích đề các miền giá trị của các thuộc tính và thỏa mãn tân từ đã cho của quan hệ. Thí dụ 1.5 Các bộ giá trị dựa trên các thuộc tính của quan hệ SINHVIEN: q1 = (SV001, Trần Văn Mạnh, 10/10/1980, Lâm Đồng, CTK27) q2 = (SV002, Nguyễn Thị Hoa Huệ, 25/11/1985, Khánh Hòa, MTK27) q3 = (SV003, Tăng Thanh Hà, 11/11/1982, Tp. Hồ Chí Minh, NVK27) Để lấy thành phần Ai – là giá trị thuộc tính Ai của một bộ giá trị q, ký hiệu q.Ai. Đây được gọi là phép chi u một bộ lên thuộc tính Ai Thí dụ 1.6 q1.Tên_sinh_viên = “Trần Văn Mạnh” q2.Khoa= “MTK27” 9 1.1.4 Lƣợc đồ quan hệ Lược đồ quan hệ (Relation schema) là sự trừu tượng hóa của quan hệ, một sự trừu tượng hóa ở mức cấu trúc của một bảng hai chiều. Khi nói đến lược đồ quan hệ tức là đề cập tới cấu trúc tổng quát của một quan hệ; khi nói đến một quan hệ thì hiểu rằng đó là một bảng có cấu trúc cụ thể trên một lược đồ quan hệ với các bộ giá trị của nó. Lược đồ cơ sở dữ liệu là tập hợp các lược đồ quan hệ con {Ri}, ký hiệu là ζ. Thể hiện (hay tình trạng) của quan hệ R, ký hiệu là TR, là tập hợp các bộ giá trị của quan hệ R vào một thời điểm. Như vậy, tại những thời điểm khác nhau thì quan hệ có những thể hiện khác nhau. Thể hiện của các lược đồ quan hệ con TRi gọi là tình trạng của lược đồ CSDL ζ Thí dụ 1.7 Thể hiện của quan hệ KHOA và LOPHOC Mã khoa Tên khoa Ngày thành lập CNTT Công nghệ thông tin 10/10/1994 TH Toán học 20/10/1976 VL Vật lý 20/10/1976 HH Hóa học 20/10/1976 Bảng 1.1 Thể hiện của quan hệ KHOA Mã lớp Tên lớp Số học viên Mã khoa CTK27 Công nghệ thông tin K27 75 CNTT HHK18 Hóa học K18 95 HH THK20 Toán học K20 120 TH Bảng 1.2 Thể hiện của quan hệ LOPHOC 10 1.1.5 Khóa của một quan hệ Quan hệ R định nghĩa trên tập các thuộc tính U = {A1, A2,..., An} Khi đó K ⊆ U là khóa của quan hệ R nếu thoả: (i) K xác định được giá trị của Aj , với mọi j = 1,2,...,n (ii) Không tồn tại K ' ⊆ K mà K ' có thể xác định được giá trị của Aj , với mọi j = 1,2,...,n Theo định nghĩa trên, K là tập con nhỏ nhất mà giá trị của nó có thể xác định được duy nhất một bộ giá trị của quan hệ. Khóa theo định nghĩa trên gọi là khóa ề nghị (candidate key). K được gọi là siêu khóa (superkey) của quan hệ R nếu K ' ⊆ K là một khóa của quan hệ. Như vậy một quan hệ Q luôn có ít nhất một siêu khóa và có thể có nhiều siêu khóa. Thí dụ 1.8 Với quan hệ LOPHOC (MaLop, TenLop, SoSV, MaKhoa) Siêu khoá : K1 = {MaLop, TenLop} K2 = {MaLop, SoSV} K3= {MaLop, TenLop, MaKhoa} K4= {MaLop, SoSV, MaKhoa} Ý nghĩa thực tế của khóa là dùng để nhận diện một bộ trong một quan hệ, khi cần thiết tìm thông tin một bộ q nào đó ta chỉ cần biết giá trị của khóa của q là đủ để dò tìm và hoàn toàn xác định được nó trong quan hệ. Trong trường hợp lược đồ quan hệ có nhiều khóa đề nghị, khi cài đặt lên một hệ quản trị CSDL người ta chọn ra một khóa trong số các khoá đề nghị này để sử dụng. Khi đó khóa này được gọi là khóa chính (primary key) và các khóa còn lại là hó g g. Khóa chính chỉ thật sự có ý nghĩa trong quá trình khai thác CSDL, khóa chính hoàn toàn không có vai trò gì khác so với các khóa chỉ định còn lại. 11 Trong các hệ quản trị CSDL có cài đặt cơ chế tự động kiểm tra tính duy nhất của khóa chính. Khi người sử dụng thêm một bộ mới q2 có giá trị khóa chính trùng với giá trị khóa chính của một bộ q1 đã có trong quan hệ thì hệ thống sẽ báo lỗi và yêu cầu nhập lại giá trị khác. Các thuộc tính tham gia vào một khóa được gọi là thuộc tính khoá. Về mặt ký hiệu, trong lược đồ quan hệ các thuộc tính khóa được gạch dưới. Trong một bộ của quan hệ, các thuộc tính khóa không chứa giá trị rỗng. Không được phép sửa đổi giá trị của thuộc tính khoá, nếu người sử dụng muốn sửa giá trị thuộc tính khoá của bộ q, cần phải hủy bỏ bộ q sau đó thêm vào bộ q’ với giá trị khóa đã được sửa đổi. Thí dụ 1.9 Một lược đồ CSDL như sau: KHOA (MaKhoa, TenKhoa, NgayThanhLap) LOPHOC (MaLop, TenLop, NienKhoa, SoHocvien, MaKhoa) MONHOC (MaMon, TenMon, SoTC) HOCVIEN (MaHV, HoHV, TenHV, NgaySinh, QueQuan, MaLop) GIAOVIEN (MaGV, HoGV, TenGV, NgaySinh, HocVi, ChuyenNganh) KQUATHI (MaHV, MaMon, LanThi, NgayThi, DiemThi, GhiChu) DAY (MaGV, MaLop, MaMon) Với hai quan hệ R và S, một tập thuộc tính K của quan hệ R được gọi là khóa ngoại (foreign key) của quan hệ R nếu K là khóa của quan hệ S. Thí dụ 1.10 • Trong quan hệ LOPHOC, MaKhoa là khoá ngoại vì MaKhoa là khóa của quan hệ KHOA. • Trong quan hệ HOCVIEN, MaLop là khoá ngoại vì MaLop là khóa của quan hệ LOPHOC.