Tài liệu đáp án cơ sở dự liệu nâng cao

Ôn tập: 1. Các qui tắc ECA (Event-Condition-Action rules) 2. Các vấn đề cần xem xét khi thiết kế và cài đặt CSDL tích cực 3. Phân biệt Valid time, transaction time, bitemporal time trong CSDL thời gian 4. Mô hình và thao tác trên CSDL suy diễn 5. Mô hình cơ sở dữ liệu đối tượng 6. Chuyển đổi từ mô hình đối tượng sang mô hình quan hệ 7. Chuyển đổi từ mô hình ER sang mô hình quan hệ 8. Truy vấn trong cơ sở dữ liệu hướng đối tượng và ODMG 3.0 9. Phân mảnh trong CSDL phân tán 10. Xử lý truy vấn trong CSDL phân tán 11. Lịch tuần tự, khả tuần tự của các giao tác 12. Thuật toán khóa 2 pha 13. Deadlock và Starvation 14. Tiếp cận thời nhãn và ma trận tương thích Bài làm 1. Các qui tắc ECA (Event-Condition-Action rules) : có tác dụng đảm bảo tính toàn vẹn trong CSDL. Một qui tác được cấu thành từ 3 thành phần (trong CSDL tích cực)  Qui tắc sự kiện (event): là các sự kiện luôn áp dụng cho cập nhật dữ liệu, gắn với CSDL. Chúng cũng có thể là sự kiện thời gian hoặc một kiểu sự kiện mở rộng khác.  Qui tắc điều kiện (condition): Điều kiện là lựa chọn. Nếu không có điều kiện nào được xác định thì hành động sẽ được thực hiện khi sự kiện xảy ra. Nếu điều kiện được xác định thì hành động chỉ xảy ra khi sự kiện là đúng.  Qui tắc hành động chiếm giữ (action rule): hành động thường là một câu truy vấn (SQL), một thực hiện CSDL hoặc một chương trình mở rộng được thực hiện một cách tự động.  CSDL tích cực nâng cao: nâng cao chức năng CSDL truyền thống với đầy đủ các quy tắc - khả năng xử lý.  CSDL tích cực cung cấp một máy có khả năng và hoạt động tương tự như bất kỳ ứng dụng hệ thống CSDL như: + Tích hợp ràng buộc + Khung nhìn + Thống kê kết quả + Giám sát hoặc thông báo,…  TrongcơsởdữliệuquanhệcácquytắctíchcựcđượcviếtdướidạngcácTrigger.Vídụ: Với 1 hai bảng: o DonVi (MaDV, TenDV,TongLuong, MaNQL) o NhanVien (MaNV, TenNV, NgaySinh, GioiTinh,Luong, MaDV) Một quytắcsẽ có dạngnhư sau: o Event:Hành động Insert một bản ghi trongbảng NhanVien. o Condition:  GiátrịcủaMaDVđượcthêmvàokhôngcótrongtậpgiátrịhiệncótrong bảng DonVi.  NếuMaDVđượcthêmvàolàđãcótrongbảngDonViTổnglươngcủa đơn vị đó cần được thay đổi. o Action:  Sửađổi sai sótdo sự kiện gâyra.  Thôngbáo lỗicho người dùng. 2. Các vấn đề cần xem xét khi thiết kế và cài đặt CSDL tích cực:  Nguyên tắc 1: Hoạt động, ngừng hoạt động và nhóm qui tắc: Một hệ thống CSDL tích cực sẽ cho phép người sử dụng hoạt động, ngừng hoạt động và hủy các quy tắc bởi tên của quy tắc.  Nguyên tắc 2: Hành động gây ra sẽ xảy ra trước, sau hoặc đồng thời với lúc bắt đầu sự kiện.  Nguyên tắc 3: Hành động xảy ra hiện tại được suy xét như một sự thực hiện rời rạc hoặc là một phần của một thực hiện tương tự gây ra qui tắc. o Có 3 khả năng chính đối với qui tắc suy xét:  1. Suy xét trực tiếp: Điều kiện được ước lượng là một phần của thực hiện tương tự khi bắt đầu sự kiện, và được ước lượng trực tiếp. Có 3 lựa chọn: + Ước lượng điều kiện trước khi sự kiện bắt đầu. + Ước lượng điều kiện sau khi sự kiện bắt đầu. + Ước lượng điều kiện thay thế việc thực hiện khi sự kiện bắt đầu.  2. Trì hoãn sự suy xét: Điều kiện được ước lượng vào cuối của sự thực hiện bao gồm sự kiện bắt đầu.  3. Suy xét tách rời: Điều kiện được ước lượng như một thực hiện rời rạc, được tái tạo từ lúc bắt đầu thực hiện. 2 3. Phân biệt Valid time, transaction time, bitemporal time trong CSDL thời gian:  Valid time (VT): thời gian sự kiện xảy ra, thông tin cập nhật dữ liệu lấy kiểu thời gian thực.  Transaction time (TT): thời gian thực hiện cập nhật vào CSDL (thời gian hệ thống).  Bitemporal time (BT): bao gồm cả VT và BT.  user-define time: do tùy người sử dụng. 4. Mô hình và thao tác trên CSDL suy diễn: 4.1 Mô hình CSDL suy diễn:  Kí pháp toán học để mô tả hình thức dữ liệu và các quan hệ.  Kỹ thuật để xử lý dữ liệu như trả lời các câu hỏi, kiểm tra điều kiện toàn vẹn.  Logic bậc một được dùng như kí pháp toán học để mô tả dữ liệu trong mô hình CSDL suy diễn và dữ liệu được xử lý trong các mô hình như vậy nhờ việc đánh giá công thức logic.  Tuy nhiên để dễ biểu diễn hình thức các khái niệm về CSDL suy diễn, người ta thường dùng phép toán vị từ, tức logic vị từ bậc nhất. Logic vị từ bậc nhất là ngôn ngữ hình thức dùng để thể hiện các quan hệ giữa các đối tượng và để suy diễn ra quan hệ mới.  Các định nghĩa: o Định nghĩa 1: Mỗi một hằng số, một biến số hay một hàm số áp lên các tên là một hạng thức (term) Hàm n ngôi f(x1,x2,..,xn); xi | i = 1,2,..,n là một hạng thức thì f(x1,x2,…,xn) là một term. o Định nghĩa 2: Công thức nguyên tố (công thức nhỏ nhất) là kết quả của việc ứng dụng một vị từ trên các tham số của term dưới dạng P(t1, t2,…, tn). Nếu P là vị từ có n ngôi và ti | i=1,2, ..,n là một hạng thức(term). o Định nghĩa 3: (Literal) Dãy các công thức nguyên tố hay phủ định của công thức nguyên tố đã được phân tách qua các liên kết logic (, , , , , , ) thì công thức đó được thiết lập đúng đắn.  Nhận xét:  i) Một công thức nguyên tố là công thức thiết lập đúng đắn. 3  ii) F, G là công thức thiết lập đúng đắn => F  G, F  G, F  G, F  G, F ,G cũng là các công thức thiết lập đúng đắn.  iii) Nếu F là công thức thiết lập đúng đắn, mà x là một biến tự do trong F => (x)F và (x)F cũng là các công thức thiết lập đúng đắn ( x, x trong F ).  Ví dụ 1: Cho quan hệ R(A1, A2,…, An) với n bậc (tức n thuộc tính) => là một vị từ n ngôi. Nếu rR (r bộ của R) => (r.A1, r.A2,…, r.An ) => R(A1, A2,.., An) nhận giá trị đúng. Nếu rR (r bộ của R) => gán (r.A1, r.A2,…, r.An ) => R(A1, A2,.., An) nhận giá trị sai. o Định nghĩa 4: Câu(Clause) Công thức có dạng P1P2….Pn  Q1Q2….Qn Trong đó: Pi và Qj (i,j=1,2,…,n) là các Literal dương Trong hệ thống logic, Literal dương có dạng nguyên tố, nhỏ nhất, trái với Literal âm là phủ định của nguyên tố. o Định nghĩa 5: Câu Horn (Horn clause) là câu có dạng P1P2….Pn  Q1 o Định nghĩa 6: CSDL suy diễn tổng quát (General deductive database) CSDL suy diễn tổng quát, hay CSDL suy diễn được xác định như cặp (D,L), trong đó D là tập hữu hạn của các câu CSDL và L là ngôn ngữ bậc một. Giả sử L có ít nhất hai ký hiệu, một là ký hiệu hằng số và một ký kiệu vị từ. + Một CSDL xác định (hay CSDL chuẩn) là CSDL suy diễn(D,L) mà D chỉ chứa các câu xác định(câu chuẩn). + Một CSDL quan hệ là CSDL suy diễn (D,L) mà D chỉ chứa các sự kiện xác định . 4.2 Thao tác trên CSDL suy diễn: 4.2.1 Định nghĩa 1:Giao tác (Transaction) Một giao tác trong CSDL suy diễn là một một xâu hữu hạn của các phép toán, hay các hành động bổ sung, loại bỏ hay cập nhật các câu. Vì một CSDL suy diễn được xem như tập các câu, tức là theo quan điểm lý thuyết mô hình, không một phép loại bỏ hay cập nhật nào được phép thực hiện trên sự kiện. Các sự kiện là ngầm có trong CSDL. 4 4.2.2 Định nghĩa 2: Khẳng định (Commit) Một giao tác được gọi là được khẳng định tốt nếu toàn bộ xâu các phép toán tạo nên kết quả tốt của giao tác. Lý do chính của việc không đảm bảo hoàn thành tốt một giao tác là sự vi phạm điều kiện toàn vẹn khi thực hiện các phép toán trong giao tác, hay hư hỏng hệ thống, tính toán vô hạn. 5. Mô hình cơ sở dữ liệu đối tượng: 5.1 Khái niệm: Thông tin được biểu diễn thành các đối tượng giống như các đối tượng trong lập trình hướng đối tượng. – Dữ liệu thuộc tính mô tả các đặc trưng của các thực thể (đối tượng) – Các phương thức mô tả hành vi ứng xử của đối tượng – Mối quan hệ giữa các lớp với nhau. – Thuộc tính khoá có thể được sử dụng để xác định các bộ dữ liệu ở những bảng khác được gọi là khoá ngoại (foreign key). Mỗi đối tượng (thực thể) có một định danh ID để xác định duy nhất trong CSDL. Các CSDLĐT được thiết kế để làm việc tốt đối với những ngôn ngữ lập trình như Java, C++, C#, Smalltalk, v.v. Mục đích của CSDLHĐT là để quản trị hiệu quả những kiểu dữ liệu phức hợp như âm thanh, hình ảnh, dữ liệu đa phương tiện, v.v., nhằm khắc phục những hạn chế của CSDL quan hệ. 5.2 Kiến trúc của CSDL đối tượng: CSDL đối tượng được tối ưu hóa cho truy cập điều hướng và điều phối các đối tượng giữa các máy chủ cơ sở dữ liệu Server và Client. Client-server architecture of an ODBMS 6. Chuyển đổi từ mô hình đối tượng sang mô hình quan hệ: Có một số cách thức thực hiện:  Một trong các cách sử dụng phổ biến là là định nghĩa một bảng cho mỗi lớp, trong đó mỗi cột trong bảng đại diện cho một thuộc tính của lớp (attri đơn trị, hoặc đa trị) Employee_Table 5 • • Tất cả các thuộc tính của Employee được lưu trong bảng Employee Những thuộc tính trên cùng với các thuộc tính bổ sung của HourlyEmployee sẽ được copy để lưu bảng HourlyEmployee. Tương tự đối với bảng SalariedEmployee. Nhận xét: – Việc chuyển mô hình đối tượng về quan hệ khi có kế thừa sẽ phải copy các thuộc tính của lớp cha sang lưu vào lớp con nên không bảo đảm được các dạng chuẩn dữ liệu. – Một khi các sơ đồ cần thiết đã được định nghĩa mã chuyển đổi từ đối tượng sang quan hệ được ghi. Mã này là cần thiết để có một đối tượng, khi nó được tạo ra và xử lý trong các ngôn ngữ lập trình và loại bỏ cấu trúc (deconstruct) để biểu diễn chúng theo yêu cầu của cơ sở dữ liệu. – Ngoài ra khi cần tìm các đối tượng HourlyEmployee trong CSDL thì phải kết nối các bảng HourlyEmployee và Employee. Như vậy sẽ tốn kém thời gian. – Vấn đề quan trọng nữa là khi cập nhật thông tin, vì có nhiều mối quan hệ giữa các bảng thực thể nên độ phức tạp sẽ càng tăng. 7. Chuyển đổi từ mô hình ER sang mô hình quan hệ:  Mỗi tập thực thể của mô hình ER chuyển đổi thành 1 lớp đối tượng có cùng tên và cùng tập thuộc tính. Các thuộc tính đa trị và phức hợp của mô hình ER được chuyển thành các thuộc tính đa trị (sử dụng từ khóa set) và phức hợp (sử dụng từ khóa tuple) cảu mô hình hướng đối tượng.  Việc xác định các phương thức cho mỗi lớp đối tượng được thực hiện sau đó bởi người thiết kế hệ thống CSDL.  Các qui tắc: o Qui tắc chuyển đổi mối quan hệ is-a: nếu tập thực thể A là có mối quan hệ is –a với tập thực thể B thì lớp A sẽ kế thừa tất cả các thuộc tính trong lớp B (tức: lớp A là lớp con của lớp B). 6 Ví dụ: id NGUOI is-a NHANVIEN hoten M« hình quan hÖ NGUOI(id, hoten, tuoi) NHANVIEN(id, luong) tuoi luong Mô hình hướng đối tượng Class NGUOI Class NHANVIEN properties inherits:NGUOI; Id: String; properties Hoten: String; Luong: Integer; Tuoi: Integer; End NHANVIEN. End NGUOI. o Qui tắc 2 (qui tắc chuyển đổi mối quan hệ nhị nguyên không có thuộc tính) : nếu 2 tập thực thể A và B có mối quan hệ R (R không có các thuộc tính đính kèm), thì mỗi lớp tương ứng A và B sẽ được bổ sung thêm thuộc tính mối quan hệ R (khai báo thuộc tính đa trị/đơn trị là tùy thuộc vào bản số liên quan). Cụ thể: Xét 2 trường hợp sau:  Trường hợp 1: Nếu chỉ số cực đại của cung nối A và R là 1 thì thuộc tính R trong lớp A được khai báo : : ;  Trường hợp 2: Nếu chỉ số cực đại của cung nối A và R là n thì thuộc tính R trong lớp A được khai báo : : set (); Id_tk Mô hình hướng đôối tượng Ví dụ : mối quan hệ 1-1 Class TRUONGKHOA TRUONGKHOA tuoi properties Id_tk: String; Hoten: String; hote quanly Tuoi: Integer; n Quanly: KHOA; tenkhoa End TRUONGKHOA. (1,1) Class KHOA id_tk KHOA properties Id_k: String; Tenkhoa: String; tuoii Sodienthoai: String; Quanly: TRUONGKHOA; 7 End KHOA. Mô hình quan hệ TRUONGKHOA(id_tk, hoten, tuoi) KHOA(id_k, tenkhoa, sodienthoai, id_tk) Ví dụ: (Mối quan hệ 1 – nhiều) id_gv GIAOVIEN hoten (1,1) tuoi thuoc (1,n) KHOA id_k tenkhoa sodienthoai Mô hình hướng đối tượng Class GIAOVIEN properties Id_gv: String; Hoten: String; Tuoi: Integer; Thuoc: KHOA; End GIAOVIEN. Class KHOA properties Id_k: String; Tenkhoa: String; Sodienthoai: String; Thuoc: set(GIAOVIEN); End KHOA. Ví dụ : (Mối quan hệ nhiều – nhiều) Mô hình quan hệ Mô hình hướng đôối tượng id_gv Class GIAOVIEN GIAOVIEN(id_gv, hoten, tuoi, id_k) properties KHOA(id_k, tenkhoa, sodienthoai) GIAOVIEN Id_gv: String; hoten Hoten: String; (1,n) Tuoi: Integer; tuoi giang Giang: set(MON); End GIAOVIEN. id_m Class MON (1,n) properties MON tenmon Id_m: String; Tenmon: String; Sotiet: Integer; sotiet Giang: set(GIAOVIEN); End MON. Mô hình quan hệ GIAOVIEN(id_gv, hoten, tuoi) MON(id_m, tenmon, sotiet) GIANG(id_gv, id_m) 8 o Qui tắc 3: Quy tắc chuyển đổi mối quan hệ nhị nguyên n-n có kèm thuộc tính  Nếu mối quan hệ R của 2 tập thực thể A1 và A2 có kèm thuộc tính, khi đó, ngoài 2 lớp A1 và A2 tương ứng, ta cần bổ sung 1 lớp mới C đóng vai trò trung gian. Cụ thể, lớp C bao gồm các thuộc tính sau:  Các thuộc tính của mối quan hệ R.  Hai thuộc tính có khai báo: : : Ví dụ : id_gv GIAOVIEN hoten (1,n) tongsotiet giang (1,n) (1,1) tuoi KHOA id_k tenkhoa sodienthoai Mô hình quan hệ GIAOVIEN(id_gv, hoten, tuoi) KHOA(id_k, tenkhoa, sodienthoai) GVIEN_KHOA(id_gv, id_k, tongsotiet) Mô hình hướng đôối tượng Class GIAOVIEN properties Id_gv: allID; Hoten: String; Tuoi: Integer; Giang1: set(GVIEN_KHOA); End GIAOVIEN. Class KHOA properties Id_k: allID; Tenkhoa: String; Sodienthoai: String; Giang2: set(GVIEN_KHOA); End KHOA. Class GVIEN_KHOA properties Id_gvien_khoa: allID; Tongsotiet: Integer; Giang1: GIAOVIEN; Giang2: KHOA; End GVIEN_KHOA. 9 o Quy tắc 4: Qui tắc chuyển đổi mối quan hệ phản xạ. Việc chuyển đổi được thực hiện tương tự như mối quan hệ nhị nguyên (bước 2 và bước 3) Ví dụ : Mối quan hệ phản xạ id cha, me (1,1) Mô hình hướng đôối tượng Class NGUOI NGUOI properties hoten Id: allID; Hoten: String; tuoi con Tuoi: Integer; (0,n) Con: set(NGUOI); Cha, Me: NGUOI; End GIAOVIEN. Sinh Mô hình quan hệ o Quy tắc 5: Quy tắc chuyển đổi mối quan hệ đa nguyên. Việc chuyển NGUOI(id, hoten, tuoi, id_cha, id_me) đổi được thực hiện tương tự như mối quan hệ nhị nguyên n-n có thuộc tính (bước 3) Ví dụ : mối quan hệ đa nguyên Id_gv GIAOVIEN Hoten (0, n) DAY (1, n) (1, n) Thoigian LOP Id_lop MONHOC Id_monhoc Sotiet Kết quả chuyển đổi thành mô hình hướng đối tượng 10 Class GIAOVIEN properties Id_gv: String; Hoten: String; End GIAOVIEN. Class LOP properties Id_lop: String; End LOP. Class MONHOC properties Id_monhoc: String; Sotiet: Integer; End MONHOC. Class LICHDAY properties Thoigian: String; Giang: GIAOVIEN; Gomco: MONHOC; Botri: LOP; 8. Truy vấn trong cơ sở dữ liệu hướng đối tượng và ODMG 3.0 : End LICHDAY. 9. Phân mảnh trong CSDL phân tán: Phân mảnh (theo chiều ngang, dọc, kết hợp), bản sao (replication), cấp phát trong CSDL phân tán:  Mô hình phân đoạn của một CSDL là việc định nghĩa tập các cách phân đoạn bao gồm các thuộc tính và tuple trong CSDL và việc thoả các điều kiện để có xây dựng CSDL ban đầu từ các phân đoạn bằng cách sử dụng các toán tử OUTER UNION (hoặc OUTER JOIN) và UNION.  Nếu một phân đoạn được lưu trữ ở nhiều site, ta nói rằng phân đoạn đó được sao lưu (replicated). 9.1 Phân mảnh ngang (horizontal fragmentation):  Phân mảnh ngang một quan hệ tổng thể n-bộ R là tách R thành các quan hệ con n-bộ R1, R2, ..., Rk sao cho quan hệ R có thể được khôi phục lại từ các quan hệ con này bằng phép hợp: R = R1 R2 ...      Rk . Phân mảnhđoạn ngang một quan hệ là tập con của các bộ trong quan hệ đó. Các bộ thuộc về phân đoạn nào thì được chỉ ra bằng điều kiện về tính chất của quan hệ. Phân đoạn ngang chia ngang một quan hệ bằng cách nhóm các dòng tạo thành tập con các bộ. Phân đoạn ngang có được từ việc phân hoạch quan hệ primary thành các các quan hệ secondary, các quan hệ này liên kết với quan hệ primary thông qua khoá ngoại. 11  Phân đoạn ngang của quan hệ R được viết là (R) trong đại số quan hệ 9.2 Phân mảnh dọc (vertical fragmentation):  Phân đoạn dọc chia một quan hệ theo chiều dọc bởi các cột  Mỗi phân đoạn dọc của quan hệ chỉ lưu các thuộc tính của quan hệ  Phân đoạn dọc của quan hệ R được viết là trong đại số quan hệ  Một tập các phân đoạn dọc mà phép chiếu danh sách L1,L2,…,Ln gồm tất cả các thuộc tính trong R nhưng chỉ chia sẻ chỉ thuộc tính khoá của R gọi là phân đoạn đầy đủ của R.  Trong trường hợp này, phép chiếu danh sách thoả: o o với mọi i ≠ j trong đó ATTTRS(R) là tập các thuộc tính của R và PK(R) là khoá chính của R.  Để xây dựng lại R từ các phân đoạn dọc ta sử dụng toán tử OUTER UNION trên phân đoạn dọc.  Phân mảnh dọc một quan hệ tổng thể n-bộ R là tách R thành các quan hệ con R1, R2, ..., Rk sao cho quan hệ R có thể được khôi phục lại từ các quan hệ con này bằng phép nối: R = R1 R2 ..., Rk 9.3 Phân mảnh kết hợp (hybrid fragmentation):  Là việc tổ hợp phân đoạn dọc và phân đoạn ngang.  Quan hệ ban đầu có thể xây dựng lại bằng cách áp dụng các toán tử UNION và OUTER UNION.  Thông thường, mỗi phân đoạn của quan hệ R có được bằng cách tổ hợp toán tử SELECT−PROJECT, kí hiệu ΠL(σC(R)): o If C = TRUE and L ≠ ATTRS(R): phân đoạn dọc. o If C ≠ TRUE and L = ATTRS(R): phân đoạn ngang o If C ≠ TRUE and L ≠ ATTRS(R): phân đoạn hỗn hợp. • • • Ví dụ: Xét cơ sở dữ liệu của một công ty phần mềm được tổ chức như sau: NHANVIEN (MANV, TENNV, CHUCVU): quan hệ này chứa dữ liệu về nhân viên của công ty. TLUONG (CHUCVU, LUONG): quan hệ này chứa dữ liệu liên quan về lương và chức vụ của nhân viên. DUAN (MADA, TENDA, NGANSACH): quan hệ này chứa dữ liệu về các dự án mà công ty đang thực hiện. HOSO (MANV, MADA, NHIEMVU, THOIGIAN): quan hệ này chứa dữ liệu về hồ sơ của nhân viên được phân công thực hiện dự án). 12 NHANVIEN(E) MANV HOSO(G) TENNV CHUCVU A1 A2 MANV A3 A4 A1 A5 A2 A6 A3 A7 A4 A8 A5 Nam Trung TENNV Đông Bắc Nam Tây Trung Hùng Đông Dũng Bắc Chiến Tây Phân tích HT Lập trình viên CHUCVU Phân tích HT Phân tích HT Lập trình viên Kỹ sưtích HT Phân điện Phân tích HT Thiết kế DL Lập trình viên A6 A7 A8 Hùng Dũng Chiến Kỹ sư điện Phân tích HT Thiết kế DL DUAN(J) MADA D1 D2 D3 D4 TENDA NGANSACH CSDL CÀI ĐẶT BẢO TRÌ PHÁT TRIỂN 20000 12000 28000 25000 TLUONG(S) CHUCVU Kỹ sư điện Phân tích HT Lập trình viên Thiết kế DL LUONG 1000 2500 3000 4000 13 14 10. Xử lý truy vấn trong CSDL phân tán:  Vai trò của thể xử lý vấn tin phân tán là ánh xạ câu truy vấn cấp cao trên một CSDL phân tán vào một chuỗi các thao tác của đại số quan hệ trên các mảnh, thể hiện các bước: o Câu truy vấn phải được phân rã thành một chuỗi các phép toán quan hệ được gọi là vấn tin đại số. o Thứ hai, dữ liệu cần truy xuất phải được cục bộ hóa để các thao tác trên các quan hệ được chuyển thành các thao tác trên dữ liệu cục bộ (các mảnh). o Cuối cùng câu truy vấn đại số trên các mảnh phải được mở rộng để bao gồm các thao tác truyền thông và được tối ưu hóa để hàm chi phí là thấp nhất.  Hàm chi phí muốn nói đến các tính toán như thao tác xuất nhập đĩa, tài nguyên CPU, và mạng truyền thông. Bài toán xử lí vấn tin:  Có hai phương pháp tối ưu hóa cơ bản được sử dụng trong các bộ xử lý vấn tin: o Phương pháp biến đổi đại số o Chiến lược ước lượng chi phí.  Phương pháp biến đổi đại số đơn giản hóa các câu vấn tin nhờ các phép biến đổi đại số nhằm hạ thấp chi phí trả lời câu vấn tin, độc lập với dữ liệu thực và cấu trúc vật lý của dữ liệu.  Nhiệm vụ chính của thể xử lý vấn tin quan hệ là biến đổi câu vấn tin cấp cao thành một câu vấn tin tương đương ở cấp thấp hơn được diễn đạt bằng đại số quan hệ. Việc biến đổi này phải đạt được cả tính đúng đắn lẫn tính hiệu quả. Ví dụ 1:Xét một tập con của lược đồ CSDL đã được cho NV( MNV, TênNV, Chức vụ) PC (MNV, MDA, Nhiệm vụ, Thời gian) Và một câu truy vấn đơn giản sau: “Liệt kê tên của các nhân viên hiện đang quản lý một dự án” Biểu thức truy vấn bằng phép tính quan hệ theo cú pháp của SQL là: SELECT TênNV FROM NV, PC WHERE NV.MNV=PC.MNV AND Nhiệmvụ=”Quảnlý” Hai biểu thức tương đương trong đại số quan hệ do biến đổi chính xác từ câu vấn tin trên là: 15 TênNV( Nhiệmvụ=”Quảnlý” NV.MNV=PC.MNV (NV x PC)) và TênNV(NV|><|MNV(Nhiệmvụ=” Quảnlý” (PC))) - Hiển nhiên là trong câu vấn tin thứ hai, chúng ta tránh sử dụng tích Descartes, vì thế tiêu dùng ít tài nguyên máy tính hơn câu vấn tin thứ nhất và vì vậy nên được giữ lại. - Trong các hệ phân tán, đại số quan hệ không đủ để diễn tả các chiến lược thực thi. Nó phải được cung cấp thêm các phép toán trao đổi dữ liệu giữa các vị trí. Bên cạnh việc chọn thứ tự cho các phép toán đại số quan hệ, thể xử lý vấn tin phân tán cũng phải chọn các vị trí tốt nhất để xử lý dữ liệu, và có thể cả cách biến đổi dữ liệu. Ví dụ 2:Thí dụ này minh họa tầm quan trọng của việc chọn lựa vị trí và cách truyền dữ liệu của một câu vấn tin đại số. Chúng ta xét câu vấn tin của thí dụ trên: TênNV(NV|><|MNV(Nhiệmvụ=”Quảnlý”(PC))) chúng ta giả sử rằng các quan hệ NV và PC được phân mảnh ngang như sau: NV1=MNV  “E3”(NV) NV2=MNV > “E3”(NV) PC1=MNV  “E3”(PC) PC2=MNV  “E3”(PC) Các mảnh PC1, PC2, NV1, NV2 theo thứ tự được lưu tại các vị trí 1, 2, 3 và 4 và kết quả được lưu tại vị trí 5. 16 Mũi tên từ vị trí i đến vị trí j có nhãn R chỉ ra rằng quan hệ R được chuyển từ vị trí i đến vị trí j. Chiến lược a) sử dụng sự kiện là các quan hệ được phân mảnh theo cùng một cách để thực hiện song song các phép toán chọn và nối. Chiến lược b tập trung tất cả các dữ liệu tại vị trí lưu kết quả trước khi xử lý câu truy vấn. Sử dụng mô hình chi phí đơn giản, giả sử:  Thao tác truy xuất một bộ (tuple access) được ký hiệu là tupacc, là một đơn vị và thao tác truyền một bộ (tuple transfer) tuptrans là 10 đơn vị.  Các quan hệ NV và PC tương ứng có 400 và 1000 bộ, và có 20 giám đốc dự án thống nhất cho các vị trí.  Các quan hệ PC và NV được gom cục bộ tương ứng theo các thuộc tính Nhiệmvụ và MNV. Vì vậy có thể truy xuất trực tiếp 17 đến các bộ của PC dựa trên giá trị của thuộc tính Nhiệmvụ (tương ứng là MNV cho NV). * Tổng chi phí của chiến lược a có thể được tính như sau: 1.Tạo ra PC’ bằng cách chọn trên PC cần (10+10)* tupacc = 20 2. Truyền PC’ đến vị trí của NV cần (10+10)*tuptrans = 200 3. Tạo NV’ bằng cách nối PC’ và NV’ cần (10+10)*tupacc*2 = 40 4. Truyền NV’ đến vị trí nhận kết quả cần (10+10)*tuptrans = 200 Tổng chi phí 460 * Tổng chi phí cho chiến lược b có thể được tính như sau: 1. Truyền NV đến vị trí 5 cần 400*tuptrans = 4.000 2. truyền PC đến vị trí 5 cần 1000*tuptrans =10.000 3. Tạo ra PC’ bằng cách chọn trên PC cần 1000*tupacc = 1.000 4. Nối NVvà PC cần 400*20*tupacc = 8.000 Tổng chi phí là 23.000  Chỉ số đánh giá tiêu dùng tài nguyên là tổng chi phí (total cost) phải trả khi xử lý truy vấn.  Tổng chi phí là tổng thời gian cần để xử lý các phép toán vấn tin tại các vị trí khác nhau và truyền dữ liệu giữa các vị trí.  Một công cụ khác là thời gian đáp ứng của câu vấn tin, là thời gian cần thiết để chạy câu vấn tin.  Trong môi trường CSDL phân tán, tổng chi phí cần phải giảm thiểu là chi phí CPU, chi phí xuất nhập và chi phí truyền.  Độ phức tạp của các phép toán quan hệ: o Các phép toán chọn, Chiếu (Không loại bỏ trùng lặp) có độ phức tạp là O(n). o Các phép chiếu (Có loại bỏ trùng lặp), trùng lặp, nối, nối nửa, chia có độ phức tạp là O(n*logn). o Tích Descartes có độ phức tạp là O(n2) (N biểu thị lực lượng của quan hệ nếu các bộ thu được độc lập với nhau)  Đánh giá: o Các thao tác có tính chọn lựa làm giảm đi lực lượng cần phải thực hiện trước tiên. o Các phép toán cần phải được sắp xếp để tránh thực hiện tích Descartes hoặc để lại thực hiện sau. 18 11. Lịch tuần tự, khả tuần tự của các giao tác:  Lịch biểu(dãy có thứ tự) là môt dãy các thao tác của một tập các giao tác mà trong đó thứ tự các thao tác trong mỗi giao tác được bảo toàn. Ví dụ1 : Xét 2 giao tác chuyển tiền:  10$ từ A -> B  20$ từ B -> C T1 Read (A) A = A- 10 Write (A) Read(B) B = B +10 Write (B) T2 Read (B) B = B- 20 Write (B) Read(C) C = C +20 Write (C) T1 T2 Read (A) Read (B) A = A- 10 B = B- 20 Write (A) Write (B) Read(B) Read(C) B = B +10 C = C +20 Write (B) Write (C)  Lịch biểu tuần tự (Serial Schedule): Là lịch biểu mà trong mỗi giao dịch các thao tác được thực hiện kế tiếp nhau, không có thao tác của giao dịch khác xen vào (Thực hiện lần lượt, hết giao dịch này đến giao dịch khác) o Không thể có đụng độ trong lịch biểu tuần tự. o Với 1 tập S có n giao tác thì sẽ có n! lịch biểu tuần tự. Ví dụ : Với 2 giao tác chuyển tiền ví dụ 1, ta có 1 lịch tuần tự như sau: T1 Read (A) A = A- 10 Write (A) Read(B) B = B +10 T2 19 Write (B) Read (B) B = B- 20 Write (B) Read(C) C = C +20 Write (C)  Lịch biểu không tuần tự (non serial schedule): là lịch biểu mà các thao tác trong các giao dịch được đan xem vào nhau. Ví dụ : T1 T2 Read (A) Read (B) A = A- 10 B = B- 20 Write (A) Write (B) Read(B) Read(C) B = B +10 C = C +20 Write (B) Write (C)  Tính khả tuần tự của lịch biểu: Lịch biểu gọi là khả tuần tự (serializable) nếu nó tương đương với một lịch biểu tuần tự. o Tương đương theo nghĩa cho ra cùng 1 trạng thái CSDL sau khi kết thúc việc thực hiện lịch biểu. o Lịch biểu bất khả tuần tự nếu nó không tương đương với 1 lịch biểu tuần tự. Ví dụ : T1 Read (A) A = A- 10 Write (A) Read(B) B = B +10 Write (B) T2 Read (B) B = B- 20 Write (B) 20