CHƯƠNG 1 TỔNG QUAN VỀ LÝ THUYẾT CƠ SỞ DỮ LIỆU QUAN HỆ 1. Cơ sở dữ liệu 1. Các khái niệm chung Dữ liệu bao gồm số, kí tự, văn bản, hình ảnh, đồ họa, âm thanh, đoạn phim,. có một giá trị nào đó đối với người sử dụng chúng và được lưu trữ, xử lý trong máy tính [5].
Cơ sở dữ liệu được xác định như một bộ sưu tập các dữ liệu có liên quan logic với nhau; nó được tổ chức sắp xếp theo một cách nào đó và được các hệ ứng dụng của một đơn vị/cơ quan cụ thể nào đó sử dụng. Mô hình dữ liệu và mô hình dữ liệu quan hệ 1. Mô hình dữ liệu Mô hình dữ liệu là cách biểu diễu các cấu trúc dữ liệu cho một cơ sở dữ liệu dưới dạng các khái niệm. Các cấu trúc dữ liệu bao gồm các đối tượng dữ liệu, mối liên hệ giữa các dữ liệu, ngữ nghĩa của dữ liệu và các ràng buộc trên đối tượng dữ liệu đó [5].
Có 3 loại mô hình cơ sở dữ liệu: 1. Mô hình cơ sở dữ liệu mức quan niệm - Là mô hình mô tả dữ liệu của thế giới thực gắn với hoạt động nghiệp vụ của tổ chức sử dụng nó. - Mô tả các cấu trúc và mối liên hệ giữa các đơn vị thông tin cơ bản. - Là phương tiện để giao tiếp với người sử dụng nhằm xác định đúng đắn và đầy đủ các yêu cầu thông tin của hệ thống.
- Hoàn toàn độc lập với mọi hệ quản trị dữ liệu và cách thức sử dụng nó. - Cung cấp các khái niệm gắn liền với cách cảm nhận dữ liệu của người sử dụng. Nó tập trung vào bản chất logic của biểu diễn dữ liệu, quan tâm đến cái được biểu diễn, chứ không quan tâm đến cách biểu diễn. 6 - Mô hình khái niệm cơ bản như mô hình E_R.
Mô hình E_R dùng để mô tả cấu trúc logic tổng thể (lược đồ) của một cơ sở dữ liệu bằng hình ảnh (đặc tả). Người ta quan niệm thế giới thực bao gồm tập các E và R. Trong đó, E là “sự vật”/ “đối tượng” tức là thực thể trong thế giới thực và phải phân biệt được, còn R là mối quan hệ (relationship) giữa một nhóm thực thể [6]. Mô hình cơ sở dữ liệu mức logic: - Cung cấp khái niệm cho người sử dụng có thể được và không xa so với cách tổ chức dữ liệu trong máy tính.
Chúng che dấu một số chi tiết về việc lưu trữ dữ liệu nhưng có thể cài đặt trực tiếp trên hệ thống máy tính. Mô hình dữ liệu logic cho một hệ quản trị cơ sở dữ liệu: - Mô tả các dữ liệu bằng cách sử dụng các ký hiệu tương ứng với mô hình dữ liệu mà 1 hệ quản trị cơ sở dữ liệu xây dựng trên nó. - Có 4 loại mô hình dữ liệu logic: mô hình dữ liệu phân cấp, mạng, quan hệ, hướng đối tượng. - Hiện nay, được tổ chức theo mô hình dữ liệu quan hệ là chủ yếu.
Mô hình cơ sở dữ liệu mức vật lý: - Cung cấp các khái niệm mô tả chi tiết về việc các dữ liệu được lưu trữ trong máy như thế nào. Mô hình dữ liệu quan hệ Mô hình dữ liệu quan hệ được Cold đề xuất năm 1970. Nó đã tạo ra một cuộc cách mạng mới trong lĩnh vực cơ sở dữ liệu và nhanh chóng thay thế các mô hình dữ liệu trước đó [5]. Mô hình dữ liệu quan hệ tương đối đơn giản và dễ hiểu.
Mô hình dữ liệu quan hệ là mô hình dữ liệu mà cốt lõi của nó là cơ sở dữ liệu quan hệ. Một cơ sở dữ liệu quan hệ là một tập của một hoặc nhiều quan hệ, trong đó mỗi một quan hệ là một bảng. Mô hình quan hệ sử dụng một tập các bảng để biểu diễn cả dữ liệu và các mối liên hệ giữa những dữ liệu này. Bảng có n cột và mỗi cột có một tên duy nhất.
Những cơ sở dữ liệu quan hệ thông dụng nhất đều có thể sử dụng ngôn ngữ SQL (Structured Query Language) 7 1. Phụ thuộc hàm và thiết kế logic cơ sở dữ liệu quan hệ 1. Khái niệm về phụ thuộc hàm Khái niệm về phụ thuộc hàm trong một quan hệ là rất quan trọng trong việc thiết kế mô hình dữ liệu.F Cold đã mô tả phụ thuộc hàm trong mô hình dữ liệu quan hệ, nhằm giải quyết việc phân rã không mất thông tin [1,5]., an} là tập thuộc tính, r = {h1, h2 ,., hm} là một quan hệ trên R, và A,B R (A, B là tập cột hay tập thuộc tính). Khi đó ta nói A xác định hàm cho B hay B phụ thuộc hàm vào A trong r ( ký pháp A ⎯⎯ → B) nếu: ( h , h f r i j r) (( a A) ( hi (a) = hj (b)) ( b B) ( hi(b) = hj(b))) nghĩa là đối số trùng nhau thì hàm có cùng giá trị.
Lúc đó F f r r được gọi là họ đầy đủ các phụ thuộc hàm của r. Nhận xét : Ta có thể thấy rằng B mà phụ thuộc hàm vào A, nếu hai dòng bất kì mà các giá trị của tập thuộc tính A mà bằng nhau từng cặp một, thì kéo theo các giá trị trên tập thuộc tính B cũng phải bằng nhau từng cặp một. Ví dụ: Xét quan hệ [4]: Bảng 1. Quan hệ THISINH SBD Hoten Diachi Tinh Khuvuc PD711001 Nguyễn Thái Bình 12 Bản Nhàn Lạng Sơn 0 PD711002 Trần Nam Ninh 3 Kim mã Hà Nội 3 PD711003 Lê Thanh Hoa 53 Hai Bà Trưng Hà Nội 3 PD711004 Vũ Thúy Hồng 89 Đồng Đăng Lạng Sơn 0 PD711005 Phạm Như Thúy 40 Trần Hưng Đạo Hải Dương 2 Trong quan hệ THISINH, dựa vào định nghĩa phụ thuộc hàm của quan hệ ta có: {tinh} ->{khuvuc}; {sbd}-> {hoten, diachi, tinh, khuvuc} Ý nghĩa: Khái niệm phụ thuộc hàm miêu tả một loại ràng buộc (phụ thuộc dữ liệu) xảy ra tự nhiên nhất giữa các tập thuộc tính.
Các thuật toán xác định bao đóng và khóa trong sơ đồ quan hệ s=<R,F> 1. Một số thuật toán liên quan đến bao đóng Một vấn đề thường xuyên xảy ra đối với một sơ đồ quan hệ cho trước (s =<R, F>), và một phụ thuộc hàm A-> B, chúng ta muốn biết A-> B có là phần tử của F+ hay không. Để trả lời câu hỏi này chúng ta cần tính bao đóng F+ của tập các phụ thuộc hàm F. Tuy nhiên tính F+ trong trường hợp tổng quát là rất khác nhau và tốn kém thời gian vì các tập phụ thuộc hàm F+ là rất lớn cho dù F có thể là nhỏ.A ->Bn}, khi đó F+ bao gồm cả những phụ thuộc hàm A->Y với Y {B1 B2 .
Bn}, như vậy ta sẽ có 2n tập con Y. Trong khi đó việc tính bao đóng của tập thuộc tính A lại không khó. Theo kết quả đã trình bay ở trên thì việc kiểm tra A->B F+ sẽ được thế bởi tính A+ [1,5,6]. Thuật toán Tính bao đóng của một tập các thuộc tính đối với tập các phụ thuộc hàm trên sơ đồ quan hệ Vào: s = <R,F> là một sơ đồ quan hệ Trong đó: R= (a1, a2,.an) là tập hữu hạn các thuộc tính.
F là tập các phụ thuộc hàm và A R Ra: A+ là bao đóng của A đối với F. A->B F+ nếu và chỉ nếu B A+. Phương pháp : Lần lượt tính các tập thuộc tính A0, A1 như sau: 1.Ai = Ai-1 {a} nếu (C->D) F, {a} D và C Ai-1 3. Ai và R hữu hạn nên tồn tại i sao cho: Ai = Ai+1.
Khi ấy thuật toán dừng và Ai chính là A+ Ví dụ: 9 Xét sơ đồ quan hệ s=<R,F> Trong đó : {c} → {t} {h,r} → {c} {h,t} → {r} {c,s} → {g} F= {h,s} → {r} R = {c, t, h, r, s, g} Tính {h, r}+ ? A0 = {h, r} A1 = {h, r, c} do {h, r} -> {c} F A2 = {h, r, c, t} do {c}-> {t} F A3 = {h, r, c, t} = A2 Vậy {h, r}+ = {h, r, c, t} 2. Một số thuật toán liên quan đến khóa Khi giải quyết các bài toán thông tin quản lý, người ta thường sử dụng các hệ quản trị cơ sở dữ liệu mà trong đó chứa cơ sở dữ liệu quan hệ. Các phép xử lý đối với bài bài toán này thường là tìm kiếm bản ghi sau đó thêm bản ghi mới, thay đổi nội dung bản ghi hoặc xóa bản ghi. Trong các thao tác trên, việc tìm kiếm bản ghi là rất quan trọng.
Muốn tìm được bản ghi trong file dữ liệu thì chúng ta phải xây dựng khóa của file dữ liệu đó. Việc tìm khóa ở đây chính là tìm khóa tối thiểu. Thuật toán tìm khóa tối thiểu cho một sơ đồ quan hệ [3]: Input: Sơ đồ quan hệ s = <R, F> Trong đó : F là tập các phụ thuộc hàm R = {a1,.an} là tập các thuộc tính Output: K là tối thiểu của s Phương pháp: Tìm liên tiếp các tập thuộc tính K0, K1,.Kn như sau: K0 = R = {a1,. an} 10 K i−1 Ki-1 nếu Ki-1 – {ai} R F+ K − {a i } Ki = i−1 Ki-1 – {ai} nếu ngược lại K = Kn là khóa tối thiểu Ta có thể dùng công thức tương đương: Nếu {Ki-1 - ai}+ = R Nếu ngược lại.
Nhận xét: - Thay đổi thứ tự các thuộc tính của R bằng thuật toán trên chúng ta có thể tìm được một khóa tối thiểu khác. - Nếu như đã biết A là một khóa nào đó thì có thể đặt K0 = A, ta vẫn tìm ra được khóa tối thiểu và thời giàn tìm nhanh hơn. Ví dụ : Giả sử s = <F, R> là một lược đồ quan hệ trong đó: R = {a, b, c, d} F = {{a,b} {d}, {c} } Tìm khóa tối thiểu của sơ đồ quan hệ. Áp dụng thuật toán trên ta có: + K0 = R = {a, b, c, d} + Tính K1 Xét K1 = K0 – {a} = {b, c, d} {b, c, d}+ = {b, c, d} R Vậy K1 = {a, b, c, d}.