CHƯƠNG 5 MÔ HÌNH HÓA DỮ LIỆU BẰNG PHƯƠNG PHÁP LÙI
I. C ÁC CấU TRÚC KIểU
Để xây dựng các mô hình dữ liệu, người ta đưa vào các cấu trúc kiểu đặc thù cho hệ thống thông tin mà nó biểu diễn. Các cấu trúc kiểu gồm :
Các cấu trúc kiểu cơ sở : PHIẾU, CHA-CON, BẢNG.
Các cấu trúc kiểu đặc biệt được tổ hợp từ các cấu trúc kiểu cơ sở, đó là :
HOẠCHĐỊNH, CÓ-KHÔNG, PHẢNXẠ, BÌNHĐẲNG, THỪAKẾ và KẾTTỤ.
I.1. Cấu trúc kiểu PHIẾU
Cấu trúc kiểu PHIẾU (FICHE) cho phép mô tả tường minh một thực thể và các thành phần của thực thể như khóa, các thuộc tính và sự PTH giữa khóa và các thuộc tính của thực thể.
Từ một phiếu dữ liệu (thu lượm được từ bài toán đang phân tích), có thể dễ dàng chuyển thành kiểu thực thể tương ứng.
Ví dụ
Phiếu dữ liệu Kiểu thực thể tương ứng
PHIẾU KHÁCH HÀNG → KHÁCHHÀNG
Mã số khách hàng : ...
Tên khách hàng : ...
Địa chỉ khách hàng : ...
Điện thoại khách hàng : ...
Doanh số năm trước : ...
MãKH TênKH ĐịaChỉKH ĐiệnThoạiKH DSốNăm-1
Thực thể KHÁCHHÀNG nhận được từ phiếu khách hàng cho biết : mỗi khách hàng được đồng nhất bởi một MãKH, vì với một MãKH, chỉ có một và chỉ một khách hàng. Như vậy MãKH là khóa của thực thê KHÁCHHÀNG.
Những dữ liệu khác là các thuộc tính của thực thể KHÁCHHÀNG. Vì rằng tồn tại sự PTH giữa khóa MãKH và mỗi một thuộc tính này, sao cho MãKH là nguồn và các thuộc tính là đích. Như vậy, mỗi giá trị MãKH chỉ tương ứng với một giá trị của hoặc TênKH, hoặc ĐịaChỉKH, hoặc ĐiệnThoạiKH, hoặc DSốNăm-1.
I.2. Cấu trúc kiểu CHA-CON
Cấu trúc kiểu CHA-CON (père-fils) liên quan đến sự kết hợp phân cấp (hay phụ thuộc toàn vẹn hàm − CIF) và sự PTH giữa khóa và nhiều thực thể.
Ví dụ
PHIẾU KIỂU CHỖ
Kiểu chỗ : ...
Giá ⁄ Ngày ⁄ Người : ...
Danh sách các chỗ : ...
Số TT Chỗ số. Diện tích Số người tối đa ... ... ... ...
... ... ... ...
Phiếu trên tạo ra các thực thể CHỖ, KIỂU và kết hợp phân cấp Thuộc về ⁄ Tính tiền. Việc phân tích phiếu chỉ ra rằng, một số dữ liệu chỉ nhận một giá trị cho một phiếu, ở đây là cho một phiếu kiểu chỗ (“lều bạt”, “xe nhà ở”...). Đó là trường hợp của các dữ liệu KiểuChỗ và
GiáNgàyNgười (giá cho một ngày và cho một người).
MãKH TênKH ĐịaChỉKH ĐiệnThoạiKH DSốNăm-1
Trong khi đó, các dữ liệu khác có thể nhận nhiều giá trị, như là ChỗSố, DiệnTích và SốNgườiMax. Vì rằng có thể có nhiều chỗ cùng kiểu chỗ. Người ta nói trường hợp này có hai luồng thông tin. Do đó, không thể xem những dữ liệu vừa nêu là thuộc về một thực thể duy nhất, mà là thuộc về hai thực thể.
Hình 5.1 Mô hình dữ liệu cấu trúc kiểu CHA-CON
Như vậy, hai thực thể quan hệ với nhau bởi kết hợp Thuộc về ⁄ Tính tiền và các bản số có nghĩa rằng một chỗ chỉ thuộc về một và chỉ một kiểu chỗ, một kiểu chỗ tính toán cho tối thiểu một chỗ và có thể cho nhiều chỗ (n). Các bản số chỉ ra kiểu kết hợp phân cấp hay CIF.
Hai thực thể nối nhau bởi một CIF tạo thành cấu trúc kiểu CHA-CON nói lên rằng, một cha có thể có nhiều con, nhưng mỗi con chỉ có một cha. Các thực thể CHỖ và KIỂU nói riêng là những cấu trúc kiểu PHIẾU. Mặt khác, trong cấu trúc kiểu CHA-CON, tồn tại sự PTH giữa hai khóa : ChỗSố → KiểuChỗ.
I.3. Cấu trúc kiểu BẢNG
Ví dụ :
Mỗi khách hàng đươc ghi chép vào một phiếu gồm mã (do công ty tự ấn định), tên họ, địa chỉ, điện thoại và doanh số hàng tháng như sau :
PHIẾU KHÁCH HÀNG
Mã khách hàng : ...
Tên khách hàng : ...
Địa chỉ : ...
Điện thoại : ...
Doanh số năm trước : ...
Doanh số hàng tháng : Giêng : ...
Hai : ...
Ba : ...
Tư : ...
Năm : ...
Sáu : ...
Bảy : ...
Tám : ...
Chín : ...
Mười : ...
Mười Một : ...
Mười Hai : ...
Cấu trúc kiểu BẢNG (TABLEAU) liên quan đến sự kết hợp không phân cấp hay CIM (phụ thuộc toàn vẹn bội), sự ghép các khóa và các PTH giứa các khóa của ít nhất hai thực thể và các thuộc tính của kết hợp không phân cấp.
Với mỗi khách hàng, có bao nhiêu tháng giao dịch trong năm thì sẽ có bấy nhiêu doanh số tháng. Mặt khác, lấy một tháng nào đó, có bao nhiêu khách hàng trong CSDL thì sẽ cớ bấy nhiêu doanh số tương ứng. Từ đó có bảng hai chiều như sau :
Thuộc về ⁄ Tính tiền CHỖ
ChỗSố.
DiệnTích SốNgườiMax
1 − 1 1 − n KIỂU
KiểuChỗ GiáNgàyNgười
Tháng
Khách hàng Giêng Hai Ba . . .
Khách hàng 1024 12 543 000 8 654 000 19 231 000 Khách hàng 1134 5 467 000 6 785 000 11 942 000 Khách hàng 1145 15 687 000 13 232 000 20 980 000 . . .
Trong bảng trên, dữ liệu DSốTháng phụ thuộc vào hai khóa là MãKH và Tháng. Có nghĩa giá trị của một doanh số tháng liên quan đến một khách hàng và tại một tháng đã cho.
Phiếu khách hàng được chuyển thành hai thực thể KHÁCHHÀNG và THÁNG. Tồn tại một kết hợp không phân cấp giữa hai thực thể này :
Hình 5.2 Mô hình dữ liệu cấu trúc kiểu BẢNG
Ta có một PTH với đích là DSốTháng và nguồn là ghép của các khóa của các thực thể tham gia vào kết hợp “Đã mua bán” :
Mã-KH + Tháng → DSốTháng
Trong thí dụ trên, ta tự giới hạn ở bảng hai chiều do các kết hợp phân cấp chỉ liên quan đến hai thực thể. Trong khi đó, các kết hợp không phân cấp lại có thể liên quan đến nhiều thực thể.
Với ba thực thể, ta có bảng bảng ba chiều. Với bốn thực thể, ta có bảng bốn chiều, v.v...
Tập hợp từ 2 đến n thực thể có quan hệ với nhau bởi một kết hợp không phân cấp được gọi là cấu trúc kiểu BẢNG.
Đã mua bán DSốTháng KHÁCHHÀNG
MãKH TênKH ĐịaChỉKH ĐiệnThoạiKH
DSốNăm-1
1 − n 1 − n
THÁNG Tháng TênTháng
I.4. Cấu trúc kiểu HOẠCHĐỊNH
Cấu trúc kiểu HOẠCHĐỊNH (planning) là trường hợp đặc biệt của cấu trúc kiểu BẢNG.
Một trong những thực thể bắt buộc hiện diện là thời gian. Trong thí dụ về cấu trúc kiểu BẢNG ở trên, có một thực thể thể hiện thời gian là tháng. Tuy nhiên đó không phải là một hoạch định.
Ta sẽ thấy rằng có sự phân biệt giữa cấu trúc HOẠCHĐỊNH và các cấu trúc kiểu khác.
Trong cấu trúc kiểu HOạCHĐịNH, có thực thể thể hiện THỜIGIAN. Người ta thường quan tâm đến chu kỳ thời gian là ngày.
Để quản lý việc thuê phòng trong một khách sạn, người ta cần biết hiện trạng của các phòng nhờ MãHiệnTrg có thể nhận các giá trị như sau :
T : phòng trống B : có người ở (phòng bận) Đ : phòng đã đặt trước Trong bảng dưới đây, ta thấy MãHiệnTrg phụ thuộc vào hai dữ liệu là NgàyThứ và PhòngSố.
Ngày
Phòng số 1 2 3 4 5 6 7 8 9 10 ...
T T T T T Đ Đ Đ T T
B B B B T T T Đ Đ Đ
B B B B T T T T T T
T T T T T T Đ Đ Đ Đ
T T T T Đ Đ Đ Đ Đ T
B B B B Đ Đ Đ Đ Đ Đ
Ngày hôm nay : 05/07/199 ...
Các thực thể PHÒNG và NGÀY nối với nhau bởi kết hợp không phân cấp “ Được thuê”.
Dữ liệu MãHiệnTrg là thuộc tính của kết hợp này.
Hình 5.3 Mô hình dữ liệu cấu trúc kiểu HOẠCHĐỊNH
Tồn tại PTH với đích là MãHiệnTrg, nguồn là do hai khóa PhòngSố và NgàyThứ ghép lại : PhòngSố + NgàyThứ → MãHiệnTrg
Cấu trúc kiểu HOẠCHĐỊNH có thể được tạo ra từ nhiều bảng (hai chiều, ba chiều hoặc nhiều chiều) tương ứng, tương tự cấu trúc kiểu BẢNG. Nếu cần quản lý chi tiết hơn về thời gian hoạt động, có thể sử dụng thêm những thực thể khác.
Chẳng hạn, nếu người ta muốn quản lý việc dành chỗ sân quần vợt vào những giờ giấc nào đó, cần phải thêm vào thực thể GIỜ và ta có mô hình dữ liệu sau :
Như vậy, với mỗi sân, mỗi ngày và mỗi giờ, ta có một giá trị của thuộc tính MãHiệnTrg : Sân số + NgàyThứ + GiơThuê ⎯→ MãHiệnTrg
Chú ý : Vậy khi nào thì phải tạo ra một thực thể thời gian ? Được thuê MãHiệnTrg PHÒNG
PhòngSố GiáNgày TầngSố
1 − n 1 − n NGÀY
NgàyThứ.
Hình 5.4 Cấu trúc kiểu HOẠCHĐỊNH nhiều chiều
Nếu như việc quản lý chỉ liên quan đến những ngày đặc biệt, chẳng hạn NgàyĐH (ngày đặt hàng) hoặc NgàyTToán (ngày thanh toán), thì không nên tạo thực thể thời gian, mà tạo ra các dữ liệu tương ứng, sau đó đặt chúng vào các thực thể liên quan với vai trò là những thuộc tính.
Ví du, NgàyĐH đưa vào thực thể ĐẶTHÀNG và NgàyTToán vào HÓAĐƠN. Khi đó, ta có thể sử dụng các PTH.
Tuy nhiên, khi thời gian là nguồn của một PTH, với vai trò là dữ liệu sơ cấp, hoặc thời gian là thành phần của một nguồn gồm nhiều thành phần ghép lại, thì phải tạo ra một thực thể thời gian. Chính vì vậy mà tên cấu trúc kiểu là HOẠCHĐỊNH.
I.5. Cấu trúc kiểu CÓ-KHÔNG
Được tạo thành từ các cấu trúc kiểu cơ sở BẢNG và CHA-CON.
Cấu trúc kiểu CÓ-KHÔNG (oui-non) dựa trên ý tưởng rằng một trường hợp cụ thể của một thực thể này ít khi tương ứng với một trường hợp cụ thể của một thực thể kia, mặc dầu giữa chúng có liên hệ với nhau bởi một kết hợp.
Người ta đưa vào khái niệm trường hợp cụ thể tuỳ ý của thực thể và sử dụng khái niệm ràng buộc toàn vẹn trong cấu trúc kiểu này.
Ví dụ
Hình 5.5 Mô hình dữ liệu cấu trúc kiểu CÓ-KHÔNG
Ở đây, sử dụng cấu trúc kiểu CHA-CON. Các bản số của ĐĐH-KH chỉ ra rằng, một đơn đặt hàng của khách hàng chỉ liên quan đến một và chỉ một sản phẩm. Bản số tối thiểu 1 có nghĩa tính ràng buộc toàn vẹn phải được kiểm tra : một trường hợp cụ thể của ĐĐH-KH phải tương ứng với một trường hợp cụ thể của SẢNPHẨM.
Các bản số của SẢN PHẨM chỉ ra rằng, một sản phẩm nào đó có thể không được đặt hàng, nhưng cũng có thể được đặt hàng nhiều lần. Bản số tối thiểu 0 chỉ ra rằng ở đây không có ràng buộc toàn vẹn. Đây là đặc trưng cuả cấu trúc kiểu CÓ-KHÔNG : một trường hợp cụ thể của
SÂNCHƠI SânSố ĐặcĐiểm
1 − n
1 − n 1 − n NGÀY
NgàyThứ. Được thuê
MãHiệnTrg
GIỜ GiờThuê
ĐĐH-KH SốĐĐH
MãKH NgàyĐH
SLĐặt SốTiền
SẢNPHẨM MãSP TênSP GiáĐơnVị
SLCó SLBáoĐộng
1 − 1 0 − n
Đặt hàng
một thực thể này có thể không tương ứng, hoặc tương ứng với một hoặc nhiều trường hợp cụ thể khác. Các bản số có thể là 0−1, hoặc 0−n.
Tuỳ theo quy tắc quản lý mà cấu trúc kiểu này tồn tại, tương ứng với bản số tối thiểu có giá trị 1, hoặc không tồn tại, bản số tối thiểu có giá trị 0. Cần phải hiểu được điều muốn diễn tả. Trong thí dụ trên, các sản phẩm có thể được nhiều đơn đặt hàng đến nhưng cũng có thể được tiêu thụ ở nơi bán, điều đó giải thích giá trị 0 của bản số tối thiểu.
I.6. Cấu trúc kiểu PHẢNXẠ
Cấu trúc kiểu PHẢNXA (reflex) có thể được kết hợp với các cấu trúc kiểu khác. Một số kết hợp không tạo ra mối liên hệ giữa hai (hay nhiều) thực thể. Tuy nhiên kết hợp có thể tồn tại trên cùng một thực thể. Khi đó kết hợp có tính phản xạ.
Có hai cấu trúc kiểu trong ví dụ này là cấu trúc kiểu BẢNG (tập hợp đặc biệt vì rằng chỉ có duy nhất một thực thể, trong khi đó kết hợp là không phân cấp) và cấu trúc kiểu CÓ-KHÔNG.
Mô hình này xác định một ma trận thay thế giữa các sản phẩm. Một sản phẩm có thể không dùng để thay thế hoặc thay thế cho nhiều sản phẩm khác. Trái lại, một sản phẩm có thể không bị thay thế hoặc bị thay thế bởi nhiều sản phẩm khác.
Hình 5.6 Mô hình dữ liệu cấu trúc kiểu PHẢNXA
I.7. Cấu trúc kiểu BÌNHĐẲNG
Cấu trúc kiểu BÌNHĐẲNG (ÉGALITÉ) đặt một kết hợp giữa hai cấu trúc kiểu PHIẾU.
Đây là một kết hợp đặc biệt mà người ta gọi là CIF qua lại (thuận nghịch) do bản số tối đa ở hai đầu đều bằng 1. Người ta cũng nói đây là trường hợp một cha có một con duy nhất.
Ví dụ : Ta thừa nhận rằng một hóa đơn chỉ có thể thanh toán một lần và một lần thanh toán chỉ căn cứ trên một hóa đơn.
Hình 5.7 Mô hình dữ liệu cấu trúc kiểu BÌNHĐẲNG
Mỗi thực thể có các đặc tính riêng khẳng định sự tồn tại của thực thể đó : khóa và các thuộc tính. Mỗi trường hợp cụ thể của mỗi một trong hai thực thể tương ứng với nhiều nhất là một
SẢNPHẨM MãSP TênSP GiáĐơnVị
SLCó SLBáoĐộng
0 − n
0 − n
Thay thế ⁄ Được thay thế bởi
HOÁĐƠN SốHĐ NgàyLậpHĐ
THANHTOÁN TToánSố NgàyTToán
0 − 1 1 − 1
Được
Một hóa đơn chỉ được thanh toán nhiều nhất một lần. Nhưng chừng nào thanh toán này chưa được thực hiện, sẽ không có trường hợp cụ thể của THANHTOÁN tương ứng với trường hợp cụ thể của HÓAĐƠN đang xét. Từ đó ta có bản số 0 (cấu trúc kiểu CÓ-KHÔNG).
Một thanh toán, một khi đã được ghi nhận, sẽ tồn HÓAĐƠN tại trong CSDL và có quan hệ đến một và chỉ một hóa đơn.
Chú ý rằng do chỉ cần làm việc với một thực thể duy nhất, việc mô hình hóa đặt ra những vấn đề sau :
SốHĐ NgàyLậpHĐ
TToánSố NgàyTToán Các thuộc tính TToánSố và NgàyTToán có giá trị 0 khi việc thanh toán cho hóa đơn
tương ứng chưa được thực hiện.
Không thể thanh toán nếu chưa biết số hóa đơn liên quan.
NgàyTToán là đích của một PTH mà TToánSố là nguồn, và cũng là đích của một PTH khác mà SốHĐ là nguồn. PTH sau cùng này có tính bắc cầu.
TToánSố → NgàyTToán
SốHĐ → NgàyTToán và ta cũng có SốHĐ → TToánSố
I.8. Cấu trúc kiểu THỪA KẾ
Việc đưa vào khái niệm thừa kế (héritage) trong các mô hình dữ liệu thực thể - kết hợp thực sự đã làm phong phú thêm về mặt ngữ nghĩa. Khái niệm cấu trúc kiểu THừAKế liên quan đến sự chuyên môn hóa và sự khái quát hoá.
Ví dụ : Trong một mô hình dữ liệu, ta quan tâm đến nhiều loại xe : loại xe du lịch (DL), loại xe chuyên dùng (CD). Thoạt tiên, ta dự kiến hai mô hình hóa :
Mô hình dùng một thực thể duy nhất : Mô hình dùng hai thực thể phân biệt :
XEHƠI XEDL XECD
(a) BiểnĐKSố MacXe CôngSuất SốChỗNgồi
TảiTrọng
(b) BiểnĐKSốDL
MacXeDL CôngSuấtDL
SốChỗNgồi
BiểnĐKSốCD MacXeCD CôngSuấtCD
TảiTrọng Cả hai mô hình trên đều không thỏa mãn. Trong mô hình dùng một thực thể duy nhất (a), dữ liệu SốChỗNgồi chỉ có nghĩa với loại xe du lịch và dữ liệu TảiTrọng chỉ có nghĩa với các xe chuyên dụnng. Còn trong mô hình dùng hai thực thể phân biệt (b), các thuộc tính chung cho cả hai loại xe (MacXe và CôngSuất) lại nằm trong cả hai thực thể.
Hình 5.8 Mô hình dữ liệu cấu trúc kiểu THừAKế XEDL
BiểnĐKSốDL SốChỗNgồi
1 − 1 1 − 1
1 − 1 0 − 1
XECD BiểnĐKSốCD
TảiTrọng +
XEHƠI BiểnĐKSố MacXe CôngSuất
Để khắc phục, ta đưa các dữ liệu chung cho cả hai loại xe vào trong một thực thể XEHƠI và các dữ liệu đặc trưng của mỗi loại xe được đặt vào các thực thể XEDL và XECD. Ta có các PTH như sau :
Mô hình (a) thể hiện sự chuyên môn hóa : các dữ liệu đặc trưng cho mỗi loại xe được đặt trong thực thể tương ứng).
Mô hình (b) thể hiện khái quát hóa : nhóm các dữ liệu chung cho cả hai loại xe vào trong cùng một thực thể đặc chủng.
Vậy thì tính thừa kế là gì trong mô hình dữ liệu này ?
Hai thực thể XEDL và XECD thừa kế các thuộc tính MacXe và CôngSuất của thực thể dặc chủng XEHƠI.
Chúng là các cấu trúc kiểu BÌNHĐẲNG và CÓ-KHÔNG, tạo thành cấu trúc kiểu THỪAKẾ. Một trường hợp cụ thể của XEDL phải tương ứng với một trường hợp cụ thể của XEHƠI (ràng buộc toàn vẹn). Tương tự như vậy đối với thực thể XECD.
Với thực thể XEHƠI, vấn đề phức tạp hơn. Một trường hợp cụ thể của XEHƠI không nhất thiết tương ứng với một trường hợp cụ thể của XEDL (cấu trúc kiểu CÓ-KHÔNG). Cũng lý luận tương tự cho thực thể XECD. Tuy nhiên, cần có một trường hợp cụ thể của XEHƠI tương ứng với một trường hợp cụ thể của XEDL, hoặc của XECD.
Thực tế, một xe nào đó hoặc là loại xe du lịch, hoặc là loại xe chuyên dụng (trong thí dụ này). Điều này thể hiện bởi dấu + (hay “hoặc có loại trừ”). Đây là một ràng buộc có loại trừ lẫn nhau giữa hai kết hợp cho phép nối kết XEHƠI với XEDL và XEHƠI với XECD.
I.9. Cấu trúc kiểu KẾTTỤ
Cấu trúc kiểu cuối cùng này chỉ ra rằng đôi khi cần phải mô hình hóa một hệ thống thông tin bằng cách thực hiện từng giai đoạn.
Ở đây đề cập đến khái niệm kết tụ (AGRÉGATION) và cũng đề cập đến khái niệm cá thể hóa để giải quyết cùng một vấn đề theo một cách khác.
Ví dụ : Xét một thư viện phục vụ sinh viên Tin học. Các tác phẩm (sách, tài liệu...) thuộc nhiều chủ đề khác nhau (ngôn ngữ lập trình, hệ điều hành, cơ sở dữ liệu, ...). Đương nhiên, một chủ đề có thể có nhiều tác phẩm.
Ta có mô hình dữ liệu kiểu BẢNG thiết lập sự tương ứng giữa các tác phẩm và các chủ đê như sau :
Hình 5.9 Mô hình dữ liệu cấu trúc kiểu BẢNG
Để quản lý thư viện dễ dàng và hiệu quả, sinh viên đã đưa ra sáng kiến thiết lập một danh mục các từ khóa có ý nghĩa nhất về tình trạng kiến thức Tin học. Họ muốn rằng có thể tìm được những từ khóa ở trong mỗi phần của tác phẩm đã được đặt mã tham chiếu, nghĩa là cho mỗi chủ đề trong mỗi tác phẩm.
Đề cập đến ⁄ Có trong TÁCPHẨM
ĐKýSố TênTácPhẩm ...
1 − n 1 − n
CHỦĐỀ.
ChủĐềSố TênChủĐề
...