Schema Transformations

Schema Transformations Cùng mô hình nghiệp vụ (business domain) có thể được mô hình hóa trong nhiều cách khác nhau. Cùng 1 sơ đồ ý niệm có thể ánh xạ thành lược đồ logical theo nhiều cách Cùng 1 lược đồ logical có thể được thực thi theo nhiều cách khác nhau. Sự tương đương giữa các lược đồVí dụ 1Lược đồ ý niệm với quan hệ 2 ngôiHai lược đồ có tương đương nhau không?? Ví dụ 1Từ các quan hệ 1 ngôi trong sơ đồ 1 có thể dịch thành các quan hệ 2 ngôi trong sơ đồ 2Patient smokes iff Patient indulges in Vice 'S' Patient drinks iff Patient indulges in Vice 'D' Và ngược lạiPatient indulges in Vice iff Patient smokes and Vice has ViceCode 'S' or Patient drinks and Vice has ViceCode 'D'  Tương đương ngữ cảnh (contextual equivalence )Ví dụ 1Tương đương ngữ cảnh vì nó bổ sung ngữ cảnh có tính định nghĩa (definitional context) vào sơ đồ gốc, thừa nhận có "virtual object types" (e.g., Vice tồn tại ngầm định trong lược đồ 1)Contextual equivalenceTương đương lược đồ trong UMLViệc săp xếp lại 1 lược đồ này cho giống với 1 lược đồ khác gọi là phép biến đổi lược đồ ý niệm. Có thể thực hiện nhiều phép biến đổi phức trong ORM mà không cần phải dùng đến các chú thích để hỗ trợConceptual schema transformationGiúp ta phân biệt được sự khác biệt giữa các chọn lựa thiết kế.Nếu 2 lược đồ được xây dựng độc lập với nhau có thể tích hợp với nhau 1 phần hay hoàn toàn, chỉ cần giải quyết được sự khác nhau trong cách mà mỗi lược đồ dùng để mô hình miền nghiệp vụ. Lợi điểm khi dùng phép biến đổiNhờ phép biến đổi lược đồ ý niệm mà có thể thay đổi 1 lược đồ gốc thành 1 lược đồ khác có thể dễ dàng hơn cho việc thực thi. Quá trình biến đổi này được gọi là conceptual schema optimization.Tối ưu hóa lược đồ ý niệmTừ 2 lược đồ ý niệm trong ví dụ 1, tạo các cấu trúc bảng (table scheme ) và bảng phân bố mẫu tương ứng như sau:Ví dụTrong 1 số ứng dụng thì dùng dạng 1 (1 bảng) hiệu quả hơn, không cần phải thực thi phép join khi muốn hiển thị thông tin mọi bệnh nhân. Nhưng nếu các tật nghiện (vice) thường xuyên thay đổi thì giải pháp dùng 2 bảng lại hiệu quả hơn Nếu sau khi tối ưu hóa 1 lược đồ ý niệm khi ánh xạ sang bảng không hiệu quả thì có thể dùng phép denormalization. So sánh 2 cấu trúc bảngChuyên biệt hóa và khái quát hóa Predicate tương tự như chuyên biệt hóa và khái quát hóa các loại đối tượng, nhưng không cần phải xác định mối liên kết subtype nào giữa các predicate Một predicate có thể được specialized nếu ràng buộc giá trị (value constraint) hay ràng buộc tần số (frequency constraint) là 1 số hữu hạn.Trong ví dụ drinker-smoker, Vice có ràng buộc giá trị { 'S', 'D' }Predicate Specialization and Generalization Vì có chính xác 3 loại huy chương , quan hệ 3 ngôi (ternary) có thề được chuyên biệt hóa thành 3 quan hệ 2 ngôi, mỗi ngôi cho 1 loại huy chương. Khi loại đồi tượng MedalKind được sáp nhập (is absorbed) vào predicate 3 ngôi, nó chia thành( chuyên biệt hóa) thành 3 predicate 2 ngôi.  Phép biến đổi này được gọi là object type absorption. Object type absorptionPhép biến đổi ngược lại khái quát hóa từ 3 quan hệ nhị phân thành 1 quan hệ tam phân bằng cách rút ra (extracting) loại đối tượng MedalKind Phép biến đổi này được gọi là object type extraction.Object type extractionIn general, when an n-valued object type is absorbed into a predicate, the n specialized predicates that result each have one less role than the original (since the object type has been absorbed). Object type absorption/ extractionPSGI: “R có thể được chuyên biệt hóa thành S1 .. Sn bằng cách sáp nhập B”Predicate Specialization/Generalization theorem 1 (PSG1).Các predicate R và S, theo thứ tự, có m + 1 roles và m roles, với m  1. Các loại đối tượng A1 .. Am và B không cần phân biệt. Loại giá trị của B có n giá trị b1 .... bn. Nếu m =1 biến đổi 1 quan hệ hai ngôi (binary) thành n quan hệ 1 ngôi (unary)Nếu m = 2, biến đổi 1 quan hệ 3 ngôi thành n quan hệ nhị phân. Định lý PSG1 (Predicate specialization/Generalization)Phép biến đổi từ trái sang phải chuyên biệt hóa predicate R thành n predicate S1 .. Sn bằng cách sát nhập loại đối tượng B. Phép biến đổi ngược lại từ phải sang trái khái quát hóa các predicate ngắn hơn thành 1 predicate dài hơn bằng cách rút ra B. Định lý PSG1PSG1 vẫn đúng ngay cả khi có các ràng buộc khác được thêm vào. Tuy nhiên khi bất kỳ 1 ràng buộc nào được bổ sung vào thì phải biến đổi thành 1 ràng buộc phụ tương đương trong lược đồ biến đổi tương ứng. Hệ quả: If a UC in R spans a combination of B's role and other roles, a UC spans the specialization of these other roles in S1 .. Sn; and conversely.Hệ quả của PSG1UC trong các lược đồ tương đương Các UC trong lược đồ trái tương đương với các ràng buộc loại trừ (exclusion constraint ) trong lược đồ phải. Exclusion constraint means that no row of values may appear in more than one of the Si fact tablesVí dụ về UC trong các lược đồ tương đươngUC bên lược đồ trái tương đương với ràng buộc loại trừ (exclusion constraint) bên lược đồ phải.Ví dụ 2If a UC spans all roles of R except for B's role, then S1, .. Sn, are mutually exclusive; and conversely.Phép biến đổi và UCIf Ai’s role (or role disjunction) in R is mandatory, then the disjunction of its specialized roles is mandatory, and conversely (1  i  m). Phép biến đổi và ràng buộc bắt buộcVí dụ phép biến đổi role bắt buộcRàng buộc bắt buộc (mandatory constraint) trong sơ đồ (a) Ánh xạ thành 1 ràng buộc inclusive-or trong sơ đồ (b).If R is a ternary with a UC spanning just B's role and one other role, then adding a frequency constraint of n to this other role is equivalent to adding an equality constraint over the specialized versions of that role. Phép biến đổi và ràng buộc ngang bằngVí dụ về ràng buộc ngang bằngIf R is a ternary with a UC spanning just B's role and one other role, then adding a mandatory role constraint and frequency constraint of n (the number of possible values for B) to this other role is equivalent to making each specialized version of that role mandatory. Phép biến đồi và ràng buộc bắt buộc và tần sốVí dụ UC ngoài trong (a) chỉ ra rằng mỗi xe có nhiều nhất một lái xe chính (main driver) và nhiều nhất 1 lái xe dự trữ (backup driver). Ví dụLược đồ (a) được ánh xạ thành (b) bằng cách sáp nhập loại đối tượng DriverStatus vào predicate “drives”, chuyên biệt hóa thành 2 predicate main driver và backup driver. Phép biến đổi ngược lại khái quát hóa các predicate driver chuyên biệt thành một predicate tổng quát bằng cách rút ra loại đối tượng DriverStatus.Vì loại đối tượng này xuất hiện trong 1 loại quan hệ khác, không phù hợp với PSG 1. Ví dụPSG2 (predicate specialization/ generalization theorem) "LHS" viết tắt của "left-hand schema" “RHS” viết tắt của "right-hand schema". Bốn hệ quả của PSG2 A, B và C tương ứng với Driver, DriverStatus, và Car; Ràng buộc ngang bằng được ngầm định bởi 2 ràng buộc role bắt buộc trên Driver. Ví dụ về PSG2Có thể chuyên biệt hóa sơ đồ ???Mặc dù không có loại đối tượng DriverStatus nhưng ràng buộc tần số (frequency constraint) cho thấy là each car has at most two drivers  cho phép chuyên biệt hóa thành 2 trường hợpVí dụ 2Vì việc phân biệt ra 2 trường hợp này không có trong sơ đồ gốc nên phép biến đổi này không tương đương với lược đồ gốcVí dụ 2Page 708ExerciseLiên quan đến việc biến đổi 1 lược đồ ý niệm thành 1 lược đồ ý niệm khác mà có thể thực thi hiệu quả hơn. Bốn yếu tố cần xem xét khi tối ưu hóa lược đồ: Target systemQuery patternUpdate patternClarity.Tối ưu hóa lược đồ ý niệm(Conceptual schema optimization )Trước khi tối ưu hóa,lược đồ ý niệm toàn cục phải được hoàn tất và hợp lệ Bất kỳ chọn lựa ánh xạ nào cũng nên khai báo. Thủ tục bao gồm hai giai đoạn chính sau: Transform to reduce the number of mapped tables (steps 1 and 2) Transform to simplify individual tables (steps 3-5)Thủ tục tối ưu hóa lược đồ ý niệmQuy trình ánh xạ từ lược đồ ý niệm thành lược đồ quan hệ được gọi là deconceptualization Ngày nay các nhà thiết kế database thường tạo lược đồ ý niệm trước bằng ORM, ER, hay UML sau đó áp dụng thủ tục ánh xạ để tạo lược đồ quan hệ.Trước đây khi thiết kế database, thường dùng kỹ thuật normalization, một số người hiện vẫn dùng kỹ thuật này chủ yếu để tinh chỉnh lược đồ quan hệ. So sánh kỹ thuật Normalization và deconceptualization Nếu lược đồ ý niệm là đúng, thì thiết kế bảng bằng Rmap luôn ở dạng chuẩn, vì vậy các nhà mô hình hóa ORM không cần phải dùng đến kỹ thuật chuẩn hóa. Tuy nhiên biết về normalization giúp hợp nhất được hướng thiết kế và tạo điếu kiện để làm việc với những người còn sử dụng phương pháp cũ normalization.So sánh kỹ thuật Normalization và deconceptualization Có hai kỹ thuật chuẩn hóa:Synthesis Decomposition ( hay còn gọi "analysis").Mỗi kỹ thuật chỉ thực hiện trên các lược đồ quan hệ và tập các phụ thuộc hàm (functional dependencies - FD). Kết quả chuẩn hóa: tập các bảng ở dạng chuẩn (normal form)Kỹ thuật chuẩn hóaCác dạng chuẩnMột bảng không ở dạng chuẩn 1NF thì được gọi là "unnormalized" hay Non-First Normal Form (NFNF = NF2). Một bảng ở dạng chuẩn cao hơn cũng có nghĩa là nó cũng ở các dạng chuẩn thấp hơnVí dụ: một bảng ở dạng 3NF đương nhiên ở dạng chuẩn 1NF và 2NFCác dạng chuẩnDạng chuẩn nào??Chuẩn NF2Repeat attribute : regNr, course, ratingRepeat group: Result Ví dụ 1Dạng chuẩn nào??Bảng (a): 2NFBảng (b): 1NFVí dụ 2Nếu dựa vào bảng (b), phát biểu các luật cơ bản (elementary facts), rồi xây dựng lược đồ ý niệm và dùng Rmap để có lược đồ quan hệVí dụ 2Dạng chuẩn nào??Bảng (a): 3NFBảng (b) : 2NFVí dụ 3Lược đồ ý niệm cho hình (b) và lược đồ quan hệ đúng bằng kỹ thuật RmapVí dụ 3Một khóa được gọi là khóa sơ cấp nếu có một FD từ nó đến 1 số thuộc tính khác trong bảng. Một thuộc tính được gọi là thuộc tính khóa sơ cấp (elementary key attribute) nếu nó thuộc vào 1 trong các khóa sơ cấp. Khóa sơ cấp (elementary key )Có 2 khóa sơ cấp là cityNr và (cityName, stateCode)Bảng thuộc dạng chuẩn nào??? Elementary key normal form (EKNF) Ví dụ 4Một lược đồ bảng ở dạng EKNF nếu và chỉ nếu tất cả các FD của nó đểu bắt đầu từ cả khóa hay kết thúc ở các thuộc tính khóa cơ bản. Elementary key normal form (EKNF) Bảng ở dạng chuẩn nào? Chuẩn BCNF?Dạng chuẩn EKNFVí dụ 5Dùng Rmap để tạo lược đồ quan hệ đúngBảng ở dạng chuẩn BCNFVí dụ 5Dạng chuẩn Boyce CoddA table T in a database schema with FD set F is said to be in Boyce-Codd normal form (BCNF) when the following property holds. For any functional dependency X → A implied by F that lies in T, where A is a single attribute that is not in X, X must be a superkey for T. A database schema is in BCNF when all the tables it contains are in BCNF. Ví dụ về BCNFKhảo sát 1 lược đồ quan hệ để quản lý lịch làm việc của nhân viên. Mỗi nhân viên (employee) làm việc 1 hay 2 ca (shift) mỗi ngày ở cửa hàng. Mỗi ca 4 tiếng. Trong mỗi ca, nhân viên sẽ được phân làm việc ở bộ phận (station) nào đó trong cửa hàng ( như quầy thâu ngân, kho sách,) . Chỉ có duy nhất 1 nhân viên cho mỗi bộ phận trong suốt ca làm việc. Lược đồ quan hệ được thiết kế như sau:schedule (employee ID, date, shift, station, worked shift?)Ví dụVới quy tắc nghiệp vụ (one person per station per shift), có hai khóa dự tuyển cho lược đồ trên là:employee ID + date + shift date + shift + station Các FD của lược đồ :employee ID + date + shift - > station, worked shift? date + shift + station - > employee ID, worked shift? Lược đồ thuộc chuẩn BCNF?? FOURTH NORMAL FORM Khảo sát 1 lược đồ quan hệ sau: movie info ( title , star , producer )Một phim có thể có nhiều hơn 1 star, cũng có thể có nhiều hơn 1 producer. Cùng 1 star có thể đóng nhiều hơn 1 phim, 1 producer có thể làm nhiều hơn 1 phim. FOURTH NORMAL FORM Khóa của lược đồ bao gồm tất cả các thuộc tính  không có thuộc tính không khóa  Lược đồ ở dạng chuẩn BCNFTuy nhiên lược đồ này có các bất thường (anomalies):You cannot insert the stars of a movie without knowing at least one producer. You cannot insert the movie ‘s producer without knowing at least one star. If you delete the only producer from a movie, you lose information about its stars. If you delete the only star from a movie, you lose information about its producers. Each producer ’ s name is duplicated for every star in the movie. By the same token, each star ’ s name is duplicated for each movie producer. FOURTH NORMAL FORMCó ít nhất 2 entity không liên quan gì đến nhau trong quan hệ này:Một thực thể quản lý mối quan hệ giữa phim và các star của nóMột thực thể quản lý mối quan hệ giữa phim và các producers của nó.Gây ra bất thườngFOURTH NORMAL FORMĐịnh nghĩa: Quan hệ ở dạng chuẩn 4NF nếu nó ơ dạng chuẩn BCNF và không có phụ thuộc đa trị (multivalued dependency) Phụ thuộc đa trị Multivalued Dependency Phụ thuộc đa trị xảy ra khi với mỗi giá trị của thuộc tính A, tồn tại 1 tập hữu hạn các giá trị của thuộc tính B có liên quan và 1 tập hữu hạn các giá trị của thuộc tính C cũng có liên quan đến giá trị của thuộc tính A đó. Thuộc tính B và C độc lập nhau.Với mỗi tiêu đề phim (movie title) có 1 nhóm các diễn viên (stars) có liên quan đến phim đó. Cũng với mỗi phim có 1 nhóm các đạo diễn (producers) của phim đó. Các diễn viên và nhà sản xuất phim độc lập nhau. Phụ thuộc đa trị Multivalued Dependency Ký hiệu:title - >> star title - >> producer Đọc là “title multidetermines star and title multidetermines producer. ” FD là trường hợp đặc biệt của phụ thuộc đa trị nhưng thuộc tính được xác định chỉ là 1 giá trị đơn hơn là 1 nhóm các giá trị. Chuẩn hóa dạng 4NFĐể loại bỏ phụ thuộc đa trị và chuẩn hóa thành dạng chuẩn 4NF: phân rã quan hệ, đặt mỗi phần của phụ thuộc vào 1 quan hệ riêng:movie stars ( title , star ) movie producers ( title , producer ) Có thể thêm hay xóa các diễn viên hay nhà sản xuất 1 cách tùy ý mà không bị ảnh hưởng lẫn nhau. Tên các diễn viên và nhà sản xuất chỉ xuất hiện 1 lần cho mỗi phim