Tài liệu Phép dịch chuyển lược đồ khối trong mô hình dữ liệu dạng khối

.. ĐẠI HỌC THÁI NGUYÊN TRƢỜNG ĐẠI HỌC CÔNG NGHỆ THÔNG TIN VÀ TRUYỀN THÔNG NGÔ VĂN ĐỊNH PHÉP DỊCH CHUYỂN LƢỢC ĐỒ KHỐI TRONG MÔ HÌNH DỮ LIỆU DẠNG KHỐI LUẬN VĂN THẠC SỸ KHOA HỌC MÁY TÍNH Thái Nguyên - 2015 Số hóa bởi Trung tâm Học liệu – ĐHTN http://www.lrc.tnu.edu.vn ĐẠI HỌC THÁI NGUYÊN TRƢỜNG ĐẠI HỌC CÔNG NGHỆ THÔNG TIN VÀ TRUYỀN THÔNG NGÔ VĂN ĐỊNH PHÉP DỊCH CHUYỂN LƢỢC ĐỒ KHỐI TRONG MÔ HÌNH DỮ LIỆU DẠNG KHỐI CHUYÊN NGÀNH: KHOA HỌC MÁY TÍNH MÃ SỐ: 60 48 0101 LUẬN VĂN THẠC SỸ KHOA HỌC MÁY TÍNH Ng-êi h-íng dÉn khoa häc TS LÊ VĂN PHÙNG Thái Nguyên - 2015 Số hóa bởi Trung tâm Học liệu – ĐHTN http://www.lrc.tnu.edu.vn LỜI CẢM ƠN Để hoàn thành luận văn này tôi đã nhận đƣợc sự giúp đỡ tận tình của thầy hƣớng dẫn khoa học, của các thầycô trƣờng Đại học Công nghệ thông tin và truyền thông - Đại học Thái Nguyên. Tôi xin chân thành cảm ơn các thầy cô trƣờng Đại học Công nghệ thông tin và truyền thông - Đại học Thái Nguyên đã tạo điều kiện học tập, nghiên cứu và giúp đỡ tôi rất nhiều trong quá trình làm luận văn. Đặc biệt tôi xin cảm ơn thầyTS Lê Văn Phùng đã tận tình hƣớng dẫn, chỉ bảo tôi trong suốt quá trình học tập, nghiên cứu đề tài và giúp đỡ tôi hoàn thành bản luận văn này. Thái Nguyên, ngày 15 tháng 5 năm 2015 Học viên Ngô Văn Định Số hóa bởi Trung tâm Học liệu – ĐHTN http://www.lrc.tnu.edu.vn LỜI CAM ĐOAN Tôi xin cam đoan đây là kết quả nghiên cứu của tôi dƣới sự hƣớng dẫn khoa học của TS. Lê Văn Phùng. Các số liệu, kết quả nêu trong luận văn là trung thực và chƣa từng đƣợc ai công bố trong bất kỳ công trình nào khác. Học viên Ngô Văn Định Số hóa bởi Trung tâm Học liệu – ĐHTN http://www.lrc.tnu.edu.vn i MỤC LỤC Trang MỤC LỤC .......................................................................................................... i DANH MỤC CÁC KÝ HIỆU, CÁC CHỮ VIẾT TẮT .................................. iii DANH MỤC CÁC HÌNH ................................................................................ iv MỞ ĐẦU ........................................................................................................... 1 CHƢƠNG 1. MÔ HÌNH DỮ LIỆU DẠNG KHỐI .......................................... 4 1.1. Một số mô hình dữ liệu tiêu biểu ........................................................... 4 1.1.1. Mô hình dữ liệu quan hệ .................................................................. 4 1.1.2. Mô hình hƣớng đối tƣợng ................................................................ 4 1.1.3. Mô hình dữ liệu dạng khối .............................................................. 5 1.2. Khối, lƣợc đồ khối và các đặc trƣng cơ bản........................................... 5 1.2.1. Khái niệm khối và lƣợc đồ khối ...................................................... 5 1.2.2. Các phép tính cơ bản trên khối ........................................................ 8 1.2.3. Khái niệm phụ thuộc hàm.............................................................. 15 1.2.4. Bao đóng của tập thuộc tính chỉ số ................................................ 16 1.2.5. Khóa của lƣợc đồ khối R đối với tập F trên R............................... 19 1.2.6. Các dạng chuẩn, tựa chuẩn và tựa chuẩn hóa trên lƣợc đồ khối ... 22 1.2.7. Khái niệm về phủ và phủ tối thiểu của tập phụ thuộc hàm ........... 31 Kết luận chƣơng 1 ....................................................................................... 33 CHƢƠNG 2. PHÉP DỊCH CHUYỂN LƢỢC ĐỒ KHỐI .............................. 34 2.1. Phép dịch chuyển lƣợc đồ quan hệ ....................................................... 34 2.1.1. Định nghĩa ..................................................................................... 34 2.1.2. Thuật toán dịch chuyển lƣợc đồ quan hệ ....................................... 35 2.1.3. Bổ đề về siêu khoá trong phép dịch chuyển lƣợc đồ quan hệ ....... 39 2.1.4. Dịch chuyển lƣợc đồ quan hệ về dạng cân bằng ........................... 40 2.2. Phép dịch chuyển lƣợc đồ khối ............................................................ 43 Số hóa bởi Trung tâm Học liệu – ĐHTN http://www.lrc.tnu.edu.vn ii 2.2.1. Định nghĩa ..................................................................................... 43 2.2.2. Sự khác biệt giữa phép chuyển dịch lƣợc đồ khối so với phép dịch chuyển lƣợc đồ quan hệ ........................................................................... 45 2.2.3 Một số thuật toán dịch chuyển lƣợc đồ khối .................................. 46 2.2.4. Biểu diễn bao đóng qua phép dịch chuyển .................................... 48 2.2.5. Biểu diễn khóa qua phép dịch chuyển ........................................... 51 2.2.6. Ví dụ .............................................................................................. 55 Kết luận chƣơng 2 ....................................................................................... 56 CHƢƠNG 3. CHƢƠNG TRÌNH THỬ NGHIỆM ......................................... 58 3.1. Bài toán thử nghiệm ............................................................................. 58 3.2. Phân tích và thiết kế chƣơng trình thử nghiệm .................................... 59 3.2.1. Thủ tục dịch chuyển ...................................................................... 59 3.2.2. Biểu diễn khóa qua phép dịch chuyển ........................................... 60 3.2.3. Thiết kế chƣơng trình .................................................................... 60 3.3. Cài đặt và thực hiện chƣơng trình thử nghiệm ..................................... 60 3.3.1. Yêu cầu hệ thống ........................................................................... 60 3.3.2. Hệ thống dữ liệu vào/ra ................................................................. 61 3.3.3. Hệ thống giao diện ......................................................................... 61 3.3.4. Kết quả thử nghiệm chƣơng trình và đánh giá .............................. 62 Kết luận chƣơng 3 ....................................................................................... 67 KẾT LUẬN ..................................................................................................... 68 TÀI LIỆU THAM KHẢO ............................................................................... 69 Số hóa bởi Trung tâm Học liệu – ĐHTN http://www.lrc.tnu.edu.vn iii DANH MỤC CÁC KÝ HIỆU, CÁC CHỮ VIẾT TẮT Luận văn này dùng thống nhất các ký hiệu và chữ viết tắt sau: Ký hiệu Ý nghĩa CSDL cơ sở dữ liệu Dom(A) miền giá trị của thuộc tính A LĐQH lƣợc đồ quan hệ r hoặc r(R) khối r trên tập R Rx lát cắt của r(R) tại điểm x. PTH phụ thuộc hàm x(i) = (x, Ai) các thuộc tính chỉ số của lƣợc đồ khối (x id(i)= {x(i)|x id, i = 1..n) id} tập các thuộc tính chỉ số của lƣợc đồ khối. Fh tập các phụ thuộc hàm trên R Fhx tập các phụ thuộc hàm trên Rx Số hóa bởi Trung tâm Học liệu – ĐHTN http://www.lrc.tnu.edu.vn iv DANH MỤC CÁC HÌNH Trang Hình 1.1 Biểu diễn khối SANPHAM 7 Hình 1.2Ví dụ về phép hợp 10 Hình 1.3Ví dụ về phép giao 10 Hình 1.4 Ví dụ về phép trừ 11 Hình 3.1 Giao diện chính của chƣơng trình 61 Hình 3.2 Giao diện nhập dữ liệu 62 Số hóa bởi Trung tâm Học liệu – ĐHTN http://www.lrc.tnu.edu.vn 1 MỞ ĐẦU 1. Lí do chọn lựa đề tài Ngày nay, công nghệ thông tin đã trở thành một nhân tố không thể thiếu đƣợc trong mọi lĩnh vực của đời sống xã hội. Sự bùng nổ nhu cầu xây dựng các hệ thống thông tin, mà trƣớc hết là các hệ thống thông tin quản lý đã trở thành hƣớng nghiên cứu và quan tâm của rất nhiều nhà khoa học cũng nhƣ ngƣời sử dụng. Các hệ thống cơ sở dữ liệu (CSDL) đã lần lƣợt xuất hiện. Vào những năm 60, thế hệ đầu tiên của cơ sở dữ liệu ra đời dƣới dạng các mô hình thực thể - liên kết (có đặc điểm nhận dạng đối tƣợng), mạng phân cấp. Tiếp đến là vào những năm 70 thế hệ thứ hai của CSDL ra đời. Đó là mô hình quan hệ do E. F. Codd đề xuất. Loại mô hình này đã đánh dấu mốc quan trọng về cơ sở lý thuyết của các hệ thống CSDL. Sở dĩ mô hình này đƣợc đánh giá cao hơn cả vì nó đƣợc xây dựng dựa trên một cơ sở toán học chặt chẽ. Tuy nhiên, do các quan hệ có cấu trúc phẳng (tuyến tính) nên mô hình này chƣa đủ đáp ứng đối với các ứng dụng phức tạp, các cơ sở dữ liệu có cấu trúc phi tuyến,… Trong những năm gần đây, việc nghiên cứu nhằm mở rộng mô hình quan hệ đƣợc nhiều nhà khoa học quan tâm. Theo hƣớng nghiên cứu này đã có một số hƣớng mở rộng mô hình quan hệ đƣợc đề xuất nghiên cứu nhƣ: mô hình dữ liệu đa chiều; khối dữ liệu; kho dữ liệu; mô hình dữ liệu dạng khối... Trong đó, ở mô hình dữ liệu dạng khối, các khối là khái niệm cơ bản đƣợc mở rộng từ các quan hệ trong mô hình quan hệ, các khối này có thể biểu diễn các dữ liệu có tính chất động (biểu diễn các dữ liệu có thuộc tính thay đổi theo thời gian, không gian…) có khả năng đáp ứng tốt đối với nhiều lớp bài toán phức tạp. Trong mô hình quan hệ, để giảm tính phức tạp của việc xác định bao đóng, khóa trong các cơ sở dữ liệu lớn, phức tạp, ngƣời ta đã đề xuất phép dịch chuyển lƣợc đồ quan hệ (LĐQH). Trong mô hình cơ sở dữ liệu dạng Số hóa bởi Trung tâm Học liệu – ĐHTN http://www.lrc.tnu.edu.vn 2 khối, việc xác định khóa và bao đóng càng khó khăn hơn, chính vì vậy mà phép dịch chuyển lƣợc đồ khối đã đƣợc đề xuất với mục đích tƣơng tự. Mục tiêu của đề tài là tìm hiểu kỹ thuật thu gọn lƣợc đồ khối dựa trên phép dịch chuyển lƣợc đồ khối và phƣơng pháp biểu diễn bao đóng và khóa của lƣợc đồ khối thông qua phép dịch chuyển với độ phức tạp thấp hơn so với phƣơng pháp tìm bao đóng và khóa thông thƣờng. Đồng thời, nghiên cứu thuật toán và cài đặt chƣơng trình thử nghiệm với thuật toán dịch chuyển lƣợc đồ khối và biểu diễn khóa của lƣợc đồ khối qua phép dịch chuyển. 2. Mục đích nghiên cứu Mô hình dữ liệu dạng khối là một mở rộng của mô hình quan hệ với các khối cho phép biểu diễn các dữ liệu có tính chất động (biểu diễn các dữ liệu có thuộc tính thay đổi theo thời gian). Tuy nhiên, các nghiên cứu về mô hình dữ liệu này còn chƣa nhiều. Đối với các cơ sở dữ liệu khối lớn và phức tạp, việc xác định khóa và bao đóng là một việc khó. Nhờ việc dịch chuyển lƣợc đồ khối, việc tính bao đóng và khóa có thể trở nên đơn giản hơn. 3. Nhiệm vụ nghiên cứu - Nghiên cứu tổng quan về mô hình dữ liệu dạng khối; một số khái niệm và thuật toán liên quan. - Nghiên cứu phép dịch chuyển lƣợc đồ khối trong mô hình dữ liệu dạng khối và một số thuật toán dịch chuyển lƣợc đồ khối. - Áp dụng thuật toán dịch chuyển trong bài toán thực tế 4. Đối tƣợng và phạm vi nghiên cứu: Đối tƣợng nghiên cứu: Mô hình dữ liệu dạng khối. Phạm vi nghiên cứu: Phép dịch chuyển lƣợc đồ khối nhằm giảm nhẹ độ phức tạp trong việc tính bao đóng và khóa của khối. 5. Phƣơng pháp nghiên cứu - Phƣơng pháp nghiên cứu lý luận. Số hóa bởi Trung tâm Học liệu – ĐHTN http://www.lrc.tnu.edu.vn 3 - Phƣơng pháp phân tích - tổng hợp. - Phƣơng pháp chuyên gia. 6. Những đóng góp mới của đề tài - Hệ thống hóa các khái niệm cơ bản về mô hình dữ liệu dạng khối; các phép toán và thuật toán liên quan trên mô hình dữ liệu dạng khối. - Tìm hiểu phép dịch chuyển lƣợc đồ khối trong mô hình dữ liệu dạng khối và một số thuật toán dịch chuyển lƣợc đồ khối. - Áp dụng thuật toán đó trên để xây dựng chƣơng trình minh họa khả năng dịch chuyển khối và biểu diễn khóa qua phép dịch chuyển. 7. Cấu trúc luận văn Các nội dung nghiên cứu của đề tài luận văn đƣợc cấu trúc thành 3 chƣơng nhƣ sau: Chƣơng 1. Mô hình dữ liệu dạng khối Giới thiệu tóm tắt về các mô hình dữ liệu. Các khái niệm cơ bản về mô hình dữ liệu dạng khối nhƣ: Định nghĩa khối, lát cắt, lƣợc đồ khối...; các phép tính trên khối. Một số khái niệm về bao đóng, khóa, phụ thuộc hàm... trong mô hình dữ liệu dạng khối. Tìm hiểu một số thuật toán tìm bao đóng và khóa của lƣợc đồ khối. Chƣơng 2. Phép dịch chuyển lƣợc đồ khối Giới thiệu sơ lƣợc về phép dịch chuyển LĐQH trong mô hình quan hệ và một số vấn đề liên quan. Tìm hiểu về phép dịch chuyển và thuật toán dịch chuyển lƣợc đồ khối trong mô hình dữ liệu dạng khối. Đƣa ra phƣơng pháp biểu diễn bao đóng và khóa của lƣợc đồ khối thông qua phép dịch chuyển. Chƣơng 3. Chƣơng trình thử nghiệm Tiến hành cài đặt các thuật toán dịch chuyển lƣợc đồ khối trong mô hình dữ liệu dạng khối. Số hóa bởi Trung tâm Học liệu – ĐHTN http://www.lrc.tnu.edu.vn 4 CHƢƠNG 1. MÔ HÌNH DỮ LIỆU DẠNG KHỐI 1.1. Một số mô hình dữ liệu tiêu biểu 1.1.1. Mô hình dữ liệu quan hệ Khái niệm toán học làm nền tảng cho mô hình quan hệ là các quan hệ theo lý thuyết tập hợp. Đó là tập con của tích Đề-Các của một danh sách các miền, mỗi miền đơn giản là một tập các giá trị. Ta có thể xem một quan hệ nhƣ một bảng, trong đó mỗi hàng là một bộ và mỗi cột là một thuộc tính. Ta cũng có thể biểu diễn một sơ đồ thực thể-liên kết trong mô hình quan hệ. Khi đó, các dữ liệu của sơ đồ thực thể-liên kết đƣợc biểu diễn bởi hai loại quan hệ: - Một tập thực thể E có thể đƣợc biểu diễn bởi một quan hệ mà LĐQH của nó chứa tất cả các thuộc tính của tập thực thể đó. Mỗi bộ của quan hệ biểu diễn một thực thể trong thể hiện của E. - Mối liên hệ giữa các tập E1, E2,.., Ek đƣợc biểu diễn bởi một quan hệ có LĐQH chứa các thuộc tính trong các khóa của E1, E2,.., Ek. Bằng cách đặt lại tên cho các thuộc tính nếu cần, ta đảm bảo rằng không có hai tập thực thể trong danh sách có các thuộc tính cùng tên, ngay cả khi hai tập thực thể này chỉ là một. 1.1.2. Mô hình hướng đối tượng Mô hình dữ liệu hƣớng đối tƣợng có một số đặc điểm sau: Đặc tính nhận dạng đối tƣợng (Object identity): Các thành phần chúng xử lý điển hình là những mẩu tin, có địa chỉ duy nhất giống nhƣ trong mô hình mạng và mô hình phân cấp. Các đối tƣợng phức (Complex object): cho phép xây dựng một kiểu mới bằng thao tác tạo lập mẫu tin hoặc tạo lập tập hợp. Số hóa bởi Trung tâm Học liệu – ĐHTN http://www.lrc.tnu.edu.vn 5 Phân cấp theo kiểu (Type hierachy): Cho phép những kiểu có thể có những kiểu con và có thuộc tính riêng. Tất cả các cấu trúc đối tƣợng (object structure) đƣợc định nghĩa trong mô hình này rất gần với tập các lƣợc đồ cho các mẫu tin cơ sở dữ liệu trong mô hình phân cấp. Một mô hình hƣớng đối tƣợng không bị giới hạn trong khái niệm kiểu đối tƣợng. Khái niệm cơ bản thực sự là lớp (class), đó là một kiểu đối tƣợng làm cấu trúc dữ liệu nền tảng và một tập hợp các phƣơng pháp (method), đó là các thao tác đƣợc thực hiện trên các đối tƣợng có cấu trúc thuộc về lớp đó. Mô hình hƣớng đối tƣợng gắn liền với mô hình phân cấp theo nghĩa là nếu đƣợc cho trƣớc một lƣợc đồ phân cấp nào đó, ta có thể mô phỏng nó trong mô hình hƣớng đối tƣợng bằng cách xem các con của một nút (gồm tất cả các con là các kiểu mẫu tin ảo) trong lƣợc đồ phân cấp nhƣ là các trƣờng trong một cấu trúc đối tƣợng ứng với n. Các cấu trúc đối tƣợng cho các con của n lại có các con của chúng là các trƣờng... Nhƣ vậy, mô hình hƣớng đối tƣợng có thể diễn tả mọi cấu trúc của mô hình thực thể-liên kiết, tuy nhiên để đảm bảo yêu cầu truy xuất hiệu quả các thông tin cần thiết trong các cấu trúc đối tƣợng cũng không phải là một công việc đơn giản. 1.1.3. Mô hình dữ liệu dạng khối Mô hình dữ liệu dạng khối là một mở rộng của mô hình quan hệ, khi đó, mô hình quan hệ có thể đƣợc coi là một trƣờng họp đặc biệt của mô hình dữ liệu dạng khối. Các nội dung cụ thể sẽ đƣợc trình bày trong phần tiếp theo của luận văn. 1.2. Khối, lƣợc đồ khối và các đặc trƣng cơ bản 1.2.1. Khái niệm khối và lược đồ khối Khái niệm toán học làm nền tảng cho mô hình dữ liệu dạng khối là các khối hiểu theo nghĩa của lý thuyết tập hợp. Khối đƣợc định nghĩa nhƣ sau: Số hóa bởi Trung tâm Học liệu – ĐHTN http://www.lrc.tnu.edu.vn 6 Định nghĩa 1.1[4], [7] Gọi R=(id;A1, A2,…, An) là một bộ hữu hạn các phần tử, trong đó id là tập chỉ số hữu hạn khác rỗng, Ai (i=1..n) là các thuộc tính. Mỗi thuộc tính Ai (i=1..n) có miền giá trị tƣơng ứng là Dom(Ai). Một khối r trên R, ký hiệu r(R), gồm một số hữu hạn phần tử mà mỗi phần tử là một họ ánh xạ từ tập chỉ số id đến các miền giá trị của các thuộc tính Ai (i=1..n). Nói một cách khác: t r(R) t = {ti: id Dom(Ai)} i=1..n Ta ký kiệu khối đó là r(R) hoặc r(id; A1, A2,…, An), đôi khi nếu không sợ nhầm lẫn, ta ký hiệu đơn giản là r. Khi đó, khối r(R) đƣợc gọi là có lƣợc đồ khối R. Nhƣ vậy, trên cùng một lƣợc đồ khối R, ta có thể xây dựng đƣợc nhiều khối khác nhau. Ví dụ 1.1 Xây dựng khối sản phẩm (ký hiệu SP(R)) để quản lý sản phẩm của một công ty: cho lƣợc đồ khối R = (id; A1, A2, A3, A4) trong đó: id = {1/2014, 2/2014, 3/2014, ..., 12/2014} và các thuộc tính A1 = ma (mã), A2 = ten (tên), A3 = c_luong (chất lƣợng), A4 = gia (giá). Hình 1.1 Biểu diễn khối SANPHAM Số hóa bởi Trung tâm Học liệu – ĐHTN http://www.lrc.tnu.edu.vn 7 Với khối SP(R) ở hình trên thì nó gồm 3 phần tử t1, t2, t3. Chất lƣợng của sản phẩm t1 ở thời điểm tháng 2 năm 2014 là: t1(2/2014, c_luong) = Tot Mã số của sản phẩm t2 ở thời điểm tháng 1 năm 2014 là: t2(1/2014, ma) = A02 Tên của sản phẩm t3 ở thời điểm tháng 3 năm 2014 là: t3(3/2014, ten) = C Giá của sản phẩm t2 ở thời điểm tháng 1 năm 2014 là: t2(1/2014, gia) = 400 Định nghĩa 1.2[4], [7] Cho R = (id; A1, A2,…, An), r(R) là một khối trên R. Với mỗi x id, ta ký hiệu r(Rx) là một khối với Rx = ({x}; A1, A2,…, An) sao cho: tx r Rx tx {t ix t i }i 1..n , t r(R), x với t = {ti: id Dom(Ai)} i=1..n ở đây t ix (x) t i (x),i 1..n . Khi đó, t(Rx) đƣợc gọi là một lát cắt trên khối r(R) tại điểm x. Ví dụ 1.2 Với khối SP(R) đã cho ở trên, R = (id; A1, A2, A3, A4) trong đó: id = {1/2014, 2/2014, 3/2014, ..., 12/2014} và các thuộc tính A1 = ma (mã), A2 = ten (tên), A3 = c_luong (chất lƣợng), A4 = gia (giá). Nếu x = 1/2014 r(R1/2014): id thì lát cắt r(R1/2014) có dạng nhƣ sau: ma ten c_luong gia A01 A TB 300 A02 B Tot 400 A03 C Cao 550 Số hóa bởi Trung tâm Học liệu – ĐHTN http://www.lrc.tnu.edu.vn 8 Nhận xét Cho R = (id; A1, A2,…, An), r(R) là một khối trên R. Với mỗi x id, thì lát cắt r(Rx) là một quan hệ. Trong trƣờng hợp tập chỉ số id gồm một phần tử thì r(R) trở thành một quan hệ. Nhƣ vậy, mỗi quan hệ r(A1, A2,…, An) là một trƣờng hợp đặc biệt của khối, đó chính là khối r(R) với R = ({x}; A1, A2,…, An). Mệnh đề 1.1[4], [7] Cho lƣợc đồ khối R = (id; A1, A2,…, An), r(R) là một khối trên R, khi đó tồn tại một họ quan hệ (hiểu theo nghĩa tập hợp) duy nhất biểu diễn họ {r(Rx)}x id các lát cắt của khối r(R). Ngƣợc lại không đúng, nghĩa là với một họ quan hệ cho trƣớc biểu diễn họ các lát cắt của một khối nào đó thì khối tìm đƣợc không duy nhất. 1.2.2. Các phép tính cơ bản trên khối Các phép tính cơ bản thƣờng đƣợc áp dụng cho một cơ sở dữ liệu là: - Phép chèn (insert) - Phép loại bỏ (delete) - Phép sửa đổi (change) Trong mô hình dữ liệu dạng khối, các phép tính này cũng đƣợc áp dụng cho từng phần tử của các khối lƣu trữ trong máy. Cụ thể - Phép chèn (insert)[4], [7] Cho lƣợc đồ khối R = (id; A1, A2,…, An), r(R) là một khối trên R. Khi chèn thêm một phần tử t0 vào khối r, ta có: r=r {t0}, ở đó t0 = (t10, t20,…, tn0) INSERT(r, t10, t20,…, tn0) - Phép loại bỏ (delete) [4], [7] Cho lƣợc đồ khối R = (id; A1, A2,…, An), r(R) là một khối trên R. Số hóa bởi Trung tâm Học liệu – ĐHTN http://www.lrc.tnu.edu.vn 9 Phép loại bỏ là phép xóa một phần tử ra khỏi một khối cho trƣớc. Chẳng hạn, loại phần tử t0 vào khối r(R), có dạng: r = r - {t0}, t0 = (t10, t20,…, tn0) DEL(r, t1 = t10, t2 = t20,…, tn = tn0) Ở đây, để xác định phần tử cần loại bỏ, ta phải dùng bộ ánh xạ (t1, t2,…, tn). Nghĩa là, ta phải thực hiện các phép so sánh: t1 = t10, t2=t20,…, tn = tn0 để xác định phần tử t0 nhƣ ở trên. - Phép sửa đổi (change)[4], [7] Phép sửa đổi phần tử t0 thành phần tử t’0 có dạng. {t’0}, với t0 = (t10, t20,…, tn0), t’0 = (t’10, t’20,…, t’n0), r = r - {t0} CH(r, t1 = t10, t2 = t20,…, tn = tn0; t1 = t’10, t2 = t’20,…, t’n = tn0) Đối với các phép chèn, loại bỏ và sửa đổi nêu trên, khi khối r suy biến thành một quan hệ, nghĩa là khi tập chỉ số id chỉ gồm một phần tử (id ={x}) thì chúng lại trở thành các phép chèn, loại bỏ và sửa đổi trên một quan hệ trong mô hình dữ liệu quan hệ. * Đại số trên khối [4], [7] Cho r là một khối trên R = (id; A1, A2,…, An). Tƣơng tự nhƣ đại số quan hệ trong mô hình dữ liệu quan hệ, ở đây, các phép toán của đại số quan hệ đƣợc áp dụng cho các khối nhƣ: phép hợp, phép giao,phép trừ, phép chiếu, phép chọn, phép kết nối, phép chia. Ngoài ra, phép nối dài là phép toán mới đƣợc xây dựng. Hai khối r và s đƣợc gọi là khả hợp nếu chúng có cùng một lƣợc đồ khối. - Phép hợp Cho hai khối r và s khả hợp, khi đó hợp của r và s, ký hiệu r s là một khối gồm các phần tử thuộc khối r hoặc thuộc khối s đã cho. Ta có: r s = {t | t r hoặc t Số hóa bởi Trung tâm Học liệu – ĐHTN s} http://www.lrc.tnu.edu.vn 10 Ví dụ 1.3 ma A A01 B A02 C t2 A03 B A02 1/2014 C A03 2/2014 C t3 r B 2/2014 C t2 1/2014 A01 A02 2/2014 A03 A02 A B A02 B t2 A A01 t1 B A02 t1 ten ten ma A A01 t1 ma ten 1/2014 A03 s r s Hình 1.2.Ví dụ về phép hợp - Phép giao Cho hai khối r và s khả hợp, khi đó giao của r và s, ký hiệu r s là một khối gồm các phần tử của nó thuộc đồng thời cả hai khối r và s đã cho. Ta có: r s = {t | t r và t s} Ví dụ 1.4 ten ma ma ma t1 ten A A01 A02 B 2/2014 A02 1/2014 t3 C A03 B 2/2014 t2 C A03 r A A01 A02 B A02 B A A01 B t2 A A02 t2 A01 t1 A A01 A01 t1 ten A B 1/2014 A02 2/2014 1/2014 s r s Hình 1.3Ví dụ về phép giao Số hóa bởi Trung tâm Học liệu – ĐHTN http://www.lrc.tnu.edu.vn 11 - Phép trừ Cho hai khối r và s khả hợp, khi đó hiệu của r và s, ký hiệu r - s là một khối mà các phần tử của nó thuộc r nhƣng không thuộc s. Ta có: r - s = {t | t r và t s} s = r – (r – s) Ta thấy: r Ví dụ 1.5 ma A01 A01 A t2 B A02 t2 B A02 A02 t1 B t3 A03 C C t3 A01 C 2/2014 A03 B A02 ten ma A t1 ten ma ten t2 1/2014 A A B A02 C A03 A01 A02 B 2/2014 1/2014 2/2014 1/2014 A03 r s r-s Hình 1.4Ví dụ về phép trừ - Tích Đề-các Cho lƣợc đồ khối R = (id; A1, A2,…, An), S = (id; B1, B2,…, Bm), và {A1, A2,…, An} {B1, B2,…, Bm} = . Khi đó, tích Đề-các của hai khối r(R) và s(S) là một khối, ký hiệu r khối này có khung R s, S = (id; A1, A2,…, An, B1, B2,…, Bm), mỗi phần tử thuộc khối này là một bộ gồm n + m ánh xạ, trong đó n ánh xạ đầu có dạng một phần tử thuộc r, còn m ánh xạ sau có dạng một phần tử thuộc s. r s = {t | t(R) trong đó: r và t(S) s}, t = (t1, t2,…, tn, tn+1,…, tn+m), t(R) = (t1, t2,…, tn), t(S) = (tn+1,…, tn+m). Số hóa bởi Trung tâm Học liệu – ĐHTN http://www.lrc.tnu.edu.vn 12 - Tích Đề-các theo tập chỉ số Cho lƣợc đồ khối R = (id; A1, A2,…, An), S =(id’; A1, A2,…, An). Khi đó, tích Đề-các của hai khối r(R) và s(S) theo tập chỉ số là một khối, ký hiệu r id s, khối này có khung R id S=(id ∐ id’; A1, A2,…, An), với id ∐ id’ là ký hiệu tích rời rạc của hai tập chỉ số id và id’. Mỗi phần tử thuộc khối này là một bộ gồm n ánh xạ(t1, t2,…, tn) với ti: id ∐ id’ → Ai, với i = 1..n, mỗi ánh xạ này đƣợc cảm sinh từhai ánh xạ thứ i tƣơng ứng của r và s. Cụ thể hơn, giả sử có 2 phần tử là tr r và ts s: tr = (t1r, t2r,…, tnr), ts = (t1s, t2s,…, tns), khi đó, ta có ánh xạ cảm sinh của tr và ts, phần tử cảm sinh của tr và ts, ký hiệu là trs. Gọi j1: id → id ∐ id’; j2: id → id ∐ id’ là các phép nhúng, thì ta đƣợc:trsj1 r và trsj2 s và r id s = {t | tj1 r và tj2 s} - Phép chiếu Cho lƣợc đồ khối R = (id; A1, A2,…, An), r là một khối trên R. Khi đó, ta gọi P = (id’; Ai1, Ai2,…, Aih) là lƣợc đồ con của lƣợc đồ R nếu: id' id, Aij {A1, A2,…, An}, j = 1..h Một phép chiếu của r trên lƣợc đồ con P, ký hiệu p(r), là một khối có lƣợc đồ P và mỗi phần tử thuộc khối này có dạng: (t i1 , t i2 ,..., t ih ) id ' Trong đó: tij {t1, t2,…, tn} với j = 1..h và (t1, t2,…, tn) r Biểu diễn theo hình thức của phép chiếu có dạng: P (r) {(t i1 ,t i2 ,...,t ih ) | t ij {t1,t 2 ,...,t n }, j=1..h,(t1,t 2 ,...,t n ) r} id ' - Phép chọn Cho lƣợc đồ khối R = (id; A1, A2,…, An), và khối r(R). Số hóa bởi Trung tâm Học liệu – ĐHTN http://www.lrc.tnu.edu.vn