Cơ sở dữ liệu - Chương 1: Đại cương về các hệ cơ sở dữ liệu

65 trang vanle 3500

Download

Bạn đang xem 20 trang mẫu của tài liệu "Cơ sở dữ liệu - Chương 1: Đại cương về các hệ cơ sở dữ liệu", để tải tài liệu gốc về máy bạn click vào nút DOWNLOAD ở trên

Tài liệu đính kèm:

co_so_du_lieu_chuong_1_dai_cuong_ve_cac_he_co_so_du_lieu.pdf

Nội dung text: Cơ sở dữ liệu - Chương 1: Đại cương về các hệ cơ sở dữ liệu

Thơng tin chung Cơ sở dữ liệu •Giảng viên – Nguyễn Hồng Phương –Bộ mơn Hệ thống thơng tin, Viện Nguyễn Hồng Phương CNTT&TT, B1-603, B1-702. phuongnh@soict.hut.edu.vn – Email: phuongnh@soict.hut.edu.vn •Giờ tiếp sinh viên tại Bộ mơn: Bộ mơnmơnHHệ thống thơng tin –Sáng thứ hai hàng tuần. ViệnnCơngCơngngh ệ thơng tin và Truy ền thơng – Ngồi ra, xin liên hệ trước. Đạiihhọ ccBáchBáchKhoa Hà Nội 1 2 Tổng quan về mơn học Đánh giá mơn học • Mụctiêu:Sau khi học xong mơn học này, sinh viên ngành cơng nghệ •Dự lớp đầy đủ,tíchcựcxâydựng bài thơng tin cĩ thể: •Kiểm tra giữa kỳ –Chỉ ra nguyên lý củahệ cơ sở dữ liệu •Kiểm tra cuối kỳ (CSDL). –Thiếtkế và xây dựng mộthệ CSDL. •Khối lượng: 3 tc, trong 15 tuần 3 4 Tài liệu học tập Nội dung mơn học •Bài giảng trên lớp • Sách tham khảo: •Chương 1: Đại cương về các hệ CSDL. – Nguyễn Kim Anh, Nguyên lý củacáchệ cơ sở dữ liệu, NXB ĐạihọcQuốcgia,HàNội, 2004. •Chương 2: Các mơ hình dữ liệu. –TơVănNam,Giáo trình Cơ sở dữ liệu,NXBGiáodục, •Chương 3: Ngơn ngữđịnh nghĩavàthaotác 2006. – Nguyễn Thiên Bằng, Phương Lan, Giáo tìtrìn hSQL Server dữ liệu đối với mơ hình quan hệ. 2000, 2004. •Chương 4: Lý thuyếtthiếtkế CSDL quan – NguyễnNgọc Minh, Hồng ĐứcHải, TrầnTiếnDũng, Tự hệ. học Microsoft SQL Server 2000 trong 21 ngày,NXBLao động-Xã hội, 2002. •Chương 5: Tối ưuhĩacâutruyvấn – J.D.Ullman, A First Course in Database Systems, Prentice-Hall,1997. •Chương 6: An tồn và tồn vẹn dữ liệu. – J.D.Ullman, Principles of Database and Knowledge-Base •Chương 7: Tổ chức dữ liệu vật lý Systems,vol.1, Computer Science Press,1988. – Các tài liệu khác •Chương 8: XML (?) 5 6 1 1
Danh ngơn Hồ Chí Minh “Trời cĩ bốn mùa: Xuân, Hạ, Thu, Đơng; Đất cĩ bốn phương: Đơng, Tây, Nam, Bắc; Người cĩ bốn đức: Cần, Kiệm, Liêm, Chín h; Thiếu một mùa khơng thể thành Trời; Thiếu một phương khơng thể thành Đất; Thiếu một đức khơng thể thành Người.” 7 8 2 2
Nội dung chương này Chương 1 • 1.1 Các hệ thống xử lý tệp Đại cương về các hệ cơ sở dữ liệu  truyền thống và những hạn chế của nĩ. Nguyễn Hồng Phương • 121.2 Các hệ CSDL: khái niệm, phuongnh@soict.hut.edu.vn khả năng, kiến trúc, người dùng của một hệ quản trị CSDL. Bộ mơnmơnHHệ thống thơng tin ViệnnCơngCơngngh ệ thơng tin và Truy ền thơng • 1.3 Sự phân loại các hệ Đạiihhọ ccBáchBáchKhoa Hà Nội CSDL. 1 2 1.1 Các hệ thống xử lý tệp truyền thống Các hệ thống xử lý tệp truyền thống •Bước khởi đầu của quá trình •Mỗichương trình ứng dụng tin học hĩa doanh nghiệp. định nghĩavàquảnlýcáctệp •Tập trung vào nhu cầu xử lý dữ liệu dữ liệucủa riêng nĩ. của các phịng riêng lẻ trong tổ chức màkhơà khơng xem xé t tổng thể t ổ chức • Trước khi xuất hiện các phần này. mềmhệ quảntrị CSDL, trong •Viết một chương trình mới quá khứ các hệ thống trên cơ đối với mỗi ứng dụng đơn lẻ, sở tệp đã đượctạolập để xử khơng cĩ kế hoạch, khơng cĩ lý mộtsố lượng lớndữ liệu. mơ hình hướng đến sự tăng trưởng. 3 4 Hạn chế của các hệ thống Nội dung chương này xử lý tệp truyền thống •Dư thừa và khơng nhất quán dữ liệu • 1.1 Các hệ thống xử lý tệp •Khĩ khăn trong truy nhập dữ liệu truyền thống và những hạn chế của nĩ. •Cơ lập và hạn chế chia sẻ dữ liệu • 1.2 Các hệ CSDL: khái niệm, •Các vấn đề về an tồn và tồn vẹn  khả năng, kiếntrúc,người •Các vấn đề về độ tin cậy dùng củamộthệ quảntrị •Sự phụ thuộcdữ liệucủacácchương CSDL. trình ứng dụng •1.3 Sự phân loạicáchệ CSDL. 5 6 3 1
1.2 Các hệ cơ sở dữ liệu Ví dụ về quản lý đào tạo • Thơng tin cần quan tâm • CSDL (database) là gì ? –Khĩa học, lớphọc, sinh viên, giáo viên, •Tại sao phải sử dụng CSDL ? mơn học, – Thơng tin về sinh viên: thơng tin cá •Tại sao phải tìm hiểu về các hệ CSDL nhân, thơng tin họctập, (da ta base systems) ? – Thơng tin về mơn học: khốilượng, giáo viên, lịch học, •Cần lưutrữ những thơng tin đadạng Cơ sở dữ liệu 7 8 Ví dụ: khai thác thơng tin “Hình dung” về xây dựng một CSDL • Sinh viên –Các mơn học của Viện Cơng nghệ thơng •Yêu cầu tin và Truyền thơng? –Lưu trữ thơng tin cần thiết một cách chính xác – Điểm thi mơn “Hệ cơ sở dữ liệu” ? – Truy xuất thơng tin hiệu quả •Giáo viên •Thực hiện – Danh sách sinh viên lớp Tin2-K49 ? – Xác định yêu cầu nghiệp vụ –Thời khĩa biểu của lớp Tin2-K49 ? –Xác định thơng tin cần lưu trữ –Xác định cách thức lưu trữ • Giáo vụ •Cần cơng cụ trợ giúp xây dựng một CSDL – Danh sách sinh viên K47 tốt nghiệp loại giỏi ? Phần mềm quản trị CSDL Phần mềm ứng dụng 9 10 Các khái niệm cơ bản Cơ sở dữ liệu (database) •Là một tập hợp các dữ liệu ứng dụng –Biểudiễnmộtvàikhíacạnh nào đĩcủathế hệ CSDL giớithực – Cĩ liên hệ logic thống nhất CSDL – Đượcthiếtkế và bao gồmnhững dữ liệuphục vụ mộtmục đích nào đĩ. •Làmộtbộ sưutậpcácdữ liệu tác nghiệp đượclưutrữ lạivàđượccáchệứng dụng củamộtxínghiệpcụ thể nào đĩsử dụng. Hệ QTCSDL 11 12 4 2
Hệ quản trị cơ sở dữ liệu Hệ cơ sở dữ liệu (Database Management SystemSystem DBMS)DBMS) •Là mộthệ thống phầnmềmcho •Là một hệ thống gồm 4 thành phần phép –Hệ quản trị CSDL – Định nghĩa, tạo lập: xác định kiểu, cấu –Phần cứng trúc, ràng buộc dữ liệu, lưu trữ dữ liệu trêáhên các thiết bị n hớ. – CSDL và phần mềm ứng dụng – Thao tác: truy vấn, cập nhật, kết xuất, –Những người sử dụng các CSDL cho các ứng dụng khác nhau • Ví dụ: Hệ quản lý đào tạo, hệ quản lý • Ví dụ: MS SQL Server, DB2, nhân sự, hệ quản lý kinh doanh, MS Access, Oracle, FoxPro, 13 14 Hệ CSDL Các tính năng của hệ quản trị CSDL •Quản lý dữ liệu tồn tại lâu dài Hệ Ứng dụng – Định nghĩa dữ liệu CSDL –Quản lý lưu trữ • Truy xuất dữ liệu một các h hiệu quả Hệ Quản Trị CSDL –Biểu diễn các thao tác dữ liệu –Xử lý câu hỏi –Quản trị giao dịch CSDL CSDL 15 16 Các tính năng của hệ quản trị CSDL Các ngơn ngữ • Ngơn ngữđịnh nghĩadữ liệu(Data •Hỗ trợ ít nhất một mơ hình dữ liệu Definition Language - DDL) • Đảm bảo tính độc lập dữ liệu –Cấutrúcdữ liệu –Mốiliênhệ giữacácdữ liệuvàquytắc, ràng •Hỗ trợ các ngơn ngữ cấpcaonhất buộcápđặtlêndữ liệu định cho ppphép ngườisử dụng định • Ngơn ngữ thao tác dữ liệu(Data Maniltiipulation Language - DML) nghĩacấutrúccủadữ liệu, truy nhập –Tìmkiếm, thêm, xĩa, sửadữ liệutrongCSDL và thao tác dữ liệu • Ngơn ngữđiềukhiểndữ liệu(Data • Điều khiển truy nhập Control Language - DCL) –Thayđổicấutrúccủacácbảng dữ liệu •Phục hồi dữ liệu –Khaibáobảomật thơng tin –Quyềnhạncủangười dùng trong khai thác CSDL 17 18 5 3
Sự trừu tượng hĩa dữ liệu Tương ứng 3 mức với ngơn ngữ Pascal Type khach_hang = record ten:string; Khung nhìn 1 Khung nhìn n ngay_sinh:string; Mức khung nhìn (ngồi) dia_chi:string; mơ tả cách mà người sử dụng cĩ thể nhìn thấy dữ end; liệu •Mứcvậtlý:mộtbản ghi khach_hang đượcmơtả Sơ đồ khái niệm như một khối nhớ,chương tìtrìn hdịch che dấucác (logic) định nghĩa cấu trúc logic chi tiếtmứcnàyđốivớingườilập trình. Mức quan niệm của dữ liệu, dữ liệu nào được lưu trữ và mối quan •Mứclogic:mỗibảnghiđượcmơtả bởimột định (logic) hệ giữa các dữ liệu nghĩakiểu, ngườilậptrìnhsử dụng ngơn ngữ lập trình làm việctạimứctrừutượng này. định nghĩa cấu trúc các •Mức khung nhìn: ngườisử dụng máy tính thấy Sơ đồ trong tệp và chỉ dẫn được sử dụng trong cơ sở dữ liệu mộttậpcácchương trình ứng dụng, che dấu (vật lý) những chi tiếtvề các kiểudữ liệu Mứclưu trữ (cách lưu trữ dữ liệu như thế nào) (trong) 19 20 Kiến trúc của một hệ quản trị CSDL Quản lý lưu trữ Các thay đổi sơ đồ Các truy vấnCác thay đổi dữ liệu •Yêu cầu Bộ quảnlýlưu trữ –lưu trữ và truy xuất dữ liệu trên các thiết Quản lý buffer Quản Bộ xử lý lý câu hỏi Bộ quảntrị bị nhớ giao dịch giao dịch • Thực hiện Quản lý tệp –Tổ chức tối ưu dữ liệu Bộ quảnlý lưu trữ trên thiết bị nhớ –Tương tác hiệu quả Metadata & với bộ quản lý tệp Data dictionary Data & index (từ điển dữ liệu) (chỉ mục) Siêu dữ liệu Dữ liệu (data) (metadata) 21 22 Xử lý câu hỏi Quản trị giao dịch •Yêu cầu Bộ xử lý câu hỏi –Tìm kiếm dữ liệu trả Bộ biên dịch •Yêu cầu lời cho một yêu cầu Bộ tối ưu – Định nghĩagiaodịch: mộttập các thao truy vấn. tác đượcxử lý như một đơnvị khơng •Thực hiện Bộđánh giá chia căt được. –Biến đổi truy vấn ở – Đảmbảotínhđúng đắnvàtínhnhất mức cao thành các Bộ quảnlý quán củadữ liệu. yêu cầu cĩ thể hiểu lưu trữ được bởi hệ CSDL. •Thực hiện –Lựa chọn một kế –Quản lý điều khiển tương tranh. Metadata & Data & index hoạch tốt nhất để trả Data dictionary – Phát hiện lỗi và phục hồi CSDL lời truy vấn này. 23 24 6 4
Người dùng Người dùng • Ngườiphântíchhệ thống và phát triển ứng • Ngườithiếtkế và cài đặthệ QTCSDL: dụng:chịutráchnhiệmxácđịnh yêu cầucủa chịutráchnhiệmthiếtkế và cài đặtcác ngườidùngcuối, xác định các giao dịch cầnthiết module củahệ QTCSDL và các giao diện để đáp ứng các yêu cầungườidùng.Ngườilập dưới hình thức các gĩi phần mềm trình ứng dụng cài đặtnhững yêu cầunàytrong chương tìtrìn h, kiểm thử,gỡ rối, lập tài liệucho chương trình • Người phát triểncơngcụ:chịutrách nhiệmthiếtkế và cài đặtcácgĩiphầnmềm • Ngườithiếtkế CSDL:chịutráchnhiệmxácđịnh hỗ trợ cho việcthiétkê,sử dụng cũng như dữ liệulưutrữ trong CSDL và cấutrúcbiểudiễn tăng cường hiệunăng củacáchệ CSDL. và lưutrữ những dữ liệunày 25 26 Người dùng Nội dung chương này • Ngườisử dụng cuối:làngườikhaitháccáchệ • 1.1 Các hệ thống xử lý tệp CSDL truyền thống và những hạn chế của nĩ. • Ngườiquảntrị CSDL:chịu trách nhiệmcho ppphép truy nhập CSDL, điều phốivàkiểmtrasử • 121.2 Các hệ CSDL: khái niệm, dụng CSDL, quản lý tài nguyên phầncứng và phân mềmkhicầnthiết khả năng, kiến trúc, người • Ngườibảotrìhệ thống:lànhững ngườiquản dùng của một hệ quản trị trị hệ thống chịu trách nhiệmviệchoạt động và CSDL. bảotrìmơitrường (phầncứng và phầnmềm) cho hệ CSDL  • 1.3 Sự phân loại các hệ CSDL. 27 28 1.3 Phân loại các hệ CSDL Các hệ CSDL tập trung •Mơhìnhdữ liệu •Hệ CSDL cá nhân: mộtngườisử dụng đơn –Mạng vs. phân cấp vs. quan hệ vs. hướng đối lẻ vừathiếtkế,tạolậpCSDL,cậpnhật, tượng vs. bảotrìdữ liệu, lậpvàhiểnthị báo cáo. đảmnhiệmvaitrị:ngườiquảntrị CSDL, người •Số người sử dụng viết chương trình ứng dụng, end-user. –Một người dùng vs. nhiều người dùng •Hệ CSDL trung tâm: dữ liệu đượclưutrữ • Tính phân tán của CSDL trên một máy tính trung tâm. –Tập trung vs. Phân tán •Hệ CSDL khách-chủ: • Tính thống nhất của dữ liệu – Các máy tính trung tâm lớn đắtsovớicác – Đồng nhất vs. Khơng đồng nhất máy nhỏ và máy trạm. –Các ứng dụng máy khách truy nhậpdữ liệu • đượcquảnlýbởimáychủ. 29 30 7 5
Các hệ CSDL tập trung (tiếp) Các hệ CSDL phân tán •CSDLphântán?LàmộttậpcácCSDLcĩ Hệ CSDL trung quan hệ logic vớinhaunhưng đượctrảira tâm trên nhiềutrạmlàmviệccủamộtmạng máy tính. Hệ CSDL cá nhân • Cĩ 2 tính chất: quan hệ logpgic và phân tán •Hệ QTCSDL phân tán: Là mộthệ thống phầnmềmchophéptạolậpCSDLPTvà điềukhiển các truy nhập đốivớiCSDLPT này. •Chiara2loại: CSDLPT thuầnnhấtvà khơng thuầnnhất Hệ CSDL khách- chủ 31 32 Các hệ CSDLPT (tiếp) Kết luận •CSDLchophéplưutrữ và khai thác dữ liệumộtcáchthống nhấtvàhiệuquả (đặc biệttrongtrường hợpkhốilượng dữ liệu lớn). • Sự trừu tượng về dữ liệu và tính độc lập dữ liệuchophéppháttriển ứng dụng “dễ dàng hơn”. •Hệ quảntrị CSDL cung cấpcáccơngcụ hữuhiệutrợ giúp việctạolậpCSDLvà phát triển ứng dụng 33 34 Sử dụng kiến thức mơn học Các điểm cần lưu ý trong này trong tương lai chương này ‘‘More than 80 % of real world computer applications are associated with databases’’* •Cách tiếp cận tệp vs. cách tiếp cận * Korth & Silberschatz. Database System Concepts. CSDL •CSDL vs. hệ QTCSDL vs. hệ CSDL •Kiến trúc 3 mức của hệ CSDL •Các chức năng chính của một hệ Nghiên cứu QTCSDL Phát triển nghiên cứuvà ứng dụng phát triển •Người sử dụng trong một hệ CSDL • Phân loại các hệ CSDL 35 36 8 6
Lời hay ý đẹp Điều chúng ta biết chỉ là một giọt nước, điều khơng biết mênh mơng như đại dương Einstein 37 38 9 7
1/30/2012 Nội dung Các mơ hình dữ liệu •Tổng quan về mơ hình dữ liệu • Mơ hình phân cấp • Mơ hình mạng Nguyễn Hồng Phương • Mơ hình quan hệ phuongnh@soict.hut.edu.vn • Mơ hình thực thể liên kết • Mơ hình hướng đối tượng Bộ mơnmơnHHệ thống thơng tin ViệnnCơngCơngngh ệ thơng tin và Truy ền thơng • Đánh giá, bài tập Đạiihhọ ccBáchBáchKhoa Hà Nội 1 2 Tổng quan về mơ hình dữ liệu Tổng quan (tiếp) • Mơ hình dữ liệu [Codd, 1980] gồm: –Một tập hợp các cấu trúc của dữ liệu •Nhiềumơhìnhcịnbaogồmcả mộttập –Một tập hợp các phép tốn để thao tác với các các phép tốn để thao tác các dữ liệu dữ liệu •Mơhìnhthuộcdạng ngữ nghĩa: tập trung –Một tập hợp các ràng buộc về dữ liệu về ngữ nghĩacủadữ liệunhư mơ hình • Mơ hình dữ liệu là một tập hợp các khái thực thể liên kết, sử dụng để hỗ trợ người niệm dùng để mơ tả: dùng cĩ cái nhìn khái quát về dữ liệu –Dữ liệu •Mơhìnhthuộcdạng khái niệm: tập trung –Ngữ nghĩa của dữ liệu vào cách thứctổ chứcdữ liệutạimứckhái –Các mối quan hệ trong dữ liệu niệmnhư mơ hình mạng, mơ hình liên kết, –Các ràng buộc dữ liệu mơ hình quan hệ, độclậpvớiDBMSvàhệ thống phầncứng để cài đặtcơ sở dữ liệu 3 4 Vài nét về lịch sử Một vài mơ hình dữ liệu Mơ hình DB2, ORACLE- quan hệ Mơ hình Mơ hình 10i, SQL Server • Mơ hình phân cấp phân cấp quan hệ mở rộng System R(81), DB2, XML ORACLE, SQL • Mơ hình mạng IMS, Server, Sybase, dbXML,natix, System • Mơ hình quan hệ 2k, Tamino, 1965 1970 1975 1980 1985 1990 1995 2000 2005 2010 • Mơ hình thực thể liên kết Mơ hình O2, • Mơ hình hướng đối tượng ORION, Thựcthể-liên kết IRIS, • Mơ hình bán cấu trúc Mơ hình IRDS(87) mạng ,CDD+,Mơ hình • Mơ hình dữ liệu của XML DMS(65), hướng đối Mơ hình bán Lore CODASYL tượng cấutrúc (97), (71), IDMS, IDS 5 6 10 1
1/30/2012 Mơ hình dữ liệu phân cấp Đặt vấn đề ((Hierarchical data model)) • Đặc điểmcủa các mơ hình dữ liệu? •Ra đời những năm 60-65 •Sự khác nhau giữa các mơ hình dữ •Biểu diễn bằng cây – Quan hệ cha-con liệu? –Mỗi nút cĩ 1 cha duy nhất • Cácmơ hìhình dữ liệuphổ biếnngày – 1 CSDL = 1 tập các cây = 1 rừng nay • Các khái niệm cơ bản –Bản ghi – Mĩc nối – Các phép tốn: GET, GET UNIQUE, GET NEXT, GET NEXT WITHIN PARENT, 7 8 Mơ hình dữ liệu phân cấp –Ví– Ví dụ Mơ hình dữ liệu phân cấp • Ưu điểm –Dễ xây dựng và thao tác lop giao_vien –Tương thích với các lĩnh vực tổ chức phân cấp – Ngơn ngữ thao tác đơn giản: duyệt cây. • Nhược điểm: –Sự lặp lại của các kiểu bản ghi dữ liệu dư sinh_vien mon_hoc mon_hoc thừa và khơng nhất quán. •Giải pháp: bản ghi ảo –Hạn chế trong biểu diễn ngữ nghĩa của các diem_thi mĩc nối giữa các bản ghi (chỉ cho phép quan hệ 1-n) 9 10 Mơ hình dữ liệu mạng ((Network data model)) Mơ hình dữ liệu mạng –Ví– Ví dụ •Sự ra đời –Sử dụng phổ biến từ những năm 60, được định nghĩa lại vào giao_vien năm 71 •Biểu diễn bằng đồ thị cĩ hướng giang_day • Các khái niệm cơ bản – Tập bản ghi (record) hoc lop mon_hoc •Kiểu bản ghi (record type) •Các trường (field) –Mĩc nối co_diem gom •Tên của mĩc nối •Chủ (owner) – thành viên (member): theo hướng của mĩc nối •Kiểu mĩc nối: 1-1, 1-n, đệ quy sinh_vien co diem_thi – Các phép tốn •Duyệt: FIND, FIND member, FIND owner, FIND NEXT •Thủ tục: GET 11 12 11 2
1/30/2012 Mơ hình dữ liệu mạng Mơ hình dữ liệu quan hệ • Ưu điểm •Sự ra đời: vào năm 1970[Codd, 1970] – Đơn giản •Dữ liệu được biểu diễn dưới dạng bảng –Cĩ thể biểu diễn các ngữ nghĩa đa dạng • Là mơ hình dữ liệu khái niệm phổ biến cho với kiểu bản ghi và kiểu mĩc nối đến tận thời điểm hiện tại –Truy vấn thơng qua phép duyệt đồ thị •Dựa trên lý thuyết tốn học, đồng thời (navigation) cũng gần với cấu trúc tệp và cấu trúc dữ •Nhược điểm: liệu nên cĩ hai loại thuật ngữ liên quan: –Số lượng các con trỏ lớn –Thuật ngữ tốn học: quan hệ, bộ, thuộc tính –Hạn chế trong biểu diễn ngữ nghĩa của –Thuật ngữ hướng dữ liệu: bảng, bản ghi, trường các mĩc nối giữa các bản ghi 13 14 MON_HOC Ví dụ maMH tenmon soHT Mơ hình dữ liệu quan hệ m ơ hìn h mơ hình CNTT01 Nhậpmơn CSDL 4 CNTT02Ví d TruyụềnDL vàmạng 4 dữ liệu CNTT03 Phân tích và thiếtkế hệ thống 4 quan hệ HTTT01 Quảnlýdự án 3 • Các khái niệm cơ bản LOP –Thuộc tính, miền thuộc tính malop lop khoa GVCN loptruong – Quan hệ IT4 Tin 4 CNTT Ng. V. Anh TrầnT. Bình IT5 Tin 5 CNTT Lê A. VănNg. Đ. Trung – Khĩa IT6 Tin 6 CNTT Ng. T. ThảoTrầnM. Quế IT7 Tin 7 CNTT Ng. V. Quý Ng. T. Phương SINH_VIEN maSV tenSV ngaysinh gt diachi malop SV0011 Trần T. Bình 1/4/1981 0 21 T. Q. B IT4 SV0025 Ng. Đ. Trung 3/2/1980 1 56 Đ. C. V IT5 SV0067 TrầnM. Quế 26/3/1982 0 45 H. B. T IT6 15 16 SV0034 Ng. T. Phương 29/2/1980 0 86 L. T. N IT7 Mơ hình dữ liệu quan hệ Mơ hình dữ liệu quan hệ • Thuộc tính (~trường): là các đặc tính của • Quan hệ (~bảng):Cho n miềngiátrị D1, một đối tượng D2 , ,Dn khơng nhấtthiếtphânbiệt, r là mộtquanhệ trênnmiềngiátrịđĩnếur •Mỗi thuộc tính được xác định trên một miền là mộttậpcácn-bộ (d ,d , ,d )sao giá trị nhất định gọi là miền thuộc tính 1 2 n cho di Di •Ví dụ: • Một quan hệ cĩ thể được biểu diễn dưới – Sinhviên (MãSV, TênSV, Nămsinh, GiớiTính, ĐịaChỉ) dạng 1 bảng trong đĩ1dịng trong bảng – dom(MãSV) = {char(5)} tương đương với1bộ ,một cột trong bảng tương đương với1thuộctínhcủaquanhệ – dom(TênSV) = {char(30)} •Bậc của1quanhệ là số các thuộctính –dom(Nămsinh) = {date} trong quan hệ –dom(GiớiTính) = {0, 1} •Lựclượng của1quanhệ là số các bộ –dom(ĐịaChỉ) = {char(50)} trong quan hệ 17 18 12 3
1/30/2012 Mơ hình dữ liệu quan hệ Mơ hình dữ liệu quan hệ • Định nghĩa Khố củaquanhệ rtrên • Định nghĩa (tiếp): Cho U = {A1,A2 , ,A}làmộttậphữuhạncác tậpthuộc tính U = {A1 ,A2 , ,An} n là mộttậpK Usaochovớibấtkỳ 2 thuộctínhtrongđĩdom(Ai )=Di,r là quan hệ trên tập thuộc tính U ký bộ t1 , t2 thuộcrđềutồntạimột hiệulàr(U)nếu: thuộc tính A thuộcKmàt1[A] ≠ t2 [A] r D1 D 2 Dn •Mộtquanhệ cĩ thể cĩ nhiềukhố •U đượcgọilàsơđồquan hệ (lược đồ quan hệ) •Nếu K là khố củarthìmọiK’sao cho K  K’ đềulàkhốcủar.K’được 19 gọilàsiêu khố củar 20 Mơ hình dữ liệu quan hệ Mơ hình dữ liệu quan hệ Ví dụ: • Định nghĩa:Klàkhố tối •Quanhệ: SinhViên(MãSV, TênSV, NămSinh, thiểu củarnếuKlàmộtkhố GiớiTính, Lớp) củarvàbấtkỳ tậpconthựcsự SV001 Nguyễn Văn An 1982 1 Tin 7 nào củaKđềukhơng phảilà SV002 Nguyễn Văn An 1985 1 HTTT khố củar SV003 Lê Văn Cường 1981 1 HTTT • Định nghĩa:MộttậpconK U SV004 Nguyễn Thùy Linh 1981 0 BK65 đượcgọilàkhố ngồi của • Siêu khố: {MãSV, HọTên}; quan hệ r(U) tham chiếu đến •Khố tối thiểu: {MãSV}; {HọTên, NămSinh} mộtquanhệ r’ nếuKlàkhố • Khố ngồi: TênLớp nếu coi nĩ là khố chính của quan hệ Lớp chính củar’ 21 22 Mơ hình dữ liệu quan hệ - Mơ hình thực thể liên kết nhận xét ((EntityEntity RelationshipRelationship data model)) •Chophépmơtả các dữ liệu cĩ liên quan trong mộtxínghiệptrongthế giớithựcdưới • Ưu điểm dạng các đốitượng và các mốiquanhệ của –Dựa trên lý thuyết tập hợp chúng. – Khả năng tối ưu hố các xử lý phong • Được sử dụng cho bước đầu thiết kế CSDL, phú làm nềntảng để ánh xạ sang mộtmơhình khái niệmnàođĩmàHệ quảntrị CSDL sẽ sử •Nhược điểm dụng –Hạn chế trong biểudiễnngữ nghĩa • Trong mơ hình thựcthể liên kết, CSDL được –Cấutrúcdữ liệu khơng linh hoạt mơ hình hĩa như là: –Mộttậphợpcácthựcthể –Liênhệ giữacácthựcthể này 23 24 13 4
1/30/2012 Mơ hình thực thể liên kết Mơ hình thực thể liên kết Các khái niệm cơ bản •Thực thể, tập •Thựcthể: một đốitượng trong thế thực thể giớithực, tồntại độclậpvàphânbiệt đượcvớicácđốitượng khác •Thuộc tính • Tập thực thể: một tập hợp các thực • Khố thể cĩ tính chấtgiống nhau • Liên kết, tập •Vídụ: liên kết –Thựcthể:một sinh viên, mộtlớp –Tậpthựcthể:tồnthể sinh viên của1 lớp, tồn thể các lớpcủa1khoa 25 26 Mơ hình thực thể liên kết Mơ hình thực thể liên kết Kiểu thuộc tính •Thuộctínhlà đặctính sinh_viên củamộttậpthựcthể •Thuộc tính đơn giản sinh_viên –Tậpthựcthể SinhViên cĩ (thuộc tính nguyên các thuộctínhnhư: TênSV, tố) NămSinh, •sv1 gioitinh •Mỗithựcthể trong tập •sv2 – cĩ kiểu dữ liệu tenSV thựcthể cĩ mộtgiátrị •sv3 nguyên tố maSV namsinh đặctínhnằmtrongmiền •Thuộc tính phức diachi giá trị củathuộctính maSV – Sinh viên 1 cĩ: Họtên là –cĩ kiểu phức, định diachi so_pho quan thanh_pho NguyễnHải Anh, Nămsinh nghĩa bởi các thuộc 1980 tenSV gioitinh tính khác namsinh 27 28 Mơ hình thực thể liên kết Mơ hình thực thể liên kết Kiểu thuộc tính Khĩa •Thuộctínhđa giá maMH •Mộthaymộttậpthuộc tính mà giá trị của trị chúng cĩ thể xác định duy nhấtmộtthực tenmon thể trong tậpthựcthể –tương ứng với mỗi mon_hoc thực thể, cĩ thể soHT –Tậpthựcthể SinhViên cĩ thể dùng MãSV làm nhận nhiều giá trị khố giao_vien •Khốgồm nhiềuthuộctínhthìgọilàkhố •Thuộctínhsuy phức diễn sinh_viên •Mộttậpthựcthể cĩ thể cĩ nhiềukhố –cĩthể tính tốn nhưng chỉ mộttrongsố các khố được đượctừ (các) thuộc chọnlàmkhố chính nam tính khác tenSV •TrongsơđồER, thuộctínhnàođượcchọn tuoi maSV làm khố chính sẽđược gạch chân ngaysinh 29 30 diachi 14 5
1/30/2012 Mơ hình thực thể liên kết Mơ hình thực thể liên kết Liên kết - Tập liên kết Liên kết - Tập liên kết - Ví dụ: •Một liên kết là một mốiliênhệ cĩ nghĩa giữa nhiềuthựcthể maSV maMH –Chomộtthựcthể SinhViên1 và LớpA, liên kết tenSV ThànhViên chỉ ra rằng SinhViên1 là 1 thành tenmon viên củaLớpA ngaysinh sinh_viên diem_thi mon_hoc •Tập liên kết là mộttậphợpcácliênkết soHT cùng kiểu nam diachi –Giữatậpthựcthể SinhViên và Lớpcĩ1tập liên ket_qua kết ThànhViên, chỉ ra rằng mỗisinhviênđềulà thành viên của1lớpnàođĩ •Một liên kếtcĩthể cĩ thuộc tính 31 32 Mơ hình thực thể liên kết Cách lập sơ đồ thực thể - liên kết Ràng buộc của kết nối 1 1 • 1-1:Liênkết1thựcthể lop_hoc chu_nhiem giao_vien •Bước 1: Xác định các thựcthể củamộttậpthựcthể với nhiềunhất1thựcthể của •Bước2:Xácđịnh các liên kếtgiữa tậpthựcthể khác • 1-n:Liênkết1thựcthể 1 n các thựcthể của một tập thực thể với lop_hoc thanh_vien sinh_vien nhiềuthựcthể củatậpthực – Bậccủa liên kết thể khác –Ràngbuộc (1-1, 1-n, n-n, đệ quy) • n-n:Liênkết1thựcthể n n củamộttậpthựcthể với sinh_viên dang_ky mon_hoc nhiềuthựcthể củatậpthực thể khác và ngượclại • đệ quy:Liênkếtgiữacác mon_hoc thựcthể cùng kiểu dieu_kien 33 34 Ho Dem Ten Bài tập: Vẽ sơ đồ ER Ten _phong Ma_phong Dia_diem •Bàitốn:phântíchvàthiếtkế 1CSDLgồmcác thơng tin trong 1 cơng ty (nhân viên, phịng ban, SoBH HoTen Dia_chi Luong dự án) Ngay_sinh 1 PHONG_BAN –Cơngtyđượctổ chứcbởi các phịng ban. Mỗi phịng ban Gioi_tinh cĩ 1 tên duy nhất, 1 số duy nhấtvà1ngườiquảnlý 1 1 n 1 (thời điểmbắt đầucơngtácquảnlýcủangườinàycũng nguoiPT NHAN_VIEN La_NV đượclưulạitrongCSDL).Mỗi phịng ban cĩ thể cĩ nhiều trụ sở làm việc khác nhau n 1 Phu_trach Quan_ly –Mỗi phịng điềuphốimộtsố dự án. Mỗidự án cĩ 1 tên 1 và 1mã số duy nhất, thực hiệntạimột địa điểm duy nguoibiPT n nhất Ngay_BD So_gio –Cácthơngtinvề nhânviêncần được quan tâm gồm: tên, số bảohiểm, địachỉ,lương, giới tính, ngày sinh. Mỗi Dieu_phoi nhânviênlàmviệctạimột phịng ban nhưng cĩ thể co Lam_viec tham gia nhiềudự án khác nhau. Những dự án này cĩ n thểđược điềuphốibởi các phịng ban khác nhau. Thơng n m tin về số giờ làm việctrongtừng dự án (theo tuần) cũng DU_AN như ngườiquảnlýtrựctiếpcủacácnhânviêncũng được CON lưutrữ – Thơng tin về con cái c ủatừng nhân viên: tên, giới tính, ngày sinh 35 Ten_DA Ma_DA Dia_diem36 HoTen Gioi_tinh Ngay_sinh 15 6
1/30/2012 Biến đổi sơ đồ thực thể liên kết Biến đổi các tập thực thể sang sơ đồ quan hệ •Bước 1: 1 tập thực thể 1 quan hệ •Biến đổitậpcácthựcthể –thuộc tính thuộc tính (trường) •Biến đổi các liên kết –1 thực thể 1 bộ •Cáckhốcủacácsơđồquan hệ –khố của tậpthựcthể khố của quanhệ sinh_viên •Cácsơđồquan hệ với khố chung maSV tenSV ngaysinh nam diachi malop SINH_VIEN •sv1 maSV •sv1tenSV ngaysin gt diachi lop h •sv2 SV001 •sv2TrầnT. Bình 1/4/81 0 21 T. Q. B IT4 •sv3 SV002 Ng. Trung 3/2/80 1 56 Đ. C. V IT5 37 SV006 •sv3TrầnM. Quế 26/3/82 0 45 H. B. T IT6 38 •sv4 SV003 Ng. Hương 29/2/80 0 86 L. T. N IT7 Biến đổi các tập thực thể Biến đổi các liên kết • Bước2:1tậpthựcthể xác định từ • Bước 3: Liên kết 1-1  Thêm 1 quan hệ mớixácđịnh bởicác tậpthựcthể khác (E) qua 1 liên kết thuộctínhnằmtrongkhốcủacácthực 1quan hệ chứakhốcuả E: thể cĩ liên quan CHU_NHIEM_LOP(malop,maGV) LOPTRUONG(maSV) hoặc  Dùng khố ngồi LOP_HOC(malop,lop,khoa,maGV) sinh_viên la_mot lop_truong maGV malop 1 1 ngaysinh lop lop_hoc chu_nhiem giao_vien trinhdo khoa khoa 39 40 Biến đổi các liên kết (tiếp) Biến đổi các liên kết (tiếp) • Bước4:Liên kết1-n • Bước 5: Liên kết n-n  Thêm 1 quan hệ mớixácđịnh bởicácthuộctínhnằm trong khố củacácthựcthể cĩ liên quan Thêm 1 quan hệ mớixácđịnh bởicác SINHVIEN_LOP(malop, maSV) thuộctínhnằmtrongkhốcủacác hoặc thựcthể cĩ liên quan và các thuộc  Dùng khố ngồi: thêm khố chính của quan hệ bên 1 vào quan hệ bên n làm khố ngồi tính của liên kết SINH_VIEN(maSV, tenSV, ngaysinh, nam, diachi, malop) maSV DANG_KY(maSV,maMH, diem) tenSV diem maSV maMH ngaysinh malop 1 tenSV n m n ten sinh_viên dang_ky mon_hoc lop lop_hoc gom sinh_vien nam ngaysinh khoa diachi nam soHT 41 42 diachi 16 7
1/30/2012 Thuộc tính đa trị Mơ hình dữ liệu hướng đối tượng (Object(Object orientedoriented data model) • Bước6:Vớimỗithuộc tính đatrị •Sự ra đời Thêm 1 quan hệ mớixácđịnh bởi –Khoảng đầu những năm 90 thuộc tính đatrị và khố củatập •Biễu diễn: sơ đồ lớp thựcthể tương ứng • Các khái niệmcơ bản – Đốitượng:một đốitượng trong thế giớithực, đượcxác MH_GV(maMH,giao_vien) định bởimột định danh duy nhất –Thuộctính:biểudiễnmột đặctínhcủa đốitượng, maMH –Phương thức :thaotácđượcthựchiệntrênđốitượng. •Tấtcả các truy nhậpvàothuộctínhcủa đốitượng đềuphải được tenmon thựchiện thơng qua các phương thứcnày. mon_hoc –Lớp:mộtcáchthức để khai báo mộttậpcácđốitượng cĩ soHT chung mộttậpthuộctínhvàphương thức giao_vien 43 44 Mơ hình dữ liệu hướng đối tượng Mơ hình dữ liệu hướng đối tượng Ví dụ: Nhận xét: class sinh_vien { string maSV; • Ưu điểm string tenSV; –Chophépđịnh nghĩakiểu đốitượng phứctạp date ngaysinh; –Tínhchất: bao đĩng (encapsulation), kế thừa boolean nam; (heritage), đahình(polymorphism) string diachi; string lop; •Nhược điểm –Cấutrúclưutrữ phứctạpvàcĩthể sử dụng string ten(); nhiềucontrỏ string ngay_sinh(); string dia_chi(); –Khả năng tối ưuhốcácxử lý bị hạnchế trong string lop(); nhiềutrường hợp void gan_DC(string DC_moi); void gan_lop(string lop); } 45 46 So sánh và đánh giá Phân loại các mơ hình Nhắc lại: Mơ hình dữ liệu là một tập hợp các khái niệm dùng để mơ tả cấu trúc của một CSDL Phân cấp Thế hệ 1 Mơ hình Mơ hình Mơ hình Mơ hình Mơ hình Các mơ hình mạng phân cấp quan hệ TT-LK Mạng HĐT dựa trên tương đối biểu diễn hạnchế hạnchế đa dạng đa dạng bản ghi ngữ nghĩa đa dạng Quan hệ DL Thế hệ 2 lưu trữ DL s/d nhiều dữ liệu dễ dàng và khĩ lưu cấu trúc con trỏ lặplại hiệu quả trữ phức tạp Thực thể-liên kết Các mơ hình dựa trên khả năng đơn giản đơn giản đa dạng đa dạng truy vấn ngữ nghĩa đốitượng hiệuquả ít khả ít khả tối ưu khơng được khơng Thế hệ 3 củatruy năng tối năng tối hố tốt xem xét h/q khi (khơng hiệu s/d nhiều Đối tượng - Quan hệ Hướng đối tượng vấn ưu ưu quả) con trỏ 47 48 17 8
1/30/2012 Các bước xây dựng một hệ CSDL Bài tập •Chosơđồthựcthể liên kếtbêndưới, hãy biến đổi 1: PHÂN TÍCH sang mơ hình quan hệ: StudentName StudentID LecturerID LecturerName StudentBirth Students Lecturers Mơ tảứng dụng Mơ hình hố DL (vd: Sơđồthựcthể-liên kết) LecturerPhone StudentAddress 2: THIẾTKẾ Belong to 3: CÀI ĐẶT ClassID Classes Learn Time ClassName ClassMonitor Subjects SubjectID Cài đặt với 1 hệ quảntrị CSDL Mơ tả DL logic với 1 mơ hình DL cụ thể SubjectName (vd: ORACLE) (vd: Sơđồquan hệ) 49 50 Lời giải Lời giải (tiếp) •Biến đổi các tập thực thể và các quan hệ •Cảitiếnthiếtkế:Bảng Students và thành các bảng: bảng Belongto cĩ cùng khĩa Lecturers(LecturerID, LecturerName, (StudentID), ta nên kếthợp chúng LecturerPhone) Students(StudentID, StudentName, StudentBirth, lại: StudentAddress) Students’(StudentID, StudentName, Classes(ClassID, ClassName, ClassMonitor) StudentBirth, StudentAddress, ClassID) Subjects(SubjectID, SubjectName) Belongto(StudentID, ClassID) Learn(LecturerID,ClassID, SubjectID, Time) 51 52 Lời hay ý đẹp Trong 10 lần thành cơng thì cĩ tới9lần thành cơng nhờ sự hăng hái và niềm tin trong cơng việc Teewilson 53 18 9
1/30/2012 Nội dung Ngơn ngữ định nghĩa •Các cách tiếpcận đốivớithiếtkế và thao tác dữ liệu đối ngơn ngữ củaCSDLquanhệ với mơ hình quan hệ –Giớithiệumộtsố ngơn ngữ và phân loại So sánh và đánh giá NguyễnnHHồng Ph ương •Một số ngơn ngữ dữ liệu mức cao phuongnh@soict.hut.edu.vn –QBE (Query By Example) –SQL (Structured Query LLanguage) Bộ mơnmơnHHệ thống thơng tin •Kếtluận ViệnnCơngCơngngh ệ thơng tin và Truy ền thơng Đạiihhọ ccBáchBáchKhoa Hà Nội 1 2 CSDL ví dụ 1 CSDL ví dụ 2 Supplier SID SNAME SIZE CITY Student Takes Enrol S1 Dustin 100 London SupplyProduct Id Name Suburb SID SNO SID Course S2 Rusty 70 Paris SID PID QUANTITY 1108 Robert Kew S3 Lubber 120 London 1108 21 3936 101 S1 P1 500 S4 M&M 60 NewYork 3936 Glen Bundoora 1108 23 1108 113 S1 P2 400 S5 MBI 1000 NewOrlean 8507 NooarmanBuudooandoora 8507 23 8507 101 S1 P4 100 S6 Panda 150 London 8452 Mary Balwyn 8507 29 S2 P3 250 S2 P4 50 Course Subject Product S3 P1 300 PID PNAME COLOR No Name Dept No Name Dept S3 P2 350 P1 Screw red 113 BCS CSCE 21 Systems CSCE S3 P6 200 P2 Screw green S4 P1 10 101 MCS CSCE 23 Database CSCE P3 Nut red S5 P2 200 29 VB CSCE P4 Bolt blue 18 Algebra Maths P5 Plier green 3 4 P6 Scissors blue Đặt vấn đề: các câu hỏi Câu hỏi (tiếp) Student • Tìm các sinh viên Id Name Suburb •Tìm tên của các sinh Student 1108 Robert Kew đăng ký khố học 3936 Glen Bundoora viên nào sống ở Id Name Suburb 8507 Norman Bundoora Bundoora 1108 Robert Kew cĩ mã số 113 8452 Mary Balwyn – Tìm các bộ của bảng 3936 Glen BdBundoora – Tìm các giá trị SID Enrol Student cĩ Suburb = 8507 Norman Bundoora trong bảng Enrol cĩ SID Course Bundoora 8452 Mary Balwyn Course tương ứng 3936 101 là 113 1108 113 – Đưa ra các giá trị của thuộc tính Name của – Đưa các bộ của 8507 101 các bộ này bảng Student cĩ Course SID trong các giá No Name Dept trị tìm thấy ở trên 113 BCS CSCE 5 101 MCS CSCE 6 19 1
1/30/2012 Phân loại các ngơn ngữ truy vấn • Ngơn ngữđạisố –1câuhỏi=1tập các phép tốn trên các quan hệ – Đượcbiểudiễnbởimộtbiểuthức đạisố (quan hệ) Ngggơn ngữ đại số quan hệ • Ngơnngữ tính tốnvị từ –1câuhỏi=1mơtả củacácbộ mong muốn – Được đặctả bởimộtvị từ mà các bộ phảithoả mãn –Phânbiệt2lớp: •ngơnngữ tính tốn vị từ biếnbộ •ngơnngữ tính tốn vị từ biếnmiền 7 8 Tổng quan Phân loại các phép tốn đại số quan hệ •Gồm các phép tốn tương ứng vớicác • Phép tốn quan hệ thao tác trên các quan hệ –Phép chiếu (projection) •Mỗiphéptốn –Phép chọn (selection) – Đầuvào:một hay nhiềuquanhệ –Phép kết nối (join) – Đầu ra: một quan hệ – Phép chia (division) •Biểuthức đạisố quan hệ =chuỗicác •Phép tốn tập hợp phép tốn –Phép hợp (union) •Kếtquả thựchiệnmộtbiểuthức đạisố là – Phép giao (intersection) mộtquanhệ –Phép trừ (difference) • Đượccàiđặttrongphầnlớncáchệ CSDL –Phép tích đề-các (cartesian product) hiệnnay 9 10 Phép tốn tập hợp Phép hợp • Đ/n: gồmcácbộ thuộcítnhất1trong2 • Định nghĩa: Quan hệ khả hợp quan hệđầuvào –2 quan hệ rvàsđượcgọilàkhả hợp •2 quan hệ đầu vào phải là khả hợp nếu chúng đượcxácđịnh trên cùng 1 •Cú pháp: R = R  R miền ggáiá trị 1 2 R1 R1  R2 R2 –r xác định trên D1x D2 x x Dn Kết quả Subject1 Subject2 –s xác định trên D’1x D’2 x x D’m Name Course – D = D’ và n=m Name Course Systems BCS i i Systems BCS Name Course Database BCS Database BCS  DataMining MCS Database MCS Database MCS Writing BCS Algebra MCS Algebra MCS DataMining MCS 11 Writing BCS12 20 2
1/30/2012 Phép giaoPhép giao Phép trừ • Đ/n: gồm các bộ thuộc cả hai quan • Đ/n: gồmcácbộ thuộcquanhệ thứ nhấtnhưng hệ đầu vào khơng thuộcquanhệ thứ hai – 2 quan hệ phảilàkhả hợp •Cúpháp: R1 R2 •Cúpháp:R1 \R2 hoặc R1 -R2 R1  R2 R1 R1 \ R2 R1 R2 R2 Subject1 Subject2 Subject1 Subject2 Kết quả Name Course Name Course Name Course Name Course Kết quả Name Course Systems BCS DataMining MCS Systems BCS DataMining MCS Name Course Systems BCS Database BCS  Database MCS Database BCS \ Database MCS Database BCS Database MCS Database MCS Systems BCS Database MCS Systems BCS Algebra MCS Algebra MCS Writing BCS Algebra MCS Writing BCS 13 14 Phép tích Đề cáccác Ví dụ phép tích Đề cáccác • Đ/n: là kếtnốigiữatừng bộ của Student Sport Id Name Suburb SportID Sport quan hệ thứ nhấtvớimỗibộ của 1108 Robert Kew XX 05 Swimming quan hệ thứ hai 3936 Glen Bundoora 09 Dancing 8507 Norman Bundoora •Cú pháp: R = R x R 8452 Mary Balwyn 1 2 Student_ Sport Id Name Suburb SportID Sport a x 1108 Robert Kew 05 Swimming a y a 3936 Glen Bundoora 05 Swimming b x b x b y 8507 Norman Bundoora 05 Swimming c XX y d c x 8452 Mary Balwyn 05 Swimming c y d x 1108 Robert Kew 09 Dancing d y 3936 Glen Bundoora 09 Dancing 8507 Norman Bundoora 09 Dancing 15 8452 Mary Balwyn 09 Dancing 16 Phép chiếu Phép chọn • Đ/n: Lựachọncácbộ trong mộtquanhệ thoả mãn điềukiệnchotrước. • Đ/n: Lựa chọn một số thuộc tính từ một quan hệ. •Cúpháp:  condition ()R •Cúpháp: AA1, 2, ()R R1 R2 R2 C1 C2 C3 C4 C5 C2 C5 R3 R3 R4  Ví dụ: đưa ra danh sách tên củatấtcả các sinh •Vídụ: đưa ra danh sách những sinh viên viên sống ở Bundoora Student Student  suburb "Bundoora ()Student  name ()Student Id Name Suburb Id Name Suburb Name Id Name Suburb 1108 Robert Kew 1108 Robert Kew Robert 3936 Glen Bundoora 3936 Glen Bundoora 3936 Glen Bundoora Glen 8507 Norman Bundoora 8507 Norman Bundoora Norman 8507 Norman Bundoora 8452 Mary Balwyn 8452 Mary Balwyn Mary 17 18 21 3
1/30/2012 Phép chọn - Điều kiện ? Ví dụ: chọn và chiếu • Điều kiện chọn cịn gọi là biểu thức • Đưaratêncủacácsinhviênsống ở chọn. Bundoora •Biểu thức chọn F: một tổ hợp logic của các tốn hạng. Mỗi tốn hạng là  name ( suburb "BundooraStudent) một phép so sánh đơn giản giữa 2 Student biến là hai thuộc tính hoặc giữa 1 Id Name Suburb biến là 1 thuộc tính và 1 giá trị hằng. 1108 Robert Kew Name Glen – Các phép so sánh trong F: , , , , , 3936 Glen Bundoora 8507 Norman Bundoora Norman – Các phép tốn logic trong F: , ,  8452 Mary Balwyn 19 20 Phép kết nối (join) 2 quan hệ r và s Phép kết nối VíVí dụ: •Kháiniệmghépbộ:u=(a1, ,an);v=(b1, ,bm) • Đưaradanhsáchcácsinhviênvà (u,v) = (a , ,a ,b , ,b ) 1 n 1 m mã khố học mà sinh viên đĩtham •Phépkếtnối2quanhệ thựcchất là phép ghép các Student Enrol cặpbộ của2quanhệ thỏamãn1điềukiệnnàođĩ gia Id SID Student Enrol trên chúng. Id Name Suburb SID Course • Biểu thức kết nối là phép hội của các tốn hạng, 1108 RbRober t Kew 3936 101 Id=SID mỗitốnhạng là 1 phép so sánh đơngiảngiữa1 3936 Glen Bundoora 1108 113 thuộctínhcủaquanhệ rvà1thuộctínhcủaquan 8507 Norman Bundoora 8507 101 hệ s. 8452 Mary Balwyn •Cúpháp: R R 1 join _ condition 2 Kết quả SID Id Name Suburb Course 1108 1108 Robert Kew 113 a r r x a r x 3936 3936 Glen Bundoora 101 b r s y b r x 8507 8507 Norman Bundoora 101 c v t z 21 22 Phép kết nối bằng-ng-kkết nối tự nhiên Phép kết nối tự nhiên -Ví- Ví dụ: • Định nghĩa: Nếuphépsosánhtrong điềukiệnkếtnốilàphépsosánh bằng thì kếtnốigọilàkếtnốibằng • Định nghĩa: Phép kếtnốibằng trên Takes Enrol các thuộc tính cùng tên của 2 quan SID SNO SID Course SID SOSNO Course hệ và sau khi kếtnối1thuộctính 1108 21 3936 101 1108 21 113 trong 1 cặpthuộc tính trùng tên đĩ 1108 23 * 1108 113 1108 23 113 8507 23 8507 101 8507 23 101 sẽ bị loạikhỏiquanhệ kếtquả thì 8507 29 8507 29 101 phép kếtnốigọilàkếtnốitự nhiên • Cú pháp phép kếtnốitự nhiên: R1 * R 2 23 24 22 4
1/30/2012 Ví dụ: chọn, chiếu, kết nối Phép kết nối ngồi • Đưa ra tên của các sinh viên sống ở Bundoora và mã khố học mà sinh viên đĩ •Phép kết nối ngồi trái đăng ký: ( (Student Enrol )) a r r x a r x  name,Course suburb "Bundoo Id SID b r s y b r x c v t z c v null Stu den t Id Name SbSubur b 1108 Robert Kew 3936 Glen Bundoora Kết quả •Phép kết nối ngồi phải 8507 Norman Bundoora Name Course 8452 Mary Balwyn Glen 101 a r r x a r x Enrol SID Course Norman 101 b r s y b r x 3936 101 c v t z null s y 1108 113 null t z 8507 101 25 26 Phép kết nối ngồi VíVí dụ: Phép chiachiaPhép • Đưa ra danh sách các sinh viên và mã • Định nghĩa: Phép chia giữa1quan khố học mà sinh viên đĩ đăng ký nếucĩ hệ rbậcnvàquanhệ sbậcm Student (m<n) vớisơđồquan hệ của s là tập Enrol ID Name Suburb SID Course con củasơđồquan hệ củarlàmột 1108 Robert Kew 3936 101 tập các (n-m)-bộ sao cho khi ghép 3936 Glen Bundoora 1108 113 8507 Norman Bundoora mọibộ thuộcsvớitthìtađềucĩ 8507 101 8452 Mary Balwyn mộtbộ thuộcr Kết quả ID Name Suburb Course •Cúpháp:R=R1 :R2 1108 Robert Kew 113 3936 Glen Bundoora 101 8507 Norman Bundoora 101 8452 Mary Balwyn null 27 28 Phép chia (tiếp) Luyện tập a x •Phép hợp (Union) a y x a a z :: z b x c y •Vídụ: Đưaramơnhọc đượcdạy ở Ví dụ: tất cả các khố học Subject Course Kết quả Name Course Course Name Systems BCS BCS :: Database Database BCS MCS Database MCS Algebra MCS 29 30 23 5
1/30/2012 Luyện tập Luyện tập • Phép giao (intersection) •Phép trừ (minus) Ví dụ: Ví dụ: 31 32 Luyện tập Luyện tập •Phép tích Đề - Các (Cartesian Product) •Phép chiếu (Projection) Ví dụ: Ví dụ: 33 34 Luyện tập Luyện tập •Phép chọn (Selection) •Phép kết nối (join) Ví dụ: Ví dụ: 35 36 24 6
1/30/2012 Luyện tập Luyện tập • Phép chia (Division) •Kết nối tự nhiên (natural join) Ví dụ: 37 38 Bài tập Yêu cầu của bài tập •ChoCSDLgồm3quanhệ sau: S(Các hãng cung ứng), P (các mặthàng),SP(cácsự cung ứng). •Biểudiễncáctruyvấnsaubằng đạisố quan hệ: – Đưa ra danh sách các mặt hàng màu đỏ –ChobiếtS#của các hãng cung ứng mặthàng 'P1' hoặc 'P2' –LiệtkêS#của các hãng cung ứng cả hai mặt hàng 'P1' và 'P2' – ĐưaraS#của các hãng cung ứng ít nhấtmột mặt hàng màu đỏ – ĐưaraS#của các hãng cung ứng tấtcả các mặthàng. 39 40 Lời giải của bài tập Bài tập về nhà • Cho các quan hệ sau: Supplier SupplyProduct sid sname size city sid pid quantity S1 Dustin 100 London S1 P1 500 S2 Rusty 70 Paris S1 P2 400 S3 Lubber 120 London S1 P3 100 S2 P2 200 Product S3 P4 100 pid pname colour S2 P3 155 P1 Screw red P2 Screw green P3 Nut red P4 Bolt blue 41 42 25 7
1/30/2012 Bài tập về nhà Bài tập về nhà •Biểudiễncáctruyvấnsaubằng biểu thức đạisố quan hệ: – Đưara{sid}của các hãng cung ứng tất cả các mặt hàng màu đỏ – Đưa ra {sid,sname,size,city} củacác Supplier cĩ trụ sở tạiLondon – Đưara{sname}của các hãng cung ứng ít nhấtmộtmặthàngmàuđỏ hoặcmàu – Đưara{pname } củatấtcả các mặt xanh hàng – Đưara{sname}của các hãng cung ứng – Đưara{sid}của các Supplier cung cấp ít nhất1mặthàngmàuđỏ và mộtmặt mặthàngP1hoặcP2 hàng màu xanh – Đưara{sname}của các Supplier cung – Đưara{sid}của các hãng khơng cung cấpmặthàngP3 ứng mặt hàng nào – Đưara{sname}của các hãng cung ứng ít nhấtmộtmặt hàng màu đỏ 43 44 Ngơn ngữ QBE 45 46 QBE (QBE (QueryQuery ByBy ExampleExample)) Truy vấn trên một quan hệ •Làmộtngơnngữ truy vấndữ liệu •P.~ Print •Cáccâutruyvấn đượcthiếtlậpbởimột Student ID Name Suburb giao diện đồ hoạ P._x Bundoora •Phùhợpvớicáccâutruyvấn đơngiản, tham chiếu đếnítbảng •Biểu thức đại số quan hệ tương đương •Mộtsố sảnphẩm: IBM (IBM Query Management Facility), Paradox, MS.  suburb "Bundoora ()Student Access, 47 48 26 8
1/30/2012 Truy vấn trên một quan hệ (tiếp) Truy vấn trên nhiều quan hệ •Lựa chọn tất cả các cột • Đưa ra tên của các sinh viên cĩ đăng ký ít nhất mộtkhốhọc Student ID Name Suburb P. Bundoora Student ID Name Suburb Enrol SID Course _id P._name _id •Sắp xếp • Đưa ra tên các sinh viên khơng đăng Student ID Name Suburb ký mộtkhốhọcnào P. A O ( 1 ) P. A O ( 2 ) Student ID Name Suburb Enrol SID Course _id P._name  _id • AO: sắpxếptăng dần •DO: sắpxếpgiảm dần 49 50 Các tính tốn tập hợp Hộp điều kiện • Đượcsử dụng để biểu diễn • Các phép tốn: AVG, COUNT, MAX, MIN, SUM – Điềukiện trên nhiềuhơn 1 thuộctính – Điềukiện trên các trường tính tốn tập hợp •Vídụ: đưa ra tên các thành phố và số lượng sinh viên đến từ thành phố đĩ • Ví dụ: đưa ra danh sách các thành phố cĩ nhiều hơn 5 sinh viên Student ID Name Suburb _id G.P. P. C O U N T. _ i d Student ID Name Suburb Condition _id G.P. COUNT._id > 5 •G. ~ Grouping 51 52 Các thao táctácthaythay đổiiddữ liệu Tính đầy đủ của QBE •Xĩa Student ID Name Suburb •Cĩ thể biểu diễn cả 5 phép tốn đại D. 1108 số cơ sở (,,,\,x) •Thêm Student ID Name Suburb I. 1179 David Evry •Sửa Student ID Name Suburb 1179 U.Paris 53 54 27 9
1/30/2012 Định nghĩa dữ liệu trong QBE Định nghĩa dữ liệu trong QBE (tiếp) •sử dụng cùng qui cách và giao diện • Các khung nhìn đồ họa như đối với truy vấn. I.View V I. ID Name Course I.Student I. ID Name Suburb I. _idid _namename _coursecourse KEY I. Y N N TYPE I. CHAR(5) CHAR(30) CHAR(30) Student ID Name Suburb Enrol SID Course DOMAIN I. Sid SName Surb _id _name _id _course INVERSION I. Y N N 55 56 SQL (Structured Query Language) • 1975: SEQUEL –System-R • 1976: SEQUEL2 • 1978/79: SQL Ngơn ngữ SQL –System-R • 1986: chuẩn SQL-86 • 1989: chuẩn SQL-89 • 1992: chuẩn SQL-92 • 1996: chuẩn SQL-96 57 58 Các thành phần của SQL Ngơn ngữ định nghĩa dữ liệu •Ngơnngữđịnh nghĩadữ liệu(Data Definition Language) •Cácthơngtinđược định nghĩabaogồm –Cấutrúccácbảng CSDL –Sơđồquan hệ –Cácmối liên hệ củadữ liệu –Kiểudữ liệuhaymiềngiátrị củamỗithuộc –Quytắc, ràng buộcápđặtlêndữ liệu tính • NơNgơnngữ thao tác dữ liệu (Data Manipulation Language) –Cácràng buộctồnvẹn –Thêm,xố,sửadữ liệutrongCSDL –Cácchỉ sốđốivớimỗibảng –Truyvấndữ liệu – Thơng tin an tồn và ủyquyền đốivớimỗi •Ngơnngữđiềukhiểndữ liệu(Data Control Language) bảng –Khaibáobảomật thơng tin –Cấutrúclưutrữ vậtlýcủamỗibảng trên đĩa –Quyềnhạncủangười dùng trong khai thác CSDL  Đượcbiểudiễnbởicáclệnh định nghĩadữ liệu 59 60 28 10
1/30/2012 Quy ước đặttttêênn vàvàkikiểuuddữữ liliệu Cú phápCú pháp •Tạo bảng •Quy ước đặt tên – 32 ký tự: chữ cái, số, dấu _ CREATE TABLE tab( •Kiểu dữ liệu (SQL-92) col1 type1(size1)[NOT NULL], , –CHAR(n) col2 type2(size2)[NOT NULL], , – VARCHAR(n) –Int [CONSTRAINT clause] –Numeric(p,d) – Real, double ); –float(n) –Date •Xố bảng –time DROP TABLE tab 61 62 Tạo bảng VíVí dụ: Tạo bảng VíVí dụ (tiếp) CREATE TABLE SupplyProduct( CREATE TABLE Supplier( sid char(4) NOT NULL, sid char(4) NOT NULL, pid char(4) NOT NULL, sname varchar(30) NOT NULL, quantity smallint, size smalli nt, primary key(sid,pid), city varchar(20), foreign key(sid) references Supplier(sid), CONSTRAINT KhoachinhS primary key(sid) foreign key(pid) references Product(pid), check(quantity >0) ); ); 63 64 Kiểu ràng buộc ThThêêm/xom/xốá/s/sửa cộttccủaaccácác bảng •Ràngbuộctồnvẹn(RBTV)về giá •Thêm trị miền ALTER TABLE ADD COLUMN [NOT NULL]; CONSTRAINT •Xố CHECK ALTER TABLE •RBTVvề khố ngoạihayphụ thuộc DROP COLUMN ; •Sửa tồntại ALTER TABLE CONSTRAINT FOREIGN KEY (fk1,fk2, ) CHANGE COLUMN TO ; REFERENCES tab(k1,k2); 65 66 29 11
1/30/2012 Ví dụ: ThThêêm/xĩa cm/xĩa cácác rràngàngbu ộc • ALTER TABLE SupplyProduct ADD •Thêm COLUMN price real NOT NULL; ALTER TABLE • ALTER TABLE SupplyProduct DROP ADD CONSTRAINT COLUMN price; • ALTER TABLE Supplier CHANGE COLUMN sname TO varchar(20); • Xĩa ALTER TABLE DROP CONSTRAINT 67 68 Truy vấn khơng điều kiện Ngơn ngữ truy vấn dữ liệu trên một bảng • Cú pháp câu lệnh SQL: • Tìm thơng tin từ các cộtcủabảng SELECT ColumnName, ColumnName, FROM TableName; SELECT [DISTINCT] |*| | SELECT * FROM FROM TableName; [WHERE ] •Ví dụ [GROUP BY [HAVING ]] SELECT Name [ORDER BY [ASC|DESC]] FROM Student; Student [UNION |INTERSECT| MINUS ]  name 1108 Robert Kew Robert 3936 Glen Bundoora Glen 8507 Norman Bundoora Norman 69 70 8452 Mary Balwyn Mary Truy vấn khơng điều kiện trên một bảng Truy vấn cĩ điều kiện trên 1 bảng Một số ví dụ khác: •Chọn các bản ghi (dịng) • Đưa ra tên của các mặt hàng SELECT ColumnName,ColumnName, SELECT pname FROM Product; FROM TableName • Đưa ra tên khác nhau của các mặt hàng WHERE condition_expression; SELECT DISTINCT pname FROM Product; •Vídụ • Đưa ra tồn bộ thơng tin về các hãng cung ứng SELECT * SELECT * FROM Supplier; FROM Student WHERE suburb=‘‘Bundoora’’ ; • Đưa ra mã số hãng cung ứng, mã mặt hàng được Student cung ứng và 10 lần số lượng mặt hàng đã được  ()Student cung ứng Id Name Suburb suburb "Bundoora SELECT sid, pid, quantity*10 1108 Robert Kew Id Name Suburb FROM SupplyProduct; 3936 Glen Bundoora 3936 Glen Bundoora 8507 Norman Bundoora 8507 Norman Bundoora 71 8452 Mary Balwyn 72 30 12
1/30/2012 Truy vấn cĩ điều kiện trên 1 bảng Biểu diễn điều kiện lựa chọn Một số ví dụ khác: • Đưaratêncủa các hãng cung ứng cĩ • Các phép tốn quan hệ: =, !=, , = trụ sở tạiLondon • Các phép tốn logic: NOT, AND, OR SELECT sname FROM Supplier •Phéptốnphạmvi: BETWEEN, IN, LIKE WHERE cityy; = ‘London’; – Kiểu dữ liệu số • Đưaramãsố và tên củacáchãng •attrBETWEEN val1 AND val2 ( (attr>=val1) and cung ứng nằm ở London và cĩ số (attr 75; _,? (thay thế cho 1 ký tự bấtkỳ), *hay%(thay thế cho 1 xâu ký tự bấtkỳ) 73 74 Biểu diễn điều kiện lựa chọn - Biểu diễn điều kiện lựa chọn - Ví dụ: Ví dụ (tiếp) • Đưa ra thơng tin của các hãng cung ứng cĩ số • Đưa ra thơng tin của hãng sản xuất nhân viên trong khoảng từ 100 đến 150 SELECT * FROM Supplier cĩ trụ sở đặt tại thành phố bắt đầu WHERE size BETWEEN 100 AND 150; bằng chữ New • Đưaramãsố củahãngcungứng mặthàngP1 hoặc P2 SELECT * FROM SUPPLIER –Cách 1: WHERE city LIKE ‘New%’; SELECT sid FROM SupplyProduct WHERE pid = ‘P1’ OR pid = ‘P2’; –Cách 2: SELECT sid FROM SupplyProduct WHERE pid IN (‘P1’, ‘P2’); 75 76 Truy vấn cĩ sử dụng phép tốn đổi tên Truy vấn phức tạp trên nhiều bảng •SQLchophépđổitêncácbảng và các cột trong mộtcâutruyvấn(saumệnh đề • Điềukiệnkết nối SELECT và FROM) sử dụng cấutrúc: SELECT T1.C1,T1.C2,T2.C1,T2.C4, • AS FROM T1, T2 – Đưaratênvàsố nhân viên của các hãng WHERE condition_expression cung ứng ở Paris • Ví dụ: đưa ra danh sách mã sinh vien (Id), SELECT sname AS HangOParis, size AS SoNhanVien tên sinh viên (Name), thành phố (Suburb), FROM Supplier mã khố học (Course) mà các sinh viên đã WHERE city = ‘Paris’; đăng ký SELECT SID , Stud.Name as SName, SELECT Id, Name, Suburb,Course Sub.Name as Subject FROM Student,Enrol FROM Student as Stud,Takes, WHERE Id=SID Subject as Sub WHERE (Id=SID) and (SNO = No) 77 78 31 13
1/30/2012 Truy vấn phức tạp trên nhiều bảng Loạiitrtrừ cáccácbbả nnghighitrùng nhau Một số ví dụ khác: • Đưaratêncủa hãng cĩ cung ứng mặt •Từ khố DISTINCT hàng P1 SELECT DISTINCT , , SELECT sname FROM , , FROM Supplier S, SupplyProduct SP WHERE S.sid = SP.sid AND SP.pid = ‘PP1’; • Ví dụ: đưa ra danh sách tên các khoa • Đưaratênvàmãsố của hãng cung ứng ít (dept)tương ứng vớicáckhốhọc nhấtmộtmặt hàng màu đỏ (Course). Mỗigiátrị chỉ hiệnthị một SELECT sname, sid lần FROM Supplier S, SupplyProduct SP, Product P SELECT DISTINCT Dept WHERE S.sid = SP.sid AND P.pid = SP.pid AND P.colour = ‘red’; FROM Course 79 80 Tìm kiếm cĩ sắp xếp PhPhâânn nhĩmnhĩm ccácácb ảnnghighi kếttququảả •Phânnhĩmcácbảnghikếtquả theo giá trị của1 •Sắpxếpcácbảnghikếtquả theo mộtthứ hoặc nhiềuthuộctính SELECT , , tự cho trước FROM , , SELECT , , [WHERE ] FROM , , [GROUP BY , , ] [WHERE ] • Cột đượcchỉ ra trong mệnh đề GBGroupBy đượcsử ORDER BY | [ASC|DESC] dụng làm cơ sởđểchia nhĩm. Cộtnàycũng bắt •Vídụ: đưaradanhsáchtêncácsinhviên buộcphải đượcchỉ ra trong mệnh đề Select theo thứ tự tăng dần •Vídụđưa ra tên các sinh viên nhĩm theo thành phố của sinh viên đĩ SELECT Name SELECT Suburb, FROM Student SELECT Suburb, Name Count(Id) ORDER BY Name ASC FROM FROM Student Student 81 GROUP BY GROUP BY 82 Suburb Suburb ĐĐiiềuukikiệnnhihiểnnththịị ccácác bảnnghighi kếttququảả CCácácphép phéptốn tốnt ậập hp hợpp:: UNION, MINUS, INTERSECT •Lựa chọn các bản ghi kết quả để hiển thị •Vídụ: đưa ra danh sách tên các mơn học khơng cĩ sinh viên nào tham dự SELECT , , SELECT DISTINCT Subject.Name FROM , , FROM Subject MINUS [WHERE ] SELECT DISTINCT Subject.Name HAVING FROM Student, Takes, Subject WHERE Stud ent.I d = Takes. SID an d Takes. SN O = SbjSubject.No •Vídụ: đưa ra tên các thành phố cĩ nhiều •Tìm sid của hãng cung ứng đồng thời 2 mặt hàng hơn 3 sinh viên P1 và P2 SELECT Suburb, COUNT(ID) SELECT sid FROM SupplyProduct WHERE pid = ‘P1’ INTERSECT FROM Student SELECT sid FROM SupplyProduct WHERE pid = ‘P2’ GROUP BY Suburb •Tìm mã số của hãng khơng cung ứng mặt hàng HAVING COUNT(ID) > 3 nào SELECT sid FROM Supplier MINUS SELECT sid FROM SupplyProduct 83 84 32 14
1/30/2012 CCácácccââuu truy vấnnllồng nhau CCácác ccââuu truy vấnnllồng nhau (tiếp) •Kiểm tra thành viên tập hợp với IN •Làtrường hợp các câu truy vấn(con) đượcviết và NOT IN: lồng nhau •Thường đượcsử dụng để – Đưa ra mã số của các hãng cung ứng –Kiểmtra thànhviên tậphợp(IN, NOT IN) đồng thời 2 mặt hàng P1 và P2: –So sánhtậphợp(>ALL, >=ALL, =ALL(SELECT SIZE FROM Supplier); – Đưa ra sid của các hãng khơng cung –Kiểmtra cácbảng rỗng (EXISTS hoặc NOT EXISTS) ứng mặt hàng P3: •Cáctruy vấncon lồng nhau thơng qua mệnh đề SELECT sid FROM SupplyProduct WHERE WHERE sid NOT IN (SELECT sid From SupplyProduct SP2 WHERE SP2.pid = ‘P3’); 85 86 CCácác ccââuu truy vấnnllồng nhau (tiếp) CCácác ccââuu truy vấnnllồng nhau (tiếp) • So sánh tập hợp: Sử dụng các phép tốn , ≥,≤,=,≠ kèm với các mệnh đề ANY •Kiểm tra tập hợp rỗng với EXISTS và và ALL – Đưa ra tên của các hãng cĩ số nhân viên NOT EXISTS đơng nhất: – EXISTS(câu truy vấn con): nhận giá trị SELECT sname FROM Supplier đúng khi câu truy vấn con cho ra kết WHERE size ≥ ALL(SELECT size FROM Supplier) quả là một quan hệ khác rỗng – Đưa ra sid của hãng cung ứng một mặt hàng với số lượng bằng ít nhất 1 trong số lượng – NOT EXISTS(câu truy vấn con): nhận các mặt hàng được cung ứng bởi S2 giá trị đúng khi câu truy vấn con cho ra SELECT sid FROM SupplyProduct kết quả là một quan hệ rỗng WHERE sid ≠ ‘S2’ AND quantity = ANY(SELECT quantity FROM SupplyProduct SP2 WHERE SP2.sid = ‘S2’); 87 88 CCácác ccââuu truy vấnnllồng nhau (tiếp) CCácáchàm hàmth ưư viviện • Hàm tính tốn trên nhĩm các bảnghi • Đưa ra thơng tin của các nhà cung cấp đã –MAX/MIN cung ứng ít nhất một mặt hàng –SUM SELECT * FROM Supplier S – AVG WHERE EXISTS (SELECT sid FROM –COUNT SupplyProduct SP WHERE S.sid = SP.sid); • Hàm tíhính tốn ttrên bảnghi • Đưa ra thơng tin của các nhà cung cấp – Hàm tốn học: ABS, SQRT, LOG, EXP, SIGN, ROUND khơng cung ứng mặt hàng nào –Hàmxử lý xâu ký tự: LEN, LEFT, RIGHT, MID SELECT * FROM Supplier S –Hàmxử lý thờigian: DATE, DAY, MONTH, WHERE NOT EXISTS (SELECT * FROM YEAR, HOUR, MINUTE, SECOND SupplyProduct SP WHERE S.sid = SP.sid); – Hàm chuyển đổikiểugiátrị: FORMAT 89 90 33 15
1/30/2012 Một số ví dụ với các hàm thư viện Một số truy vấn phức tạp • ĐưaratêncủahãngS1vàtổng số mặt hàng mà hãng đĩ cung ứng SELECT sname, SUM(quantity) • Cĩ bao nhiêu mặt hàng khác nhau được cung ứng FROM Supplier S, SupplyProduct SP SELECT COUNT(DISTINCT pid) FROM SupplyProduct; WHERE S.sid = SP.sid AND S.sid = ‘S1’ •Cĩ tổng cộng bao nhiêu nhân viên làm cho các GROUP BY sname; hãng ở Paris • Đưaramãsố cáchãngcungứng và số lượng trung bình các mặt SELECT SUM(size) FROM Supplier hàng được cung ứng bởitừng hãng WHERE city = ‘Paris’; SELECT sid, AVG(quantity) FROM SupplyProduct • Đưa ra số lượng mặt hàng trung bình mà hãng S1 cung ứng GROUP BY sid; SELECT AVG(quantity) • Đưaramãsố cáchãngcungứng mà số lượng mặt hàng trung FROM SupplyProduct bình được cung cấpbởihãngđĩ là trong khoảng từ 75 đến 100 WHERE sid = ‘S1’; SELECT sid, AVG(quantity) FROM SupplyProduct GROUP BY sid HAVING AVG(quantity) BETWEEN 75 AND 100 91 92 Các câu lệnh cập nhật dữ liệu Các câu lệnh cập nhật dữ liệu •Thêm •Xĩa dữ liệu:  INSERT INTO table[(col1,col2, )] DELETE FROM VALUES (exp1,exp2, ) INSERT INTO table[(col1,col2, )] WHERE ; SELECT col1, col2, • Ví dụ: FROM tab1, tab2, DELETE FROM SupplyProduct WHERE WHERE sid = ‘S4’; •Ví dụ DELETE FROM Student INSERT INTO Student(Id, Name, Suburb) WHERE Suburb = ‘‘Bundoora’’; VALUES (‘‘1179’’,‘‘David’’,‘‘Evr’’) 93 94 Các câu lệnh cập nhật dữ liệu •Sửa đổi dữ liệu: –UPDATE SET ( = Giá trị mới , ) [WHERE ]; •Ví dụ: – Hãng S1 chuyển tới Milan UPDATE Suppli er SET ci ty = ‘Milan ’ WHERE sid = ‘S1’; –Tất cả các mặt hàng được cung cấp với số lượng nhỏ hơn 100 đều tăng số lượng lên 1.5 lần UPDATE SupplyProduct SET quantity = quantity * 1.5 WHERE quantity < 100; 95 96 34 16
1/30/2012 Lời hay ý đẹp "Người kém thơng minh nhưng say sưavớicơngviệc, tiếnmạnh và xa hơn người cực thơng minh mà lãnh đạmvớicơngviệc". J. Deval 97 35 17
1/30/2012 Nội dung Lý thuyết thiết kế •Tổng quan về thiết kế CSDLQH cơ sở dữ liệu quan hệ •Phụ thuộc hàm • Phép tách các sơ đồ quan hệ (SĐQH) Nguyễn Hồng Phương • Các dạng chuẩn đối với các SĐQH phuongnh@soict.hut.edu.vn Bộ mơnmơnHHệ thống thơng tin ViệnnCơngCơngngh ệ thơng tin và Truy ền thơng Đạiihhọ ccBáchBáchKhoa Hà Nội 1 2 Tổng quan về thiết kế CSDLQH Các vấn đề đối với CSDL VD •Vấn đề củamộtsơđồquan hệđượcthiết • Dư thừadữ liệu: Hãng nào cung ứng nhiềuhơn1 mặthàngthìthơngtincủahãngđĩsẽ bị lặplại kế chưatốt: trong bảng (VD S1), mặthàngđượccungứng bởi Giả sử ta cầnmộtcơ sở dữ liệulưutrữ thơng tin nhiềuhãngcũng bị lặplại (VD Screw) về các hãng cung ứng. Sơđồquan hệđượcthiết • Dị thường dữ liệukhithêm:Nếucĩmộthãng kế trong đĩtấtcả các thuộctínhcầnthiết được chưa cung cấpmặthàngnào,vậygiátrị cho thuộc lưu trong đúng 1 quan hệ: tính product và qqyuantity trong bộ dữ liệumới được Suppliers(sid, sname, city, numofemps, product, quantity) thêm vào sẽ khơng đượcxácđịnh • Dị thường dữ liệukhixĩa:Nếumộthãngchỉ cung cấp1mặthàng,nếutamuốn xĩa thơng tin sid sname city NOE product quantity về sự cung cấpnàythìtasẽ mất thơng tin về hãng S1 Smith London 100 Screw 50 cung cấp • Dị thường dữ liệukhisửa đổi: Do thơng tin bị S1 Smith London 100 Nut 100 lặplạinênviệcsửa đổi1bộ dữ liệucĩthể dẫn đến S2 J&J Paris 124 Screw 78 việc khơng nhất quán trong dữ liệuvề mộthãng n ếusơ sĩt khơng sửa đổitrêntồnbộ các bộ giá S3 Blake Tokyo 75 Bolt 100 3 trị liên quan đếnhãngđĩ 4 Đề xuất giải pháp MMục đích củaachuchuẩnnhohốá •Nếusơđồtrên đượcthaythế bằng •Xác định được1tậpcáclược đồ quan 2sơđồquan hệ hệ cho phép tìm kiếm thơng tin một –Supp(sid, sname, city, numofemps) cách dễ dàng, đồng thời tránh được dư thừadữ liệu –Supply(sid, product,quantity) • Hướng tiếp cận: Một trong những kỹ Thì tấtcả các vấn đề nêu ở trên sẽ thuật đượcsử dụng là Tách các lược đượcloạibỏ. Tuy nhiên khi tìm đồ quan hệ cĩ vấn đề thành những kiếmdữ liệu thì chúng ta phảithực lược đồ quan hệ chuẩnhơn. Phụ thuộc hiệnkếtnối2bảng chứ khơng chỉ là hàm cĩ thể đượcsử dụng để nhân biết chọnvàchiếutrên1bảng nhưở các lược đồ chưachuẩnvàđề xuất cách thiếtkếttrước hướng cảitiến 5 6 36 1
1/30/2012 Phụ thuộc hàm Ví dụ • Định nghĩa: Cho R(U) là mộtsơđồ •Ví dụ 1: ABC quan hệ vớiUlàtậpthuộctính a1 b1 c1 a2 b2 c2 {A1,A2, ,An}. X, Y là tậpconcủa a3 b1 c1 U. Nĩi rằng X xác địnhYhayYlà a4 b3 c2 phụ thuộc hàmvào X ( X Y) nếuvới1quanhệ rxácđịnh trên •A B, A C, B C R(U) và 2 bộ bấtkỳ t1,t2 thuộcr •Vídụ 2: trong cơ sở dữ liệumẫu dùng trong mà t [X] = t [X] thì ta cĩ t [Y] = chương 3, ta cĩ bảng S, vớimỗigiátrị củasid 1 2 1 đềutồntạimộtgiátrị tương ứng cho sname, t2[Y] city và status. Do đĩtacĩsid sname, sid city, sid status 7 8 Hệ tiên đề Amstrong đối với phụ thuộc hàm Hệ quả của hệ tiên đề Amstrong Cho •Luật hợp (union) – R(U) là 1 sơ đồ quan hệ, U là tập các thuộc tính. Nếu X Y, X Z thì X YZ. – X,Y,Z,W  U (Ký hiệu: XY = X  Y) •Luật tựa bắc cầu (pseudotransitivity) • Phản xạ (reflexivity) Nếu X Y, WY Z thì XW Z. Nếu Y  X thì X Y •Luật tách (decomposition) •Tăng trưởng (augmentation) Nếu X Y, Z  Y thì X Z Nếu X Y thì XZ YZ •Bắc cầu (transitivity) Nếu X Y, Y Z thì X Z 9 10 Ví dụ Bao đĩng của một tập phụ thuộc hàm •Vídụ 1: • Định nghĩa: Cho F là mộttậpphụ thuộc Cho tậpphụ thuộchàm{AB C, C A} hàm. Bao đĩng củaFkýhiệulàF+ là tập Chứng minh: BC ABC lớnnhấtchứacácphụ thuộchàmcĩthể C ABC AB đượcsuyratừ các phụ thuộchàmtrongF AB CAB ABC • Bao đĩng của một tập phụ thuộc hàm cĩ BC AB, AB ABC BC ABC thể rấtlớn, sẽ chi phí rấttốnkémchoviệc •Vídụ 2: tìm kiếmbaođĩng của1tậpphụ thuộc Cho lược đồ quan hệ R(ABEIJGH) và tập hàm. Do đĩ để thuậntiệnchoviệckiểmtra phụ thuộchàmF={AB E, AG J, BE I, xem mộtphụ thuộchàmcĩđượcsuydiễn E G, GI H} từ mộttậpphụ thuộchàmcĩsẵnkhơng, Chứng minh: AB GH ngườitacĩthể sử dụng Bao đĩng của1tập 11 thuộctính 12 37 2
1/30/2012 Bao đĩng của một tập các thuộc tính Thuật tốn 1: Tìm bao đĩng của một tập thuộc tính đối với tập các phụ thuộc hàm đối với tập phụ thuộc hàm • Định nghĩa: Cho mộtlược đồ quan hệ • Vào:TậphữuhạncácthuộctínhU,tậpcácphụ R(U), F là mộttậpphụ thuộchàmtrên thuộchàmFtrênU U. X là tậpconcủaU.Baođĩng củatập X  U thuộctínhXkýhiệulàX+ là tậptấtcả • Ra: X+ các thuộctínhđượcxácđịnh hàm bởiX • Thuật tốn thơng qua tập F B0 X0 = X i i i-1 + + B Tính X từ X X ={A U| X A F } Nếu  Y Z F và Y  Xi-1 và A Z và A Xi-1 •Tacĩthể thấylàđịnh nghĩavề bao đĩng thì Xi = Xi-1  A củamộttậpthuộctínhdựatrênbao ngược lại, Xi = Xi-1 đĩng củatậpphụ thuộchàm.Trênthực Nếu Xi Xi-1 tế,ngườitađưaramộtthuậttốnđể thì lặp Bi giúp xác định bao đĩng củamộttập ngược lai, chuyển Bn thuộctínhdễ dàng hơn Bn X+ = Xi 13 14 Ví dụ Bổ đề • Cho R(U) , U = {A, B, C, D, E, F} •X Y đượcsuydiễntừ hệ tiên đề + F = {AB C, BC AD, D E, CF B} Amstrong khi và chỉ khi Y  X •Chứng minh: Tính (AB)+ –Giả sử Y=A1 An,vớiA1, ,An là các • Thực hiện: thuộc tính và YX+ 0 + –Bước 0: X = AB –Từđịnh nghĩaX ta cĩ X Ai.Ápdụng –Bước 1: X1 = ABC ( do AB C) tiên đề Amstrong cho mọii,suyraX Y nhờ luậthợp. –Bước 2: X2 = ABCD (do BC AD) –Ngượclại, giả sử cĩ X Y, áp dụng hệ tiên –Bước 3: X3 = ABCDE (do D E) đề Amstrong cho mỗii,tacĩX Ai,Ai Y –Bước 4: X4 = ABCDE nhờ luậttách.TừđĩsuyraYX+ 15 16 KhốKhố Thuật tốn 2: Tìm khố tối thiểu • Định nghĩa: Cho lược đồ quan hệ R(U), F là • Vào: U = {A1, A2, , An} , F mộttập các phụ thuộchàmxácđịnh trên U. K • Ra:khốtốithiểuKxácđịnh được là mộttậpconcủaU,Kđượcgọilàkhố tối trên U và F thiểucủaRnếunhư –K Ulàmộtphụ thuộchàmtrongF+ • Thuật tốn 0 0 –Vớimọitậpconthựcsự K’ củaKthìK’ U khơng B K = U thuộcF+ i i-1 B Nếu (K \{Ai}) U •Vớinhững gì ta đã đề cậptrongphầnbao i i-1 thì K = K \{Ai} đĩng ở trên, ta cĩ thể nĩi, để thỏamãnlà i i-1 mộtkhốtốithiểuthìK+ =UvàKlàtập ngược lại, K = K thuộctínhnhỏ nhấtcĩtínhchấtnhư vậy Bn+1 K = Kn 17 18 38 3
1/30/2012 Ví dụ Nhận xét vềề phphụụ thuthuộcchhàmàm • ChoU={A,B,C,D,E} •F={AB C, AC B, BC DE}. TÌm mộtkhốtốithiểucủa •Từ mộttậpcácphụ thuộchàmcĩthể một quan hệ rxácđịnh trên U và F •Thựchiện suy diễnracácphụ thuộc hàm khác •B0:K0=U=ABCDE •Trongmộttậpphụ thuộchàmchosẵn •B1:Kiểm tra xem cĩ tồntạiphụ thuộchàm(K0\{A}) U (BCDE U) hay khơng. Ta cầnphảisử dụng thuậttốn1để cĩ thể cĩ các phụ thuộchàmbị coi là kiểm tra điều kiện tương đương là (BCDE)+ cĩ bằng U khơng. (BCDE)+=BCDE,khácU.VậyK1 =K0 =ABCDE dư thừa •B2:Tương tự,thử loạibỏ BrakhỏiK1 ta cĩ (ACDE)+ = ABCDE = U. VậyK2 =K1 \{B}=ACDE • Làm thế nào để cĩ đượcmộttập •B3:K3 =ACDE •B4:K4 =ACE phụ thuộchàmtốt? •B5:K5 =AC •VậyAClàmộtkhốtốithiểumàtacầntìm 19 20 TTậppphphụụ thuthuộcchhàmàmt ươương đươđươngng Ví dụ • Định nghĩa: Tậpphụ thuộchàmFlàphủ •Cholược đồ quan hệ R(U) với U = {A, B, C, D, E, củatậpphụ thuộc hàm G hay G là phủ của F} FhayFvàGtương đương nếuF+ =G+. F={AB C, D EF, C BD} –KýhiệulàF G G={AC B, D EF, B CD} •Kiểmtratínhtương đương của2tậpphụ HỏiFvàGcĩphảilà2tậppthtương đương hay khơng? thuộc hàm •Thựchiện: B.1. Vớimỗiphụ thuộchàmY Z F, Z  Y+ (trên G) thì Y Z G+ Đốivớicácphụ thuộchàmtrongF + + + –f1=AB C. AB (đốivớiG)=ABCDEF=U.Vậyf1 thuộc Nếuvới phụ thuộchàmf F, f G thì F  G+ + G + –f2=D EF thuộcGnênchắcchắnthuộcG + + B.2. Tương tự,nếu  phụ thuộchàmg G, g F –f3=C BD. C (đốivới G) = C khơng chứaBD.Vậyf3 thì G+  F+ khơng thuộcG+ B.3. NếuF+  G+ và G+  F+ thì F G –KếtluậnFkhơngtương đương vớiG 21 22 TTậppphphụụ thuthuộcchhàmàm khkhơơngng dưư ththừa PhPhủủ ttốiithithiểuuccủaa11 tậppphphụụ thuthuộcchhàmàm • Đ/N: Tậpphụ thuộchàmFlàkhơng dư • Đ/N: F được gọi là phủ tối thiểu của 1 thừa nếu khơng  X Y FsaochoF\ c {X Y} F. tập phụ thuộc hàm F nếu thỏa mãn 3 •Thuậttốn3:Tìmphủ khơng dư thừacủa1 điều kiện sau: tậpphụ thuộchàm Đk1: Với  f Fc, f cĩ dạng X A, – Vào: Tập thuộc tính U, F = {Li Ri: i = 1 n} –Ra:Phủ khơng dư thừaF’củaF trong đĩ A là 1 thuộc tính –Thuậttốn Đk2: Với  f = X Y Fc,! A X (A là 1 B0 F0=F i i-1 i-1 thuộc tính): B NếuF \{Li Ri} F i i-1 (F \ f) U {(X \ A) Y} F thì F =F \{Li Ri} c c ngượclại, Fi =Fi-1 Đk3: ! X A Fc : Fc \{X A} Fc Bn+1 F’ = Fn 23 24 39 4
1/30/2012 Thuật tốn 4: Tìm phủủ ttốiithithiểu của một tập phụ thuộc hàm Ví dụ 1 • Vào:TậpthuộctínhU,F={Li Ri: i = 1 n} • U = {A,B,C} • Ra:phủ tốithiểuFc củatậpphụ thuộchàmF • Thuậttốn F={A BC, B C, A B, AB C}. Tìm phủ B.1. Biến đổiFvề dạng F1={Li Aj} trong đĩAj là 1 thuộctínhbấtkỳ thuộcU(thoả mãn đk1) tốithiểucủaF? B.2. Loạibỏ thuộctínhthừatrongvế trái củacácphụ thuộc hàm –F1 = {A B, A C, B C, AB C} Lần lượt giản ước từng thuộc tính trong vế trái của từng – Xét các pth trong F1 mà vế trái cĩ nhiều hơn 1 phụ thuộchàmtrongF1 thu đượcF1’. NếuF1’ F1 thì loạibỏ thuộctínhđang xét thuộctínhAB C. Giản ướcAthìtacịnB Ccĩ Khi khơng cĩ sự giản ướcnàoxảyranữatathuđược trong F1,vậyAlàthuộctínhthừa. Tương tự ta F2 thỏamãnđk2 cũng tìm đượcBlàthừa, vậyloạibỏ luơn AB C B.3. Loạibỏ phụ thuộchàmdư thừa khỏiF.F ={A B, A C, B C} Lầnlượtkiểmtratừng phụ thuộchàmf.NếuF2 \f F2 1 2 thì loạibỏ f –Bỏ pth thừa: A C là thừa. Vậy F = {A B, Khi khơng cịn phụ thuộchàmnàocĩthể loạibỏ thì thu đươc c B C} F3 thoả mãn đk3 B.4. Fc =F3 25 26 Ví dụ 2 Ví dụ 2 (tiếp) •Tìmphủ tốithiểucủatậpphụ thuộchàm – Loạibỏ pth thừatrongF2:Lầnlượtthử loạibỏ 1pthrakhỏiF,nếutập pth thu đựoc sau khi F={A B, ABCD E, EF G, ACDF EG} 2 loạibỏ vẫntương đương vớiF2 thì pth vừaloại –F1 ={A B, ABCD E, EF G, ACDF E, là thừa ACDF G} A B khơng thừavìnếuloạipthnàykhỏiF2 thì – Loạibỏ thuộc tính thừa trong 3 phụ thuộc từ tậpphụ thuộchàmcịnlại A+ khơng chứaB hàm ABCD E, ACDF EvàACDF G Tương tự , ACD E, EF G khơng thừa Xét ABCD E: Giả sử giản ướcA,tacịn ACDF Elàphụ thuộchàmthừavìnếuloạibỏ BCD E, kiểmtraBCD Ecĩđượcsuyratừ F1 + + pth này, trong tậppthvẫncịnlạiACD E, theo khơng, ta tính (BCD) (đốivớiF1). (BCD) = tiên đề tăng trưởng ta sẽ suy ra đượcACDF E BCD, khơng chứaE,vậythìBCD E khơng được suy diễnratừ F, vậyAkhơngphảilàthuộctính ACDF Glàthừavìnếuloạibỏ pth này, trong tậppthcịnlạivẫncĩACD EvàEF G, do đĩ thừatrongpthđang xét. B là thừavìtừ F1 ta cĩ + A Bdẫn đến(ACD)+ = ABCDE cĩ chứaE ta vẫncĩ(ACDF) =ACDEFGcĩchứaG Làm tương tự ta thấy khơng cĩ thuộc tính nào là –VậyFc ={A B, ACD E, EF G} thừanữa. F2 ={A B, ACD E, EF G, ACDF E, ACDF G} 27 28 Phép tách các Sơ đồ quan hệ Phép tách khơng mất mát thơng tin •Mục đích • Đ/N: Cho lược đồ quan hệ R(U) phép tách R thành các sơđồcon {R1,R2, ,Rk} đượcgọilà –Thay thế mộtsơđồquan hệ R(A ,A, , phép tách khơng mấtmátthơngtinđ/v mộttập 1 2 phụ thuộchàmFnếuvớimọiquanhệ rxácđịnh An)bằng mộttậpcácsơđồcon {R1,R2, trên R thỏa mãn F thì: , R }trongđĩR RvàR=R UR U k i 1 2 r=R1(r) R2(r)  Rk (r) U Rk •Vídụ: Phép tách mấtmátthơng tin •Yêu cầu của phép tách Supplier(sid, sname,city,NOE, pid, pname,colour,quantity) S1(sid,sname,city,NOE) và –Bảo tồn thuộc tính, ràng buộc SP1(pid,pname,colour,quantity) –Bảo tồn dữ liệu •Vídụ: Phép tách khơng mấtmátthơng tin S1(sid,sname,city,NOE) và SP2(sid,pid,pname,colour,quantity) 29 30 40 5
1/30/2012 Thuật tốn 5: Kiểm tra tính khơng mất Định lý tách đơi mát thơng tin của 1 phép tách •Cholược đồ quan hệ R(U), tậppthF,phéptáchR • Vào: R(A1, A2, , An), F, phép tách {R1, R2, , Rk} • Ra: phép tách là mất mát thơng tin hay khơng thành R1(U1), R2(U2)làmột phép tách khơng mất mát thơng tin nếu1trong2phụ thuộchàmsaulà • Thuật tốn thỏamãntrênF+: B.1. Thiết lập một bảng k hàng, n cột Nếu A là thuộc tính của R thì điền a vào ơ (i,j). U ∩ U U -U j i j 1 2 1 2 Nếu khơng thì điền bij. U1 ∩ U2 U2 -U1 B.i. Xét f = X Y F Nếu  2 hàng t1, t2 thuộc bảng : t1[X] = t2[X] thì đồng •Hệ quả:Cholược đồ quan hệ R(U) và phụ thuộc nhất hàm X Ythỏa mãn trên R(U). Phép tách R thành t1[Y] = t2[Y], ưu tiên về giá trị a 2lược đồ con R1(U1), R2(U2)làmộtphéptách Lặp cho tới khi khơng thể thay đổi được giá trị nào trong khơng mấtmátthơngtinvới: bảng B.n. Nếu bảng cĩ 1 hàng gồm các kí hiệu a , a , , a U =XY 1 2 n 1 thì phép tách là khơng mất mát thơng tin U2 =XZ ngược lại, phép tách khơng bảo tồn thơng tin Z=U\XY 31 32 Ví dụ Ví dụ (tiếp) •R = ABCD được tách thành R1=AB, R2 • B.2 & 3: ABCD =BD, R3=ABC, R4=BCD. F = {A C, •Từ A C, ta cĩ R1 a1 a2 a3 b41 B C, CD B, C D} R2 b12 a2 b32 a4 •B.1: Tạo bảng gồm 4 hàng, 4 cột R3 a1 a2 a3 b43 R4 b14 a2 a3 a4 ABCD ABCD R1 a1 a2 b31 b41 •Từ B C, ta cĩ R1 a1 a2 a3 b41 R2 b12 a2 b32 a4 R2 b12 a2 a3 a4 R3 a1 a2 a3 b43 R3 a1 a2 a3 b43 R4 b14 a2 a3 a4 R4 b14 a2 a3 a4 33 34 Ví dụ (tiếp) Phép tách bảo tồn tập phụ thuộc hàm •Từ C D, ta cĩ • Hình chiếu của tập phụ thuộc hàm ABCD Cho sơ đồ quan hệ R, tập phụ thuộc hàm F, phép R1 a1 a2 a3 a4 tách {R1, R2, , Rk} của R trên F. R2 b12 a2 a3 a4 Hình chiếu Fi của F trên Ri là tập tất cả X Y F+: R3 a1 a2 a3 a4 XY  Ri R4 b14 a2 a3 a4 •Phép tách sơ đồ quan hệ R thành {R1, R2, , Rk} là một phép tách bảo tồn tập phụ •Vậy ta cĩ 2 hàng cĩ tồn các giá trị thuộc hàm F nếu + + a. Chứng tỏ phép tách đã cho là (F1  F2  Fk) = F hay hợp của tất cả các phụ thuộc hàm trong các khơng mất mát thơng tin hình chiếu của F lên các sơ đồ con sẽ suy diễn ra các phụ thuộc hàm trong F. 35 36 41 6
1/30/2012 Ví dụ Các dạng chuẩn đối với SĐQH • Ví dụ 1: R={A,B,C}F={A B, B C, C A} •Quaylạivấn đề thiếtkế cơ sở dữ liệuquanhệ, được tách thành R1 =AB,R2 =BC.Phéptách câu hỏi mà chúng ta đặt ra trong quá trình này này cĩ phảilàbảotồntậpphụ thuộchàm là Cĩ cầnthiếtphảitinhchỉnh thiếtkế nữahay khơng? khơng, thựcsự thiếtkế mà chúng ta cĩ được đã là tốthaychưa. Để giúp trả lờicâuhỏinày, • Ví dụ 2: R={A,B,C},F={AB C, C B} ngườitađưaracácđịnh nghĩavề các dạng được tách thành R1 =AB,R2 =BC.Phéptách chuẩn. Cĩ mộtvàidạng chuẩn đã đượcxemxét, này cĩ bảo tồn tập pth khơng, cĩ mất mát khi mộtquanhệ thuộcvàomộtdạng chuẩnnào thơng tin khơng? đĩ thì ta cĩ thể coi như là mộtsố các vấn đề về • Ví dụ 3: R={A,B,C,D},F={A B, C D} dư thừadữ liệuhaydị thường dữ liệu đã được được tách thành R1 =AB,R2 =CD.Phéptách ngănngừahaytốithiểuhĩa này cĩ bảotồntập pth khơng, cĩ mấtmát •Các dạng chuẩn mà chúng ta quan tâm thơng tin khơng? –Dạng chuẩn 1 (1NF) •Vậymộtphéptáchcĩbảotồntậpphụ thuộc hàm thì khơng đảmbảolànĩsẽ khơng mấtmát –Dạng chuẩn 2 (2NF) thơng tin và ngượclại –Dạng chuẩn 3 (3NF) 37 –Dạng chuẩn Boye-Code (BCNF) 38 Dạng chuẩn 1 (1NF) Dạng chuẩn 2 (2NF) • Định nghĩa: Mộtsơđồquan hệ R đượcgọilàở • Định nghĩa: Mộtsơđồquan hệ R được dạng chuẩn1nếutấtcả các miềngiátrị củacác thuộctínhtrongRđềuchỉ chứagiátrị nguyên tố coi là ở dạng chuẩn2nếu –Giátrị nguyên tố là giá trị mà khơng thể chia –Sơ đồ quan hệ này ở 1NF nhỏ ra đượcnữa •Một quan hệ r xác định trên sơđồquan hệ ở dạng –Tấtcả các thuộc tính khơng khố đều chuẩn1thìquanhệđấylàở dạng chuẩn1 phụ thuộc hàm đầy đủ vào khố chín h •Vídụ:Quanhệ khơng ở dạng chuẩn1vàquanhệ (Lưuý,AlàmộtthuộctínhkhốnếuA sau khi chuẩnhĩavề dạng chuẩn1 thuộcmộtkhốtốithiểunàođĩcủaR. sname city product sname city item price NgượclạiAlàthuộc tính khơng khố) name price Blake London Nut 100 Blake London Nut 100 Blake London Bolt 120 Bolt 120 Smith Paris Screw 75 Smith Paris Screw 75 39 40 Phụ thuộc hàm đầy đủ Ví dụ • Định nghĩa: Cho lược đồ quan hệ • Sales(sid, sname, city, item, price) R(U), F là tập phụ thuộc hàm trên R. •F = {sid (sname,city), X, Y  U. Y được gọi là phụ thuộc đầy (sid,item) price} đủ vào X nếu: • Khố chính ((,sid,item), ta cĩ sname, + -X Y thuộc F city khơng phụ thuộchàmđầy đủ vào -! X’  X : X’ Y F+ khố chính => Quan hệ Sales khơng thuộc2NF •Các phụ thuộc hàm khơng đầy đủ cịn • S(sid, sname, city) và Sales (sid, gọi là phụ thuộc bộ phận item, price) là quan hệ thuộc2NF 41 42 42 7
1/30/2012 Dạng chuẩn 3 (tiếp) Phụ thuộc bắc cầu • Định nghĩa: Một sơ đồ quan hệ R được • Định nghĩa: Cho lược đồ quan hệ coi là ở dạng chuẩn 3 nếu R(U). F là tậpphụ thuộchàmtrên –Sơ đồ quan hệ này ở 2NF R(U). X,Y,Z  U. Ta nĩi Z là phụ –Mọi thuộc tính khơng khố đều khơng thuộcbắccầuvàoXnếutacĩX Y phụ th uộc bắc c ầu vààkháhího khố chính ,Y ZthuộcF+.Ngượclại, ta nĩi Z khơng phụ thuộcbắccầuvàoX 43 44 Ví dụ Dạng chuẩn BoyeBoye CoddCodd •Vídụ 1: Trong ví dụ tách về dạng chuẩn2ta • Định nghĩa: Một sơ đồ quan hệ R(U) với cĩ:S(sid,sname,city)vàSales(sid,item, một tập phụ thuộc hàm F được gọi là ở price). dạng chuẩn Boye-Codd (BCNF) nếu với  Xét quan hệ S, pth sid sname, city tồntại X A F+ thì trên S, sid là khố chính, các thuộctính –A là thuộc tính xuất hiện trong X hoặc khơng khố sname, city đều phụ thuộctrực –X chứa một khố của quan hệ R. tiếpvàosid.Sthuộc3NF.Tương tự ta cĩ •Ví dụ Sales cũng thuộc3NF –R = {A,B,C} ; F = {AB C , C B}. •Vídụ 2: – R khơng phải ở BCNF vì  C B, C khơng phải là –ItemInfo(item,price,discount).F={item price, khố price discount}. Khố chính là item, thuộctính • Chú ý: khơng khố discount phụ thuộcbắccầuvàokhố –Một quan hệ thuộc 3NF thì chưa chắc đã thuộc chính item. Vậyquanhệ này khơng ở 3NF. BCNF. Nhưng một quan hệ thuộc BCNF thì thuộc – ItemInfo(item, price) và Discount(price, 3NF discount) thuộc 3NF. 45 46 Tách bảo tồn tập phụ thuộc hàm về 3NF3NF Ví dụ • Vào: R(U), F (giả thiếtFlàphủ tốithiểu) Cho R = {A,B,C,D,E,F,G} • Ra:Phéptáchbảotồntậpphụ thuộchàmvề 3NF F = {A B, ACD E, EF G} (đã tối thiểu) • Thuậttốn •Xác định phép tách bảo tồn tập phụ thuộc B1.VớicácA U, A FthìloạiA khỏiRvàlập1 i i i hàm về 3NF quan hệ mớichocácAi B1. Khơng lập được quan hệ nào mới. B2.Nếu  f F, f chứatấtcả các thuộctínhcủaR B2. ! f F: f chứa tất cả các thuộc tính của R (đãbỏ các Ai ở bướctrên)thìkếtquả là R B3.Ngượclại, vớimỗiX A F, xác định một B3. A B  R1(AB) quan hệ Ri(XA). ACD E  R2(ACDE) Nếu X A ,X A thì tạomộtquanhệ chung  i j EF G  R3(EFG) R’(XAiAj) 47 48 43 8
1/30/2012 Tách khơng mất mát thơng tin và bảo tồn tập phụ thuộc hàm về 3NF Ví dụ •Cho R(U) trong đĩ U = {A,B,C,D,E,F,G}. F = •Yêucầu: {A B, ACD E, EF G} –Bảotồntậpphụ thuộchàm(như thuậttốn •Tìm một khố tối thiểu của R: trên) K0 = ABCDEFG – Đảmbảolàcĩmộtlược đồ con chứakhốcủa K1 = K0 do nếu loại A thì BCDEFG U khơng lược đồ đượctách thuộc F+ • Các bước tiến hành K2 = K1 \{B} = ACDEFG do ACDEFG U thuộc F+ B1. Tìm mộtkhốtốithiểucủalược đồ quan hệ R đãcho K3 = K2 do nếu loại C thì ADEFG U khơng thuộc B2. Tách lược đồ quan hệ R theo phép tách bảotồntậpphụ F+ thuộchàm. K4 = K3 do nếu loại D thì ACEFG U khơng thuộc B3. Nếu1trongcácsơđồcon cĩ chứakhốtốithiểuthìkết F+ quả củaB2làkếtquả cuối cùng K5 = K4 \{E} = ACDFG do ACDFG U thuộc F+ Ngượclại, thêm vào kếtquảđĩmộtsơđồquan hệđược K6 = K5 do nếu loại F thì ACDG U khơng thuộc tạobởikhốtốithiểutìmđược ở 1 F+ K7 = K6 \{G} = ACDF do ACDF U thuộc F+ 49 •Vậy khố tối thiểu cần tìm là ACDF 50 Tách khơng mất mát thơng tin về Ví dụ (tiếp) BCBCNFNF • Dùng kếtquả củavídụởphầntáchbảo • Vào:Sơđồquan hệ R, tậpphụ thuộchàmF. tồn tậpphụ thuộchàmtacĩmộtphép • Ra: phép tách khơng mấtmátthơngtinbaogồm mộttậpcácsơđồcon ở BCNF vớicácphụ thuộc táchRthành3sơđồcon R1 =AB,R2= hàm là hình chiếucủaFlênsơđồđĩ. ACDE, R3 =EFG •Cáchtiếnhành • Do khố ACDF khơng nằm trong bất kỳ một B1. KQ = {R}, sơđồcon nào trong 3 sơđồcon trên, ta lập B2.VớimỗiS KQ, S khơng ở BCNF, xét X A S, mộtsơđồcon mớiR =ACDF với điềukiệnXkhơngchứakhốcủaSvàA 4 X. Thay thế SbởiS1,S2vớiS1=A X,S2= S •Kếtquả cuối cùng ta cĩ phép tách R thành \A. 4sơđồcon {R1,R2,R3,R4}làmộtphép B3.Lặp(B2)chođếnkhiS KQ đều ở BCNF tách khơng mấtmátthơngtinvàbảotồn KQ gồmcácsơđồcon củaphéptáchyêucầu tậpphụ thuộchàm 51 52 Kết luận •Tầm quan trọng củathiếtkế CSDL – ảnh hưởng đến chất lượng dữ liệu lưu trữ –Hiệu quả của việc khai thác dữ liệu •Mục đích củathiết kế CSDL: – Tránh dư thừa dữ liệu – Tránh dị thường dữ liệu khi thêm/xố/sửa đổi –Hiệu quả trong tìm kiếm  Đưa về các dạng chuẩn –2NF: giản ước sự dư thừa để tránh các dị thuờng khi cập nhật – 3NF: tránh các dị thường khi thêm/xố 53 54 44 9
1/30/2012 Lời hay ý đẹp "Nếuanhthấymộtgiađình hạnh phúc, anh nên tin rằng ở trong gia đình cĩ mộtngười đàn bà biết quên mình." (René Bazin) 55 45 10
1/30/2012 Nội dung •Tổng quan về xử lý truy vấn Tối ưu hĩa câu truy vấn •Tối ưu hĩa các biểu thức đại số quan hệ Nguyễn Hồng Phương phuongnh@soict.hut.edu.vn Bộ mơnmơnHHệ thống thơng tin ViệnnCơngCơngngh ệ thơng tin và Truy ền thơng Đạiihhọ ccBáchBáchKhoa Hà Nội 1 2 NHP Tổng quan về xử lý truy vấn Tổng quan về xử lý truy vấn (tiếp) •Xử lý mộttruyvấnbaogồm3 –Tối ưuhĩacâutruyvấn: Mụctiêucủabước tối ưu hĩa là chọnramộtkế hoạch thựchiện bước chính: câu truy vấn cĩ chi phí thấpnhất. –PhântíchvàBiêndịch câu truy vấn: • Để thựchiện được điềunày,trướctiêntacầnbiến đổi 1biểuthức ĐSQH đầu vào thành mộtbiểuthức Trong bướcnày,hệ thống phảidịch câu ĐSQH tương đương nhưng cĩ thể xử lý được 1 cách truy vấn từ dạng ngơnngữ bậccao hiệuquả và ít tốnkémhơn. Bướcconđầutiênnày thành mộtngơnngữ biểudiễndữ llệu đượcgọilàtối ưuhĩađạisố. •Tiếptheođĩ, ta cầnphải đặctả các thuậttốnđặc bên trong để máy tính cĩ thể thao tác biệttiếnhànhthựcthicácphéptốn,chọn1chỉ dẫn trên đĩ. Mộtbiểudiễnbêntrongthích cụ thể nào đĩ để sử dụng. hợpvàhỗ trợ cho bướctối ưuhĩatiếp •Cácdữ liệuthống kê về CSDL sẽ giúp ta trong quá theo là biểudiễnbằng ngơn ngữđạisố trình xem xét và lựachọn. Ví dụ như: quan hệ 3 4 NHP NHP Tổng quan về xử lý truy vấn (tiếp) Tổng quan về xử lý truy vấn (tiếp) –Số bộ trong quan hệ –Thựchiện đánh giá truy vấn: Từ mộtkế –Kíchthướccủamộtbộ hoạch thựchiệncĩđượcdoTrìnhtối ưuhĩa –Số khối(block)chứacácbộ củaquanhệ cung cấp, hệ thống sẽ tiếnhànhthựchiệncác –Số bộ củaquanhệ mà mộtkhốicĩthể chứa thao tác trên dữ liệu trong CSDL và đưaracâu –Các thơng tin về cơ chế truy nhập, chỉ dẫntrên quan hệ trả lời cho truy vấn đĩ. Biên dịch • Chi phí cho việc thực hiện một truy vấn được Truy vấn đầu vào Biểu thức ĐSQH truy vấn đobởichiphísử dụng tài nguyên như việc truy cập đĩa, thờigianCPUdùngđể thực Tối ưu hóa hiệnmộttruyvấn. truy vấn Thống kê về dl •Trongchương này, chúng ta sẽ tập trung vào Th ực h i ệ n Câu trả lời truy vấn Kế hoạch thực hiện việc đánh giá các biểuthức đạisố quan hệ tìm kiếm dl chứ khơng đivàochitiếtviệctínhtốnchi phí cho việcthựchiện đánh giá mộttruy vấn. 5 CSDL 6 NHP NHP 46 1
1/30/2012 Đánh giá biểu thức ĐSQH Đánh giá biểu thức ĐSQH (tiếp) •Saubướcphântíchvàbiêndịch, ta cĩ •Vậtchấthĩa:Trong cách tiếpcậnnàythì ta lầnlượt đánhgiácácphéptốntheo mộttruyvấn đượcbiểudiễnbằng một mộtthứ tự thích hợp. Kếtquả củaviệc biểuthức đạisố quan hệ bao gồm đánh giá mỗiphéptốnsẽđượclưutrong nhiềuphéptốnvàtácđộng lên nhiều mộtquanhệ trung gian tạmthời để sử dụng làm đầu vào cho các phép tốn tiếp quan hệ khác nhau. Ta sẽ phải tiến theo. hành đánh giá biểuthứcnày.Cĩ2 • Điểmbấtlợicủacáchtiếpcậnnàylàviệc hướng tiếpcận để thực thi quá trình cầnthiếtphảixâydựng các quan hệ trung gian tạmthờinhấtlàkhicácquanhệ này đánh giá biểuthức ĐSQH: thường phải đượcghirađĩa(trừ khi chúng –Vậtchất hĩa (Materialize) cĩ kích thướcrấtnhỏ). Mà việc đọcvàghi ra đĩa cĩ chi phí khá lớn. – Đường ống (Pipeline) 7 8 NHP NHP Đánh giá biểu thức ĐSQH (tiếp) Đánh giá biểu thức ĐSQH (tiếp) • Đường ống: Chúng ta cĩ thể cảithiệnhiệuquả •Vídụ: Chúng ta cĩ mộtbiểuthức đạisố quan hệ đánh giá truy vấnbằng cách làm giảmbớtsố gồm2phéptốn:kếtnốivàchiếu. lượng các quan hệ trung gian tạmthời đượctạo • Trong cách tiếpcậnvậtchấthĩa,xuấtpháttừ ra. Điềunàycĩthểđạt đượcnhờ việckếthợpmột phép tốn ở mứcthấpnhấtlàphépkếtnốitự vài phép tốn quan hệ vào một đường ống của nhiên, kếtquả củaphépkếtnốinàysẽđượclưu các phép tốn. Trong đường ống thì kếtquả của trong mộtquanhệ trung gian. Sau đĩ,đọctừ một phép tốn được chuyển trực tiếp cho phép qanquan hệ tngtrung gian này để tiến hành chiếu lấy kết tốn tiếp theo mà khơng cầnphảilưulạitrong quả mong muốn. quan hệ trung gian. • Trong cách tiếpcận đường ống, khi mộtbộđược •Rõràng,cáchtiếpcậnthứ hai sẽ hạnchếđược sinh ra trong phép kếtnối2quanhệ,bộ này sẽ nhược điểmcủacáchtiếpcận đầutiên,nhưng cĩ được chuyểntrựctiếp đếnphépchiếu để xử lý và những trường hợp, ta bắtbuộcphảivậtchấthĩa kếtquảđượcghivàoquanhệđầu ra. Quan hệ chứ khơng dùng đường ống được. kếtquả sẽđượctạolậpmộtcáchtrựctiếp. 9 10 NHP NHP Tối ưu hĩa các biểu thức ĐSQH Các chiến lược tối ưu tổng quát •Mụctiêulàtổ chứclạitrìnhtự thựchiệncác 1. Đẩyphépchọnvàphépchiếuxuống thựchiện phép tốn trong biểuthức để giảmchiphí sớmnhấtcĩthể: vì hai phép tốn này giúp làm thựchiện đánh giá biểuthức đĩ. giảmkíchthướccủaquanhệ trướckhithựchiện • Trong quá trình tối ưuhĩa,tabiểudiễnmột các phép tốn 2 ngơi biểuthức ĐSQH dướidạng mộtcâytốntử. 2. Nhĩm dãy các phép chọnvàchiếu: Sử dụng chiến Trong cây thì các nút lá là các quan hệ cĩ lượcnàynếunhư cĩ mộtdãycácphépchọnhoặc mặt trong biểu thức, các nút trong là các dãy các phép chiến trên cùng một quan hệ phép tốn trong biểuthức 3. KếthợpphépchọnvàtíchĐề các thành phép kết •Vídụ : Đưa ra tên hãng cung ứng mặthàng nối: Nếukếtquả củamộtphéptíchĐề các là đối cĩ mã là 'P1': số của1phépchọncĩđiềukiệnchọnlàphépso sánh giữacácthuộctínhtrên2quanhệ tham gia Select sname From S, SP Where S.sid = tích Đề các thì ta nên kếthợp 2 phép tốn thành SP.sid And pid = 'P1' phép kếtnối. •Biểuthức ĐSQH tương ứng là? 4. Tìm các biểuthứcconchungtrongbiểuthức đại • Cây tốn tử tương ứng là? số quan hệđểđánh giá chỉ mộtlần 11 12 NHP NHP 47 2
1/30/2012 Các phép biến đổi tương đương Các chiến lược tối ưu tổng quát (tiếp) biểu thức ĐSQH 5. Xác định các phép tốn cĩ thểđược đưa vào đường ống và thựchiện đánh giá •Haibiểuthức ĐSQH E1 và E2 là tương đương chúng theo đường ống nếu chúng cho cùng mộtkếtquả khi áp 6. Xử lý các tệpdữ liệutrướckhitiếnhành dụng trên cùng mộttập các quan hệ tính tốn: Tạolậpchỉ dẫnhaysắpxếptệp dữ liệucĩthể gĩp phầnlàmgiảmchiphí •Trongphần này, ta cĩ các ký hiệudạng sau: của các phép tính trung gian –E1,E2,E3, là cácbiểuthức đạisố quan hệ 7. Ướclượng chi phí và lựachọnthứ tự thực –F1,F2,F3, làcácđiềukiệnchọnhoặclàcác hiện: Do vớimỗicâutruyvấncĩthể cĩ điềukiệnkếtnối nhiềucáchkhácnhauđể thựchiện, với việc ướng lượng chi phí (số phép tính, tài –X1,X2, Y,Z,U1,U2, làcáctậpthuộctính nguyên sử dụng, dung tích bộ nhớ,thời gian thựchiện ) ta cĩ thể chọncáchđánh giá biểuthức ĐSQH cĩ chi phí nhỏ nhất. 13 14 NHP NHP Các phép biến đổi tương đương Các phép biến đổi tương đương biểu thức ĐSQH (ti(tiếp) biểu thức ĐSQH (ti(tiếp) 1. Quy tắckếthợpcủaphéptíchĐề các và kếtnối • VD: S* SP * P cĩ thểđượcthựchiệntheo ()EEEEEE  () 3thứ tự như sau 1 2 3 1 2 3 1)(S*SP)*P (*) (*)EEEEEE1 2 3 1 2 3 2)(S*P)*SP 3)S*(SP*P) ()EEEEEE1 2 3 1 ()2 3 F1 F 2 F1 F 2 Xét theo ngữ nghĩa S, P khơng kết nối •Quitắcnàysử dụng cho chiếnlượcsố 7. Thứ tự đượcnên(1)và(3)làtốthơn(2).Xét thựchiệncácphépkếtnốihaytíchĐề các là rất về kích thướcthì(3)tốthơn(1)vìScĩ quan trọng vì kích thướccủaquanhệ trung gian 4thuộc tính cịn P cĩ 3 thuộc tính, tuy cĩ thể rấtlớnnếu khơng cân nhắckỹ.Lựachọn thứ tự thựchiện các phép tốn này thì tùy thuộc nhiên, cũng cịn tùy thuộcvàolực vào kích thướccủa các quan hệ tham gia phép lượng của2quanhệ SvàPnữa tốn và cả ngữ nghĩacủaquanhệ (mối liên hệ) 15 16 NHP NHP Các phép biến đổi tương đương Các phép biến đổi tương đương biểu thức ĐSQH (ti(tiếp) biểu thức ĐSQH (ti(tiếp) 2. Quy tắc giao hốn trong phép tích Đề 5. Quy tắc giao hốn phép chọn các và kết nối EEEE  1 2 2 1 và phép chiếu EEEE  1 2 2 1  ( (E )) (  (E )) EEEE1 2 2 1 XF FX F F 3. Quy tắc đối với dãy các phép chiếu Quy tắc này áp dụng khi F là điều kiện xác định được trên tập thuộc (   (E ) )  (E ) XX1 2 X n X 1 tính X. Tổng quát hơn ta cĩ: XX   X 1 2 n  ( (E ))  ( (  (E ))) 4. Quy tắc đối với dãy các phép chọn XF X F XY  (  (E ) )   ()E FF1 2 Fn F1 F 2   Fn 17 18 NHP NHP 48 3
1/30/2012 Các phép biến đổi tương đương Các phép biến đổi tương đương biểu thức ĐSQH (ti(tiếp) biểu thức ĐSQH (ti(tiếp) 6. Quy tắc đối với phép chọn và phép 7. Quy tắc đối với phép chọn và tích Đề các • Ta ký hiệu: phép hợp: –E1(U1) cĩ nghĩa là biểu thức E1 xác định trên tập thuộc tính U1  F ()()()EE1 2   F E1   F E 2 –F1(U1) cĩ nghĩa là điều kiện chọn F1 xác định trên tập thuộc tính U1 8. Quy tắc đối với phép chọn và –Quy tắc biến đổi liên quan đến phép chọn và tích Đề các được phát biểu như sau: phép trừ: •t F (EUEU1 ( 1 ) 2 ( 2 )) ương đương với:  F ()()()EE1 2   F EE1  F 2  ()EE –tF1 1 2 rong trường hợp F = F1(U1) –trongF1()()EE 1  F 2 2 trường hợp F = F1(U1) F2(U2) –trongFF2(())  1EE 1 2 trường hợp F = F1(U1) F2(U1U2) 19 20 NHP NHP Các phép biến đổi tương đương biểu thức ĐSQH (ti(tiếp) VVí dụ 9. Quy tắc đối với phép chiếu và tích Đề • Tìm tên hãng cung ứng ít nhất1mặt các: hàng màu đỏ hoặcmàuxanh SELECTsnameFROMS,P,SP  X (EUEU1 ( 1 ) 2 ( 2 )) Y (E1 )  Z (E 2 ) X YZ,, Y  U Z  U WHERE S.sid = SP.sid AND P.pid = SP.pid 1 2 AND (colour = ‘Red’Red OR colour = ‘GreenGreen’) ; 10.Quy tắc đối với phép chiếu và phép •Biểuthức đạisố quan hệ tương đương với hợp: câu truy vấntrênlà:  X ()()()EE1 2   X E1   X E 2  sname ( S. sid SP . sid  P . pid SP . pid  (colour 'Red '  colour 'Green ') (S SP P)) 21 22 NHP NHP Lời hay ý đẹp "Phẩm cách chân chính củaconngườilàở trong cách họ sống chứ khơng phải ở cái họ cĩ" Blackie 23 24 NHP NHP 49 4
1/30/2012 Nội dung •An tồn dữ liệu – Xác minh người sử dụng An tồn và tồn vẹn dữ liệu –Kiểm tra quyền truy nhập của người sử dụng Nguyễn Hồng Phương – Các câu lệnh an tồ n dữ liệu trong SQL phuongnh@soict.hut.edu.vn •Tồn vẹn dữ liệu –Các ràng buộc tồn vẹn trong SQL Bộ mơnmơnHHệ thống thơng tin – Điều khiển tương tranh ViệnnCơngCơngngh ệ thơng tin và Truy ền thơng Đạiihhọ ccBáchBáchKhoa Hà Nội 1 2 An tồn dữ liệu Các quyền truy nhập của người sử dụng • Định nghĩa: Tính an tồn dữ liệulàsự bảo •Quyền đọcdữ liệu: đượcphépđọcmộtphầnhay vệ dữ liệutrongcơ sở dữ liệuchống lại tồn bộ dữ liệutrongCSDL những truy nhập, sửa đổihaypháhủybất •Quyềncậpnhậtdữ liệu: đượcphépsửa đổimộtsố hợppháp. giá trị nhưng khơng đượcxĩadữ liệutrongCSDL •Quyềnxĩadữ liệu: đượcphépxĩadữ liệutrong • Ngườisử dụng hợppháplànhững ngườisử CSDL dụng đượccấp ppp,hép, được ủy qqyuyền. Ngược • Quyền bổ sung dữ liệu: được phép thêm dữ liệu mới lạilànhững ngườisử dụng bấthợppháp. vào trong CSDL nhưng khơng đượcphépthayđổidữ • Để đảmbảotínhantồnchocơ sở dữ liệu, liệu chúng ta cầncĩmộtcơ chếđểquảnlýngười •Quyềntạochỉ dẫn trên các quan hệ trong CSDL dùng cho hợplý. •Quyềnthayđổisơđồcơ sở dữ liệu: thêm hay xĩa các thuộctínhcủa các quan hệ trong CSDL • Những nhĩm ngườidùngkhácnhautronghệ CSDL cĩ quyềnsử dụng khác nhau đốivới •Quyềnloạibỏ quan hệ trong CSDL •Quyềnquản lý tài nguyên: đượcphépthêmcác các dữ liệutrongCSDL. quan hệ mớivàoCSDL 3 4 Trách nhiệm của người quản trị hệ thống Xác minh người sử dụng • Để cĩ thể phân biệt đượcngườisử dụng • Để xác minh đượcngườisử dụng, ngườita trong hệ CSDL, ngườiquảntrị hệ thống phải cĩ thể dùng các kỹ thuậtsau: –Kỹ thuậtdùngtàikhoảnvàmậtkhẩu, mậtkhẩu cĩ trách nhiệm: cũng đượcbảovệ bởihệ thống mộtcáchkỹ càng. –Xácđịnh các quyềncụ thể mà mỗingườisử dụng –Kỹ thuậtsử dụng các hàm kiểmtrachongườisử hay một nhĩm ngườisử dụng đượcphépthực dụng: Hệ thống đưachongườisử dụng mộtsố ngẫu nhiên x, người sử dụng dùng một hàm F hiện, xác định vai trị và tráhách nhiệmcủamỗi tính nhẩmkếtquả và đưakếtquả y = F(x) vào ngườisử dụng. Điềunàyđượcgọi chung là Phân hệ thống. Trong lúc đĩ, hệ thống cũng tính tốn quyềnngườisử dụng và so sánh kếtquả vớiy.Ngườisử dụng hợp pháp là ngườibiếthàmbiến đổiFvàđưavàogiá – Cung cấpmộtphương tiện cho ngườisử dụng để trị y đúng. hệ thống cĩ thể nhậnbiết đượcngườisử dụng đĩ –Kỹ thuật dùng thẻđiệntử,thẻ thơng minh. hay cịn gọi là Xác minh ngườisử dụng –Kỹ thuậtsử dụng nhậndạng tiếng nĩi, vân tay v v. 5 6 50 1
1/30/2012 Kiểm tra quyền truy nhập của người sử dụng Các câu lệnh an tồn dữ liệu trong SQL •Mỗingườisử dụng sẽ cĩ mộtbộ hồ sơ do •Câu lệnh tạo khung nhìn ngườiquảntrị thiếtlậpvàđượchệ thống quảnlý,tronghồ sơđĩsẽ cĩ chi tiếtvề các •Câu lệnh phân quyền cho người sử thao tác ngườisử dụng đượcphépthựchiện: dụng – Phân quyềnngườisử dụng: Ngườiquảntrị hệ thống phải cĩ trách nhiệm xác định khung nhìn để •Câu lệnh thu hồi quyền của người sử kiểmsốtxemmỗingườisử dụng chỉđượctruy dụng nhậpphầndữ liệunàotrongCSDLvàcĩđượccác quyềnnàotrongsố các quyền đọc, thêm, xĩa , sửa đổi. –Xác định và kiểmsốtsự lưu chuyểndữ liệu: Hệ thống phảibảo trì danh sách các quyềnmộtcách chặtchẽ vì ngườisử dụng cĩ thểđượcquyềnlan truyềncácquyền cho ngườisử dụng khác. 7 8 CCâu lệnh tạo khung nhìn Ví dụ câu lệnh tạo khung nhìn •Chocơ sở dữ liệugồm2quanhệ: • CREATE VIEW Nhânviên(Id,Họtên,ĐC,Lương,NămBD,Đánhgiá,PhịngCT) [(d/s cột)] AS Phịng(PId, Tên, ĐC, Điệnthoại, Trưởngphịng) • Danh sách các cột trong khung nhìn •Câulệnh tạo khung nhìn cho mộtnhânviêncủa phịng là phần khơng bắtbuộc. Trong Khoa Họccĩthểđược định nghĩanhư sau: trường hợp người sử dụng muốn đặt CREATE VIEW NVKH(HọtênNhânviên, Địachỉliênlạc) AS tên khác cho các cộtxuấthiệntrong SELECT Họtên,Địachỉ FROM Nhânviên khung nhìn thì ngườisử dụng cĩ thể WHERE PhịngCT IN chỉ ra tên các cột, dữ liệutrêncộtthì (SELECT PId FROM Phịng WHERE Tên =‘Khoa Học’) tương ứng vớicáccộttrongmệnh đề Select củacâutruyvấn. 9 10 Câu lệnh phân quyền cho NSD Câu lệnh phân quyền cho NSD (tiếp) • GRANT ON TO • : bảng hoặc khung nhìn [WITH GRANT OPTION] • : Mộtngườihaymột • :cĩthể bao gồm 1 hay nhiều nhĩm hay một danh sách ngườisử dụng. thao tác đượcliệtkêdưới đây: – Insert: chèn dữ liệuvàotrongCSDLcĩsẵnnhưng khơng Từ khĩa public được dùng thay thế cho mọi được thay đổi bất kỳ mục dữ liệu nào trong CSDL người sử dụng – Update: sửa đổidữ liệunhưng khơng đượcxĩadữ liệu – Delete: xĩa dữ liệutrongCSDL •[WithGrantOption]Nếu dùng từ khĩa này – Select : tìm kiếm trong câu lệnh phân quyềnthìngười dùng –Create:tạolập các quan hệ mới xuấthiện trong cĩ –Alter:Thayđổicấutrúccủa quan hệ –Drop:Loạibỏ quan hệ quyền đượclantruyềncácquyềnvừa được – Read/Write: ĐọcvàGhi tuyên bố cho những người dùng khác 11 12 51 2
1/30/2012 Ví dụ câu lệnh phân quyền cho NSD Câu lệnh thu hồi quyền của NSD •Traoquyền đọc, ghi, tìm kiếm, sửa đổidữ •REVOKE ON FROM học trên khung nhìn vừatạolậptrongphần [RESTRICT/CASCADE] trước • , , GRANT read, write, select, update ON > giiống như đối NVKH TO Hoa; vớicâulệnh GRANT. •Traoquyềnchotrưởng phịng Khoa học– ơng HungNC •Phần [RESTRICT/CASCADE] là chỉ ra cơ chế thu hồivớicácquyền đã GRANT read, write, select, update, delete ON NVKH TO HungNC WITH GRANT đượcngười dùng trong lan truyền 13 14 Câu lệnh thu hồi quyền của NSD (tiếp) Tồn vẹn dữ liệu • Định nghĩa: Tính tồn vẹndữ liệulàsự bảovệ •Nếu Restrict thì cĩ nghĩalàchỉ hủybỏ dữ liệutrongCSDLchống lạinhững sự sửa đổi, quyềncủanhững người cĩ trong danh phá hủyvơcăncứđểđảmbảotínhđúng đắnvà chính xác củadữ liệu. sách, quyền đã đượclantruyềnchongười • Các thao tác cĩ thểảnh hưởng đếntínhđúng khác khơng bị thu hồi. đắncủaCSDLlàthêm,xĩa,sửa đổi. •Nếu dùng Cascade thì hủybỏ quyềncủa • Để đảmbảotínhtồnvẹndữ liệu, cầnphảichỉ người trong , đồng thời ra và duy tìtrì những ràng buộc tồn vẹn liên kết kéo theo hủybỏ quyềnmàngườidùngđĩ vớimỗiquanhệ. Các ràng buộctồnvẹncung cấp1phương tiện để đảmbảorằng các thao tác đã luân chuyển cho những ngườikhác. đượcthựchiệnbởinhững ngườisử dụng hợp •Vídụ: pháp khơng làm mất đitínhđúng đắncủa CSDL. • Trong hệ thống đangười dùng, để đảmbảo REVOKE update,delete ON NVKH FROM đượctồnvẹndữ liệu, hệ thống cịn phảicĩ HungNC CASCADE đượcmộttrìnhđiềukhiểntương tranh để tránh đụng độ giữa các thao tác được đưarabởi 15 những ngườisử dụng khác nhau tại cùng mộ16t thời điểm Các ràng buộc tồn vẹn trong SQL Ví dụ về khẳng định •Các ràng buộcvề khĩa chính, khĩa •Số lượng mặthàngđược cung cấpbởi ngồi, kiểmtratrênmiềnsử dụng các hãng cĩ số nhânviên (SELECT sid FROM SP WHERE quantity CHECK >= 100)) 17 18 52 3
1/30/2012 Các ràng buộc tồn vẹn trong SQL (tiếp) Ví dụ về kích hoạt •Cáckíchhoạt: Là mộtthaotácđượcthực • Nhânviên(ID,Họtên,Lương,Địachỉ,Ngư hiệnmộtcáchtựđộng khi cĩ mộtthayđổi ờiquảnlý) đốivớiCSDL.Kíchhoạtlàcáccơ chế cĩ ích •Mộtnhânviênbaogiờ cũng cĩ lương để báo động hoặcthựchiệnnhững nhiệm ít hơnlương ngườitrưởng phịng, điều vụ được định sẵn khi các điều kiện nhất kiệnnàyphải đượckiểmtrakhithêm bộ dữ liệu. định đượcthỏamãn. •Kíchhoạtcĩthểđược định nghĩa để hủy DEFINE TRIGGER ThemNV ON INSERT Nhânviên bỏ,hoặckiểmtravàthựchiệnmộtsố các IF Nhânviên.Lương > (SELECT E.Lương FROM sự kiệndođĩnĩcĩthểđượccoilàmột Nhânviên AS E WHERE E.ID = biệnphápđể đảmbảotồnvẹndữ liệu. Nhânviên.Ngườiquảnlý) THEN ABORT; 19 20 Điều khiển tương tranh Các kỹ thuật điều khiển tương tranh • Kỹ thuật dùng khĩa:Khimộtgiaodịch cầndữ liệu •Trong hệ CSDL đangười dùng, hệ nào thì xin hệđiềuhànhmộtkhĩatrênphầndữ liệu thống cần đưaragiảiphápchống đĩ, các giao dịch khác phải đợi đếnkhigiải phĩng khĩa mới đượcsử dụng phầndữ liệu đĩ. Cĩ thể đụng độ giữa các giao dịch (mộtdãy ngườitasử dụng các loại khĩa khác nhau ví dụ như các thao tác) được đưarabởinhững khĩa đọc–chophépnhiềugiaodịch đọccùng1lúc, khĩa ghi – chỉ 1 giao dịch cĩ được tại một thời điểm. ngườidùng khác nhau để tránh việc • Kỹ thuật gán nhãn thờigian:Mỗigiaodịch được một đốitượng dữ liệunàođĩbị làm gán một nhãn T theo thờigian,giaodịch nào cần được ưutiênthìđược gán nhãn thờigiannhỏ hơnvà mấttínhđúng đắn trong quá trình đượcthựchiệntrước. Kỹ thuậtnàygiúpđưayêucầu cậpnhật. đồng thờivề thựchiệntuầntự. 21 22 Lời hay ý đẹp "Khi nĩi sự thậtbạnsẽ khơng phảinhớ mình vừanĩigì,màbạncũng khơng bao giờ quênnhững gì mìhình vừanĩi" S.Raybum 23 24 53 4
1/30/2012 Nội dung • 1. Mơ hình tổ chức bộ nhớ ngồi •2. Tổ chức tệp đống Tổ chức dữ liệu vật lý •3. Tổ chức tệp băm •4. Tổ chứctc tệpcp chỉ dẫn Nguyễn Hồng Phương phuongnh@soict.hut.edu.vn •5. Cây cân bằng Bộ mơnmơnHHệ thống thơng tin ViệnnCơngCơngngh ệ thơng tin và Truy ền thơng Đạiihhọ ccBáchBáchKhoa Hà Nội 1 2 1. Mơ hình tổ chức bộ nhớ ngồi 1. Mơ hình tổ chức bộ nhớ ngồi •Bộ nhớ ngồi (bộ nhớ thứ cấp): đĩa từ, băng •Thao tác với dữ liệu của tệp thơng qua từ, địa chỉ tuyệt đối của các khối. •Các bản ghi đều cĩ địa chỉ: – địa chỉ tuyệt đối của byte đầu tiên – địa chỉ khối và số byte tính từ đầu khối đến vị trí đầu bản ghi • Đĩa được chia thành các khối vật lý (sector) - • Địa chỉ của các bản ghi/khối được lưu ở 512 byte đến 4096 byte được đánh địa chỉ 1 tệp => sử dụng con trỏ (pointer) để khối gọi là địa chỉ tuyệt đối truy cập dữ liệu của tệp. •Mỗi tệp dữ liệu chiếm 1 hoặc nhiều khối •Mỗi khối chứa 1 hoặc nhiều bản ghi 3 4 2. Tổ chức tệp đống (Heap file) 2. Tổ chức tệp đống (Heap file) •Tổ chức dữ liệu • Các thao tác (tiếp) –Bản ghi lưu trữ kế tiếp trong các khối, –Xĩa một bản ghi: thao tác xĩa bao hàm khơng tuân theo một thứ tự đặc biệt nào. thao tác tìm kiếm. Nếu cĩ bản ghi cần xĩa thì nĩ sẽ được đánh dấu là xĩa => hệ k1 k2 k3 k4 k5 k6 k7 k8 thống cần tổ chức lại đĩa định kỳ. • Các thao tác –Sửa một bản ghi: tìm bản ghi rồi sửa một –Tìm kiếm một bản ghi: tìm kiếm một bản hay nhiều trường. ghi cĩ giá trị khĩa cho trước => quét tồn bộ tệp. –Thêm một bản ghi: thêm bản ghi mới vào sau bản ghi cuối cùng 5 6 54 1
1/30/2012 2. Tổ chức tệp đống (Heap file) 3. Tổ chức tệp băm (Hashed files) • Ví dụ: •Hàm băm: h(x) nhận một giá trị trong đoạn [0,k], ví dụ: h(x)=x mod k •Tổ chức tệp dữ liệu Thêm bản ghi – Phân chia các bản ghi vào các cụm. cĩ giá trị khĩa là – Mỗi cụm gồm một hoặc nhiều khối. 32 –Mỗi khối chứa số lượng bản ghi cố định. –Tổ chức lữu trữ dữ liệu trong mỗi cụm áp dụng theo tổ chức đống Xĩa bản • Tiêu chí chọn hàm băm: phân bố các ghi cĩ giá trị khĩa bản ghi tương đối đồng đều theo các là 64 cụm. 7 8 3. Tổ chức tệp băm (Hashed files) 3. Tổ chức tệp băm (Hashed files) h(x) = x mod 5 1 2 4 Store hash 3 0 1 2 3 4 1 2 3 4 9 10 3. Tổ chức tệp băm (Hashed files) 3. Tổ chức tệp băm (Hashed files) h(x) = x mod 5 • Các thao tác 12 10 –Tìm kiếm một bản ghi: để tìm bản ghi cĩ 17 Store hash khĩa x, tính h(x) sẽ được cụm chứa bản 18 ghi, sau đĩ tìm kiếm theo tổ chức đống. – Thêm một bản ghi: thêm 1 bản ghi cĩ giá 0 1 2 3 4 trị khĩa là x. •nếu trong tệp đã cĩ một bản ghi cĩ trùng khĩa 10 1 2 3 4 x =>bản ghi mới sai (vì khĩa là duy nhất!) •nếu khơng cĩ bản ghi trùng khĩa, bản ghi được 12 18 thêm vào khối cịn chỗ trống đầu tiên trong cụm, nếu hết chỗ thì tạo khối mới. 17 11 12 55 2
1/30/2012 3. Tổ chức tệp băm (Hashed files) 4. Tổ chức tệp chỉ dẫn(Indexed Files) –Xĩa một bản ghi: tìm kiếm bản ghi rồi xĩa •Giả sử giá trị các khĩa của các bản ghi được sắp xếp tăng dần. –Sửa đổi một bản ghi: •Tệp chỉ dẫn được tạo bằng cách chọn các giá •nếu trường cần sửa cĩ tham gia vào trong khĩa trị khĩa trong các bản ghi thì việc sửa sẽ là loại bỏ bản ghi này và thêm •Tệp chỉ dẫn bao gồm các cặp (k,d), trong đĩ mới 1 bản ghi (bản ghi cĩ thể thuộc vào 1 cụm k là giá trị khố của bản ghi đầu tiên, d là khác) địa chỉ của khối (hay con trỏ khối). •nếu trường cần sửa khơng thuộc khĩa: tìm kiếm rồi sửa. Nếu bản ghi khơng tồn tại thì xem như cĩ lỗi. 13 14 4. Tổ chức tệp chỉ dẫn(Indexed Files) 4. Tổ chức tệp chỉ dẫn(Indexed Files) •Tìm kiếm trên tệp chỉ dẫn • Các thao tác –Cho một giá trị khĩa ki, tìm một bản ghi –Tìm kiếm một bản ghi (km,d) trong tệp chỉ dẫn sao cho km sửa bản ghi chỉ dẫn tương ứng –Tìm kiếm này cĩ thể là: •nếu bản ghi mới này cĩ giá trị khĩa lớn hơn tất cả mọi khĩa trong tệp dữ liệu chính và khơng cịn chỗ thì tạo •tuần tự thêm một khối mới. •nhị phân 15 16 4. Tổ chức tệp chỉ dẫn(Indexed Files) 5. Cây cân bằng(Balancedng(Balanced trees)trees) –Xĩa một bản ghi: giống như thêm một bản • B-tree được tổ chức theo cấp m, cĩ các ghi, nếu xĩa mà tạo thành 1 khối rỗng, khi tính chất sau đây: đĩ cĩ thể loại bỏ cả khối đĩ. –Gốc của cây hoặc là một nút lá hoặc ít –Sửa một bản ghi: nhất cĩ hai con. • Sử dụng thủ tục tìm kiếm để xác định bản ghi – Mỗi nút (trừ nút gốc và nút lá) cĩ từ [m/2] cần sửa đến m con. •nếu các trường cần sửa khơng phải là khĩa thì sửa bình thường –Mỗi đường đi từ nút gốc đến bất kỳ nút lá •nếu các trường cần sửa tham gia vào khĩa thì nào đều cĩ độ dài như nhau. quá trình sửa sẽ là quá trình thêm và xĩa 1 bản ghi. 17 18 56 3
1/30/2012 5. Cây cân bằng(Balancedng(Balanced trees)trees) 5. Cây cân bằng(Balancedng(Balanced trees)trees) •Mọi khố trong cây con, trỏ bởi con trỏ p0 đều nhỏ hơn k1; •Mọi khố trong cây con, trỏ bởi con trỏ pi đều nhỏ hơn ki+1. •Mọi khố trong cây con, trỏ bởi con trỏ pn đều lớn hơn kn. •Cấu trúc của mỗi nút trong B-cây cĩ dạng (p0, k1, p1, k2, ,kn, pn) với pi (i=1 n) là con trỏ trỏ tới khối i của nút cĩ ki là khố đầu tiên của khối đĩ. Các khố k trong một nút được sắp xếp theo thứ tự tăng dần. 19 20 5. Cây cân bằng(Balancedng(Balanced trees)trees) 5. Cây cân bằng(Balancedng(Balanced trees)trees) • Các thao tác –Loại bỏ 1 bản ghi: –Tìm kiếm một bản ghi: xác định đường • Dùng thủ tục tìm kiếm một bản ghi để xác định dẫn từ nút gốc tới nút lá chứa bản ghi này nút L cĩ thể chứa bản ghi đĩ. –Thêm một bản ghi: •Rất cĩ khả năng “động chạm” đến nút •Xác định vị trí nút lá sẽ chứa bản ghi này (như cha, ,nút gốc. tìm kiếm) •Nếu cịn chỗ thì thêm bình thường •Nếu hết chỗ thì phải tạo thêm nút lá mới, chuyển nửa dữ liệu cuối của nút lá hiện tại sang nút mới, sau đĩ thêm bản ghi mới này vào vị trí phù hợp nút lá hiện tại hoặc nút mới tạo •Rất cĩ khả năng “động chạm” đến nút cha, .nút gốc. 21 22 Kết luận •Tổ chức tệp chỉ dẫn: – được áp dụng phổ biến –Với các ứng dụng yêu cầu cả xử lý tuần tự và truy nhập trực tiếp đến các bản ghi –Hiệu năng sẽ giảm khi kích thước tệp tăng =>chỉ dẫn B-cây •Tổ chức băm: –Dựa trên 1 hàm băm, cho phép tìm thấy địa chỉ khoản mục dữ liệu một cách trực tiếp –Hàm băm tốt? Phân bố các bản ghi đồng đều trong các cụm 23 24 57 4
1/30/2012 Lời hay ý đẹp Bản chất của tình bạn chân thật là khoan dung với những lỗi nhỏ của bạn David Storey 25 58 5
Nội dung trình bày Phát hiện các luật kết hợp 1. Tổng quan trong cơ sở dữ liệu 2. Phát hiện luật kết hợp trong cơ sở dữ liệu giao dịch Nguyễn Hồng Phương Bộ mơn Hệ thốnggg thơng tin 3. Phát hiện luật kết hợp trong cơ sở Viện CNTT&TT – trường ĐHBK Hà Nội dữ liệu quan hệ phuongnh@soict.hut.edu.vn 4. Một số vấn đề khác 1 Phát hiện luật kết hợp trong cơ sở dữ liệu 2 1. Tổng quan Khai phá dữ liệu và phát hiện tri thức Khai phá dữ liệu và phát hiện tri thức Khai Luật kết hợp: Bài tốn “Cái giỏ hàng” ChọnTiền xử lý Biến đổi phá dữ Thơng dịch Một số ứng dụng khác liệu / Đánh giá Các khái niệm cơ bản    Dữ liệu Dữ liệu Dữ liệu Dữ liệu MẫuTri thức mục tiêu tiền xử lý biến đổi Phát hiện luật kết hợp trong cơ sở dữ liệu 3 Phát hiện luật kết hợp trong cơ sở dữ liệu 4 Luật kết hợp: Bài tốn “Cái giỏ hàng” Phân tích bài tốn “Cái giỏ hàng” Phân tích thĩi quen mua hàng của Cho cơ sở dữ liệu gồm các giao dịch khách hàng: tìm sự kếthợpvàtương của khách hàng, mỗi giao dịch là một quan giữacácmặt hàng khác nhau tập các mặt hàng mà khách hàng đặtvàotrong“giỏ Tìm các nhĩm mặt hàng thường được hàng”hàng của họ mua cùng nhau Sữa, trứng, đường, Sữa, trứng, ngũ cốc, bánh mỳ Trứng, đường bánh mỳ Khách hàng 1 Khách hàng 2 Khách hàng 3 Phát hiện luật kết hợp trong cơ sở dữ liệu 5 Phát hiện luật kết hợp trong cơ sở dữ liệu 6 59 1
Một số ứng dụng khác Các khái niệm cơ bản Viễn thơng Giao dịch:  Mỗi khách hàng là một giao dịch gồm Dạng quan hệ Dạng thu gọn một tập các cuộc gọi của khách hàng đĩ Hiện tượng khí quyển  Mỗi khoảng thời gian quan sát là một giao dịch chứa một tập các sự kiện quan Mục (Item): phần tử đơn, sát được (mưa, giĩ, mây, ) Tập mục (Itemset): Tập các mục Độ hỗ trợ của 1 tập mục X - sup(X): Số giao dịch chứa X Độ hỗ trợ tối thiểu minsup : ngưỡng của độ hỗ trợ Tập mục thường xuyên : độ hỗ trợ minsup. Phát hiện luật kết hợp trong cơ sở dữ liệu 7 Phát hiện luật kết hợp trong cơ sở dữ liệu 8 Tập mục thường xuyên Luật kết hợp ID giao dịch Các mặt hàng đã mua A, B là tập các mục trong tập mục I 1 Sữa, trứng, đường, bánh mỳ Luật r = A B 2 Sữa, trứng, ngũ cốc, bánh mỳ 3 Trứng, đường Độ hỗ trợ của r: sup(r)=sup(AB) Độ tin cậy của r: Sup({Sữa, trứng, bánh mỳ})= 2 (66.6%)  conf(r) = sup(AB)/sup(A) Sup({Trứng, đường})= 2 (66.6%) r được gọi là luật kết hợp nếu Sup({Ngũ cốc, bánh mỳ})= 1 (33.3%) Nếu minsup = 50% thì {Sữa, trứng, bánh mỳ} và sup(r) minsup và conf(r) minconf {Trứng, đường} là các tập mục thường xuyên cịn {Ngũ cốc, bánh mỳ} thì khơng phải. Độ hỗ trợ Độ tin cậy tối thiểu tối thiểu Phát hiện luật kết hợp trong cơ sở dữ liệu 9 Phát hiện luật kết hợp trong cơ sở dữ liệu 10 Hai tính chất cơ bản 2. Phát hiện luật kết hợp trong CSDL giao dịch Tính chất 1: Phát hiện các tập mục thường xuyên  Nếumộttậpmục là khơng thường xuyên thì các  Kiểu Apriori siêu tậpcủanĩcũng khơng thường xuyên  Sử dụng FP-tree Tính chất 2:  Nếumộttậpmụclàthường xuyên thì các tập Phát hiện các luật kết hợp con củanĩ cũng thường xuyên Khai phá luật kế t hợp đa mức {1,2,3,4,5} B {1,2,3,5}{1,2,4,5} {1,3,4,5} {2,3,4,5} {1,2,5}{1,3,5} {1,4,5} {2,3,5} {2,4,5} {3,4,5} {1,5}{2,5} {3,5} {4,5} {5} A Phát hiện luật kết hợp trong cơ sở dữ liệu 11 Phát hiện luật kết hợp trong cơ sở dữ liệu 12 60 2