intTypePromotion=1
zunia.vn Tuyển sinh 2024 dành cho Gen-Z zunia.vn zunia.vn
ADSENSE

Nhập môn Cơ sở dữ liệu - Phạm Thị Thanh

Chia sẻ: Pham Thi Thanh | Ngày: | Loại File: DOC | Số trang:100

147
lượt xem
25
download
 
  Download Vui lòng tải xuống để xem tài liệu đầy đủ

Với kết cấu nội dung gồm 5 chương, tài liệu nhập môn "Cơ sở dữ liệu" giới thiệu đến các bạn các khái niệm cơ bản về cơ sở dữ liệu, ngôn ngữ thao tác dữ liệu, thiết kế một cơ sở dữ liệu, mô hình thực thể liên kết. Đây là tài liệu tham khảo hữu ích cho các bạn đang học và nghiên cứu về Công nghệ thông tin.

Chủ đề:
Lưu

Nội dung Text: Nhập môn Cơ sở dữ liệu - Phạm Thị Thanh

  1. Nhập môn cơ sở dữ liệu – Phạm Thị Thanh, Khoa Ngoại ngữ & Tin học LỜI NÓI ĐẦU Ngày này cơ sở dữ liệu đã có nhiều ứng dụng trong mọi hoạt động của  xã hội. Muốn thiết kế, sử dụng cơ sở dữ liệu chúng ta phải nắm được các kỹ  thuật cơ  bản của cơ  sở  dữ  liệu. Tập bài giảng này nhằm trình bày các kỹ  thuật cơ bản của cơ sở dữ liệu truyền thống, đó là mô hình thực thể liên kết,   mô hình cơ  sở  dữ  liệu quan hệ. Tập bài giảng cũng trình bày cách thiết kế  một cơ sở dữ liệu quan hệ, cách sử  dụng các phép toán đại số quan hệ, ngôn  ngữ  tân từ, ngôn ngữ  hỏi có cấu trúc để  tạo, cập nhật và truy vấn cơ  sở  dữ  liệu. Khái niệm phụ  thuộc hàm và  ứng dụng của nó trong thiết kế  và chuẩn   hóa cơ sở dữ liệu quan hệ. Tập bài giảng là tài liệu chính thức của học phần  nhập môn cơ sở dữ liệu cho sinh viên chuyên ngành sư phạm Toán – Tin. Tập  bài giảng cũng là tài liệu tham khảo hữu ích cho giảng viên khi giảng dạy các   học phần liên quan đến cơ sở dữ liệu Tập bài giảng gồm 5 chương, cuối mỗi chương có câu hỏi và bài tập   giúp sinh viên rèn luyện các kiến thức học được trong chương đó. Chương 4   là chương sinh viên tự nghiên cứu để hiểu biết thêm về mô hình thực thể liên  kết.  Chúng tôi xin tiếp nhận và chân thành cảm  ơn sự  giúp đỡ, đóng góp ý   kiến của các đồng nghiệp để tập bài giảng ngày càng hoàn thiện hơn. Nhóm tác giả 1
  2. Nhập môn cơ sở dữ liệu – Phạm Thị Thanh, Khoa Ngoại ngữ & Tin học MỤC LỤC  1. Các khái niệm về hệ cơ sở dữ liệu                                                                  ..............................................................      4  1.1. Khái niệm cơ sở dữ liệu và hệ cơ sở dữ liệu                                          ......................................      4  1.2. Kiến trúc CSDL                                                                                          ......................................................................................      4  1.3. Lược đồ và thể hiện của CSDL                                                                ............................................................      6  1.4. Tính độc lập dữ liệu                                                                                  ..............................................................................      7  2. Tổ chức dữ liệu mức vật lý                                                                              .........................................................................      7  2.1. Mô hình tổ chức bộ nhớ ngoài                                                                   ...............................................................      7  2.2. Tệp băm (Hashed  file)                                                                               ...........................................................................      8  2.3. Tệp chỉ số (indexed file)                                                                          ......................................................................       10  2.4. Cây cân bằng (Balanced tree – B cây)                                                      ..................................................       12  3. Ba mô hình dữ liệu cơ bản                                                                             .........................................................................       14  3.1. Mô hình hóa trong tin học                                                                         .....................................................................       14  3.3. Các mô hình dữ liệu cơ bản                                                                     .................................................................       14  Kết chương                                                                                                              ..........................................................................................................       17  Câu hỏi và bài tập                                                                                                    ................................................................................................       17  CHƯƠNG II: NGÔN NGỮ THAO TÁC DỮ LIỆU                                             ........................................       19  1. Cơ sở dữ liệu quan hệ                                                                                    ................................................................................       19  1.1. Khái niệm cơ bản                                                                                     ................................................................................       19  1.2. Các thao tác cập nhật dữ liệu trên quan hệ                                             .........................................      20  1.3. Đại số quan hệ                                                                                         .....................................................................................       21  1.4. Ngôn ngữ tân từ:                                                                                       ...................................................................................       32  2. Ngôn ngữ hỏi có cấu trúc – SQL (Structured Query Language)                    ................      33  2.1. Ngôn ngữ định nghĩa dữ liệu                                                                   ...............................................................       34  2.2. Ngôn ngữ thao tác dữ liệu                                                                        ....................................................................       38  Kết chương                                                                                                              ..........................................................................................................       44  Câu hỏi và bài tập                                                                                                    ................................................................................................       44  CHƯƠNG III: THIẾT KẾ MỘT CƠ SỞ DỮ LIỆU                                            ........................................       50  1. Mục đích thiết kế CSDL                                                                                 .............................................................................       50  2. Phụ thuộc hàm (Function Defendency­FD)                                                    ................................................       52  2.5. Bao đóng của 1 tập phụ thuộc hàm                                                         .....................................................       53  2.6. Bao đóng của 1 tập thuộc tính                                                                 ............................................................       54  2.7. Định nghĩa khoá và siêu khoá theo ngôn ngữ phụ thuộc hàm                 .............      56  2.8. Tập phụ thuộc hàm tối thiểu                                                                   ...............................................................       59  3. Phép tách các lược đồ quan hệ                                                                       ...................................................................       63  3.1. Khái niệm phép tách                                                                                 .............................................................................       63  3.2. Phép tách kết nối không tổn thất                                                             ........................................................       63  4. Chuẩn hoá lược đồ quan hệ                                                                           .......................................................................       67  4.1. Các dạng chuẩn                                                                                        ....................................................................................       67  4.2. Phép tách kết nối không tổn thất thành BCNF                                        ....................................       69  4.3. Phép tách bảo toàn phụ thuộc hàm thành 3NF                                        ....................................      72 2
  3. Nhập môn cơ sở dữ liệu – Phạm Thị Thanh, Khoa Ngoại ngữ & Tin học  Kết chương                                                                                                              ..........................................................................................................       73  Câu hỏi và bài tập                                                                                                    ................................................................................................       73  1. Mô hình dữ liệu khái niệm bậc cao và quá trình thiết kế CSDL                  ..............       78  2. Các thành phần cơ bản của mô hình thực thể liên kết:                                 .............................       79  2.1. Thực thể và thuộc tính                                                                             .........................................................................       79  2.2. Kiểu thực thể, tập thực thể, khóa và tập giá trị                                     .................................      81  2.3. Kiểu liên kết, tập liên kết và các thể hiện                                             .........................................       84  2.4. Cấp liên kết, tên vai trò và kiểu liên kết đệ quy                                     .................................       85  2.5 Các ràng buộc trên các kiểu  liên kết                                                        ..................................................      86  2.6. Thuộc tính của các kiểu liên kết                                                             .........................................................       87  2.7. Các kiểu thực thể yếu                                                                              ........................................................................       88  3. Ví dụ về thiết kế mô hình ER                                                                        ....................................................................       88  Xác định các kiểu thực thể, các thuộc tính và các kiểu liên kết                   ...............      89  CHƯƠNG V: HỆ QUẢN TRỊ CƠ SỞ DỮ LIỆU                                                 .............................................      94  1.  Định nghĩa một hệ quản trị CSDL:                                                                ...........................................................       94  2. Các chức năng của một hệ quản trị cơ sở dữ liệu                                        ....................................      94  3. Các đặc trưng của giải pháp cơ sở dữ liệu                                                   ...............................................       97  4. Ví dụ về một cơ sở dữ liệu                                                                            ........................................................................       99 3
  4. Nhập môn cơ sở dữ liệu – Phạm Thị Thanh, Khoa Ngoại ngữ & Tin học CHƯƠNG I: CÁC KHÁI NIỆM CƠ  BẢN VỀ CSDL 1. Các khái niệm về hệ cơ sở dữ liệu 1.1. Khái niệm cơ sở dữ liệu và hệ cơ sở dữ liệu ­ Một CSDL (Database) là một tập hợp các dữ liệu có liên quan với nhau  chứa thông tin về một tổ chức nào đó (như 1 trường ĐH, 1 công ty, ngân   hàng,..) được lưu trữ trên các thiết bị nhớ thứ cấp (như bằng từ, đĩa từ..)  để  đáp  ứng nhu cầu khai thác thông tin của nhiều người sử  dụng với   nhiều mục đích khác nhau. ­ Hệ   quản   trị   CSDL   (Database   Management   System­   DBMS)   là   phần  mềm   cho   phép   người   dùng   giao   tiếp   với   CSDL,   cung   cấp   một   môi  trường thuận lợi và hiệu quả  để  tìm kiếm và lưu trữ  thông tin của   CSDL ­ Hệ  csdl: (Database System): Gồm phần cứng, CSDL, Hệ quản trị csdl,   người quản trị. Mục đích chính của hệ  CSDL là che dấu đi những chi   tiết phức tạp về cách thức dữ liệu được lưu trữ và bảo trì ­ Ví dụ  về  sử  dụng CSDL: Thông qua giao diện Web đăng ký một khoá  học, tìm hiểu chi tiết một mặt hàng, tra điểm thi tuyển sinh… 1.2. Kiến trúc CSDL Cơ sở dữ liệu có kiến trúc 3 mức: ­ Mức trong (mức vật lý): mô tả  dữ  liệu thực sự  được lưu trữ  như  thế  nào trong CSDL. Đây là mức thể hiện các cài đặt có tính chất vật lý của   CSDL để đạt hiệu quả tối ưu trong thao tác tìm kiếm và lưu trữ, để tận  dụng được các vùng nhớ  còn trống. Mức vật lý cũng phản ánh các cấu  trúc dữ  liệu, các tổ  chức tệp được dùng cho việc lưu trữ  dữ  liệu trên   các thiết bị nhớ thứ cấp. ­ Mức khái niệm (mức logic): mô tả  những dữ  liệu nào được lưu trữ  trong CSDL và có mối quan hệ  nào giữa chúng. Nói một cách cụ  thể  hơn, mức logic biểu diễn các thực thể, các thuộc tính và các mối quan   4
  5. Nhập môn cơ sở dữ liệu – Phạm Thị Thanh, Khoa Ngoại ngữ & Tin học hệ giữa các thực thể đó, mức logic cũng cho thấy các ràng buộc trên dữ  liệu, các thông tin về ngữ nghĩa của dữ liệu, các thông tin về an ninh và   toàn vẹn dữ liệu. Tuy nhiên mức này chỉ  quan tâm đến cái gì được lưu  trữ trong CSDL chứ không quan tâm đến cách thức để lưu trữ. ­ Mức ngoài (mức khung nhìn): Mô tả  chỉ  1 phần của CSDL, phần thích  hợp   với   một  người  sử   dụng  nhất   định.  Mỗi  người  sử   dụng  có   thể  không quan tâm đến toàn bộ  thông tin của hệ  CSDl mà chỉ  cần một   phần thông tin nào đó. Khung nhìn dành cho người sử dụng đó chỉ gồm  những thực thể  và những thuộc tính, những mối quan hệ  giữa những   thực thể  mà họ  quan tâm. Các khung nhìn khác nhau có thể  cùng trình  bày về một dữ liệu nhưng khuôn dạng khác nhau, ví dụ ngày tháng năm  sinh có thể   ở  khung nhìn này là kiểu dd/mm/yyyy, khung nhìn khác là  mm/dd/yy, một số  khung nhìn có thể  chứa các dữ  liệu được suy dẫn  hoặc tính toán chứ  không chứa thật sự  trong CSDL. Ví dụ  như  tính  điểm trung bình cuối kỳ của sinh viên  hoặc tính thành tiền của một đơn  hàng không cần lưu trong CSDL. Khung nhìn 1 Khung nhìn 2 Khung nhìn n Mức ngoài Lược đồ khái niệm Mức khái niệm Mức trong Lược đồ vật lý Hình 1.1 Kiến trúc CSDL Mục đích của kiến trúc 3 mức là sự cách ly quan niệm về CSDL của nhiều   người sử  dụng với chi tiết về  biểu diễn vật lý của nó. Điều đó dẫn đến  thuận lợi sau: ­ Đối với 1 CSDL, mỗi người dùng có một khung nhìn riêng. Họ  có thể  thay đổi khung nhìn của mình mà không làm ảnh hưởng đến khung nhìn  của người khác dùng chung CSDL này. 5
  6. Nhập môn cơ sở dữ liệu – Phạm Thị Thanh, Khoa Ngoại ngữ & Tin học ­ Những tương tác của người dùng CSDL không phụ  thuộc vào những  vấn đề chi tiết trong lưu trữ dữ liệu. ­ Người  quản trị  CSDL (Database Administrator­DBA) có thể  thay đổi  cấu trúc lưu trữ  CSDL mà không làm  ảnh hưởng đến khung nhìn của  người sử dụng. ­ Những thay đổi về khía cạnh vật lý trong lưu trữ, chẳng hạn thay đổi thiết bị  nhớ khác cũng không làm ảnh hưởng đến cấu trúc bên trong của CSDL. ­ Người quản trị  CSDL có thể  thay đổi cấu trúc tổng thể  hay cấu trúc  khái niệm của CSDL mà không ảnh hưởng đến tất cả người dùng. 1.3. Lược đồ và thể hiện của CSDL  Toàn   bộ   mô   tả   CSDL   được   gọi   là   lược   đồ   CSDL   (Database  schema). Tương  ứng với 3 mức kiến trúc trên có 3 loại lược đồ  dữ  liệu: Lược đồ ngoài, lược đồ khái niệm và lược đồ trong  Phân biệt bản thân CSDL và lược đồ CSDL. Lược đồ xác định trong   quá trình thiết kế và người ta không muốn nó thay đổi thường xuyên. Trong  khi đó bản thân CSDL lại thay đổi thường xuyên theo thời gian  Toàn bộ  dữ  liệu tại một thời điểm xác định gọi là thể  hiện của   CSDL (Database instance). Như vậy nhiều thể hiện của CSDL có thể  cùng tương ứng với một lược đồ CSDL  Ví dụ:  Khung nhìn 1 Khung nhìn 2 MaSV  HoTen     Ngaysinh   quequan MaSV   hocky    MaMon    diem Mức  MaSV  HoTen     Ngaysinh    quequan        hocky    MaMon    diem logic Hình 1.2. Ví dụ lược đồ và thể hiện của CSDL Mức vật lý    Struc SINHVIEN{ Int MaSV; Char hoten[25] 6
  7. Nhập môn cơ sở dữ liệu – Phạm Thị Thanh, Khoa Ngoại ngữ & Tin học Struc date ngaysinh Int hocky Int mamon Float diem Struc SINHVIEN next /* trỏ đến bản ghi tiếp của tệp nhân viên*/ }; 1.4. Tính độc lập dữ liệu  Là tính bất biến giữa các hệ ứng dụng đối với các thay đổi trong  cấu trúc lưu trữ và chiến lược truy cập.  Có 2 mức độc lập dữ liệu: Độc lập vật lý và độc lập logic - Độc lập dữ  liệu vật lý: Việc thay đổi trong tổ  chức  CSDL mức vật lý có thể làm ảnh hưởng đến hiệu quả của hệ ứng   dụng nhưng không đòi hỏi viết lại chương trình. Ví dụ  như  sử  dụng các tệp khác trước, dùng thiết bị nhớ khác, thay đổi chỉ mục  hay thay đổi thuật toán băm. - Độc lập dữ liệu logic: Khi sử dụng CSDL có thể thay  đổi   lược   đồ  khái  niệm  mà  không  làm  thay   đổi  các   khung  nhìn  (lược đồ ngoài) cũng không cần thay đổi chương trình. Ví dụ thêm  bớt các thực thể, các thuộc tính hay mối quan hệ  giữa chúng. Tất  nhiên những người dùng có chạm đến các thông tin đã thay đổi này  sẽ được thông báo về sự thay đổi, nhưng điều quan trọng là những  người dùng khác không ảnh hưởng gì. 2. Tổ chức dữ liệu mức vật lý  2.1. Mô hình tổ chức bộ nhớ ngoài - Bộ nhớ ngoài: Băng từ, đĩa từ.. - Cách lưu trữ trên đĩa từ: Đĩa từ được chia thành các khối  vật lý (physical block) có kích cỡ  như  nhau. Mỗi khối chiếm khoảng  512 ­> 4096 byte và được đánh địa chỉ  khối. Một tệp (file) chiếm 1   hoặc nhiều khối. 1 khối chứa 1 hay nhiều bản ghi (record), 1 b ản ghi   chứa nhiều trường (field). Thông thường một bản ghi tương  ứng với   7
  8. Nhập môn cơ sở dữ liệu – Phạm Thị Thanh, Khoa Ngoại ngữ & Tin học một thực thể, một trường tương  ứng với một thuộc tính. Thao tác với  tệp dữ liệu thông qua địa chỉ khối. - Địa chỉ của các bản ghi là địa chỉ  của byte đầu tiên của   bản ghi đó hoặc địa chỉ khối chứa bản ghi đó. - Con trỏ (Pointer) là chỉ dẫn tới địa chỉ của bản ghi hoặc   các khối thường được lưu ở 1 tệp hay vị trí nào đó để khi cần qua đó  truy cập tới dữ liệu cần thiết 2.2. Tệp băm (Hashed  file) - Hàm băm: Nếu mỗi bản ghi có 1 khoá là x thì hàm băm H(x)  nhận 1 giá trị  nguyên dương nào đó. Vì thế  tệp băm còn gọi là tệp   ngẫu nhiên. Hàm băm được chọn sao cho các bản ghi được phân bố  đều trong tệp. Có một kỹ thuật được gọi là gấp lại (Folding), nó áp  dụng một hàm số học, chẳng hạn phép cộng vào các phần khác nhau   của khóa. Kết quả có được từ phép cộng đó được lấy làm địa chỉ của  khối chứa bản ghi nói trên. Có một kỹ  thuật thông dụng hơn được   gọi là chia dư (division – remainder). Kỹ thuật chia dư sử dụng hàm  MOD, giá trị của khóa được chia cho một số nguyên định trước và số  dư  trong phép chia đó được sử  dụng làm địa chỉ  của khối chứa bản  ghi. Khi địa chỉ  được sinh ra cho 2 hay nhiều bản ghi , các bản ghi   được gọi là các đồng nghĩa. Khi một bản ghi mà khối cho bản ghi đó  đã đầy thì ta nói rằng xuất hiện các xung đột (collision). - Tệp băm phân chia tập hợp các bản ghi của tệp dữ  liệu  thành các cụm (Buckets). Mỗi cụm gồm 1 hoặc nhiều khối (block).   Mỗi khối chứa 1 số lượng cố định các bản ghi. - Mỗi cụm ứng với 1 địa chỉ băm. Địa chỉ băm được đánh số  từ  0 đến k­1.  Ở  đầu mỗi khối đều chứa con trỏ  tới khối tiếp theo   trong cụm. Khối cuối cùng trong cụm chứa con trỏ rỗng. - Có 1 bảng chỉ  dẫn cụm (buckets directory) chứa k con trỏ.   Mỗi con trỏ ứng với 1 cụm, đó là địa chỉ của khối đầu tiên trong cụm - Nếu bảng chỉ  dẫn có kích thước nhỏ  có thể  được lưu trữ  trong bộ nhớ trong, ngược lại được để ở bộ nhớ ngoài 8
  9. Nhập môn cơ sở dữ liệu – Phạm Thị Thanh, Khoa Ngoại ngữ & Tin học 0 * Null  1 * Null k­1 * Null Hình 1.3. Tổ chức tệp băm Tìm kiếm bản ghi Giả sử cần tìm bản ghi có khoá x. Trước hết tính hàm băm H(x), giả sử  H(x) =i, i sẽ là địa chỉ  băm của cụm i. Trong bảng chỉ dẫn cụm cho biết con   trỏ  đến khối đầu tiên (nếu có). Tìm trong khối này xem liệu có bản ghi có  khoá x hay không. Theo con trỏ  ở đầu khối, tìm tới các khối tiếp theo cho tới   khi tìm được bản ghi hoặc tới cuối cùng của cụm i mà không có bản ghi đó. Thêm 1 bản ghi Thêm bản ghi có khoá x vào tệp. Thực hiện thủ tục như tìm kiếm. Nếu  tìm thấy bản ghi có khoá x thì bản ghi mới là sai (vì khoá không được trùng  nhau). Nếu không có bản ghi trùng, bản ghi có khoá x được thêm vào khối đầu  tiên trong cụm còn chỗ  trống. Nếu không còn chỗ  trống nào trong mọi khối   của cụm, thì phải tạo thêm khối mới, con trỏ null của khối cuối cùng được trỏ  sang khối mới này. Lúc này bản ghi mới là bản ghi đầu tiên của khối và khối  này trở thành khối cuối cùng. Xoá 1 bản ghi  Để xóa bản ghi có khoá x, sử dụng thủ tục tìm bản ghi có khoá x. Nếu   bản ghi thuộc một khối nào đó có nhiều bản ghi thì bản ghi đó được xoá, nếu  bản ghi đó là duy nhất trong khối, thì sẽ xoá đồng thời khối đó khỏi cụm. Sửa 1 bản ghi  Cần sửa một số trường của bản ghi có khoá x. Nếu có sửa trường tham   gia trong khoá, việc sửa chữa sẽ là loại bỏ  bản ghi này và thêm vào một bản  ghi mới cho tệp. Nếu trường cần sửa không thuộc khoá thì tiến hành sửa bình   thường, nếu bản ghi không tồn tại xem như có lỗi. 9
  10. Nhập môn cơ sở dữ liệu – Phạm Thị Thanh, Khoa Ngoại ngữ & Tin học 2.3. Tệp chỉ số (indexed file) Quy   ước:   Tệp  dữ  liệu   được   sắp  xếp  theo  khoá,   khoá  bao  gồm  các  trường có thứ  tự  và chiều dài cố  định. Tệp chỉ  số  được tạo theo khoá, bao  gồm các cặp (k, d) trong đó k là giá trị của khoá, d là địa chỉ của khối. Các cặp   này được sắp xếp theo giá trị của khoá (k1,d1) (k1,d1)   * k1 k2 (k2,d2) * (k2,d2)   * * * kn (kn,dn) (kn,dn)   Null Bảng chỉ số khối Tệp chỉ số Tệp dữ liệu chính Hình 1.4. Tệp chỉ số Tìm kiếm bản ghi Giả sử tìm bản ghi có khoá x, có nhiều cách để duyệt tệp chỉ số Tìm tuần tự Duyệt trong tệp chỉ số các cặp (k,d) trong bảng chỉ số khối, so sánh giá trị  x  với k, gặp cặp đầu tiên (k’,d’) có  k’>x thì dừng. Như  vậy giá trị  x có thể   ở  trong khối ngang với khối trước đó. Trong khối này ta tìm tuần tự cho tới khi  gặp k=x thì d tương  ứng là bản ghi cần tìm. Nếu không có giá trị k nào trong   khối đang xét bằng x, xem như x không tồn tại. Tìm kiếm nhị phân 10
  11. Nhập môn cơ sở dữ liệu – Phạm Thị Thanh, Khoa Ngoại ngữ & Tin học Phương   pháp   tìm   kiếm   tuần   tự   thường   là   chậm,   thường   có   thể   sử   dụng  phương pháp khác nhau như phương pháp tìm kiếm nhị phân vì tệp chỉ số bao  giờ cũng được sắp xếp. Giả sử tệp chỉ số được lưu trên n khối (b1....b1). Để  tìm một bản ghi có khoá x, trước hết chọn khối b[n/2]. So sánh giá trị k thuộc   khối b[n/2] và x, nếu k>x thì bộ  cần tìm nằm trong các khối từ  b 1…b[n/2],  ngược lại thì nằm trong các khối b[n/2+1] … bn. Quá trình lặp lại cho đến khi  chỉ  còn một khối chứa bản ghi có khoá x. Trong khối này tiếp tục tuần tự  trong các cặp (k,d) như phương pháp tìm tuần tự. Thêm bản ghi Thực hiện thao tác tìm bản ghi để xác định khối sẽ chứa bản ghi mới Nếu trong khối còn chỗ  trống thì thêm bản ghi này vào khối theo thứ  tự  sắp  xếp của khoá. Việc đặt đúng vị  trí này đòi hỏi phải chuyển chỗ  các bản ghi  đứng sau bản ghi có khoá  x. Nếu bản ghi có khoá x là bản ghi đầu tiên của  khối thì phải sửa khoá k = x trong bảng chỉ dẫn khối. Nếu khối bị hết chỗ thì  bản ghi cuối cùng của khối này phải đẩy xuống khối tiếp theo để  dành chỗ  của nó cho bản ghi có khoá x. Khi đó phải sửa lại giá trị (k,d). Nếu bản ghi có khoá x là bản ghi cuối cùng, tức là x lớn hơn mọi khoá k trong  tệp chỉ dẫn và mọi khối đều hết chỗ, khi đó thiết lập một khối mới, bản ghi   này là bản ghi đầu tiên của khối mới thành lập. Xoá bản ghi Quá trình giống như thêm 1 bản ghi. Lưu ý nếu bản ghi có khoá x là bản ghi   duy nhất của khối thì, xoá cả khối đó. Sửa bản ghi Dùng thủ tục tìm bản ghi để tìm bản ghi cần sửa + Nếu các trường cần sửa không phải là khoá thì việc sửa tiến hành bình  thường, giá trị của bản ghi sau khi sửa được ghi lại vị trí cũ. + Nếu giá trị của trường cần sửa tham gia trong khoá. Quá trình sửa sẽ là thêm   vào và xoá 1 bản ghi. Chú ý: Tệp chỉ số có thể được cấu trúc một cách đơn giản hơn rất nhiều. Tệp   này chỉ gồm 2 trường, khoá k và con trỏ d. Mỗi bản ghi của tệp chỉ số tương   ứng với một bản ghi của tệp chính. Khoá k là giá trị  khoá của bản ghi chính,  11
  12. Nhập môn cơ sở dữ liệu – Phạm Thị Thanh, Khoa Ngoại ngữ & Tin học con trỏ d là địa chỉ của bản ghi trong tệp chính. Trong trường hợp này, tệp dữ  liệu chính không nhất thiết phải được sắp xếp. 2.4. Cây cân bằng (Balanced tree – B cây) - B­ cây cân bằng được tổ chức theo cấp m, có các tính chất   sau đây: o Gốc của cây hoặc là 1 nút lá hoặc là có ít nhất  2 con o Mỗi nút (trừ nút gốc và nút là) có từ [m/2] đến  m con o Mỗi đường đi từ gốc đến bất kỳ lá nào đều có  độ dài như nhau - Cách tổ chức dữ liệu:  o Mỗi nút trên cây cân bằng có dạng (P0,k1,P1,… kn.Pn). Với Pi là con trỏ trỏ tới khối i mà ki là khoá đầu 1≤k≤n o Các khoá trong 1 nút được sắp xếp tăng dần o Mọi khóa trong cây con trỏ  bới con trỏ  P0 đều  nhỏ hơn k1. Mọi khoá trong cây con trỏ bởi Pn đều > Kn o Các nút lá chỉ chứa khoá của bản ghi trong tệp  (nút lá trỏ bởi Pi chứa khoá cả khoá ki ▪ ▪ ▪ ▪ ▪1 ▪ 1 ▪ ▪ 2 5 ▪ ▪ ▪ ▪   1 2 3 1 1 14 2 3 Hình 1.5. Biểu diễn cây cân bằng.  Tìm kiếm bản ghi 12
  13. Nhập môn cơ sở dữ liệu – Phạm Thị Thanh, Khoa Ngoại ngữ & Tin học Giả sử cần tìm bản ghi có khoá x. Trước hết cần xác định đường đi từ nút gốc  đến nút là có thể chứa bản ghi này. Muốn vậy liên tiếp duyệt các nút của B­ cây kể từ nút gốc. Tại mỗi nút sẽ xác định con trỏ đi tới nút tiếp theo. Thủ tục: So sánh khoá x với các khoá k1,…kn tại nút đang xét. Nếu ki≤x
  14. Nhập môn cơ sở dữ liệu – Phạm Thị Thanh, Khoa Ngoại ngữ & Tin học xem xét nút đó có hơn [m/2+1] cặp (k,p). ngược lại nếu nút bên trái hoặc phải   có đúng [m/2] khi đó ghép p và p’ thành 1 nút mới, quá trình truyền  ứng lên  đến gốc của cây. 3. Ba mô hình dữ liệu cơ bản 3.1. Mô hình hóa trong tin học Là sự  xác lập tương quan giữa các đặc trưng, các tính chất của đối  tượng trong thế giới thực với các phần tử của 1 tập hợp cho trước sao cho các   thông tin của các phần tử này luôn phù hợp với sự  vận động và biến đổi của  đối tượng được mô tả. 3.2. Mô hình dữ liệu:  Mô hình dữ liệu là một tập hợp các khái niệm và các ký pháp dùng để  mô tả  dữ  liệu, các mối quan hệ  của dữ  liệu, các ràng buộc trên dữ  liệu của   một tổ chức. Mô hình dữ liệu gồm 3 thành phần: - Phần mô tả cấu trúc của CSDL  - Phần mô tả  các thao tác,  định nghĩa các phép toán  được  phép trên dữ liệu - Phần mô tả  các ràng buộc toàn vẹn để  đảm bảo sự  chính  xác của dữ liệu. 3.3. Các mô hình dữ liệu cơ bản Có 3 nhóm cơ bản: Mô hình logic trên cơ sở đối tượng, mô hình logic trên cơ  sở bản ghi và mô hình vật lý 3.3.1. Mô hình logic trên cơ sở đối tượng (Object­based Data Models):  Có 2 loại mô hình thường được nhắc đến là mô hình thực thể mối quan hệ và  mô hình đối tượng. 3.3.1.1 Mô hình thực thể mối quan hệ (mô hình E­R):  Mô hình này được xây dựng trên nhận thức là thế giới thực mà chúng ta muốn   phản ánh là một tập hợp các đối tượng cơ  sở  và các mối quan hệ  (liên kết)  giữa chúng. 14
  15. Nhập môn cơ sở dữ liệu – Phạm Thị Thanh, Khoa Ngoại ngữ & Tin học - Thực thể (Entity): Là đối tượng có thực hay trừu tượng mà  ta muốn ghi chép thông tin của nó - Mối quan hệ  (Relationship): Là liên kết giữa các thực thể  phản ánh sự ràng buộc về mặt quản lý. - Kiểu liên kết: Có 3 kiểu:  o Liên kết 1­1: A –B o Liên kết 1­n: A   B o Liên kết n­n : A B Thông thường liên kết 1­1 được đưa về cùng một thực thể, liên kết n­n  được tách thành 2 liên kết 1­n, bằng cách thêm 1 thực thể C   B, C  A Cấu trúc tổng thể của một CSDL có thể được biểu thị bởi một biểu đồ  E­R, được thành lập từ các thành phần sau: Hình chữ nhật biểu diễn các tập thực thể Hình ellip biểu diễn các thuộc tính Hình thoi biểu diễn các quan hệ Các đường nối các thuộc tính với tập các thực thể và các tập thực thể  với mối quan hệ. Ví dụ 1:  Khách hàng người  Tài khoản gửi Tên khách  Địa chỉ Số dư hàng Số tài khoản Số chứng minh  thư Hình 1.6 Ví dụ mô hình E­R Ví dụ 2: Cho 2 thực thể độc giả và sách, quan hệ là người mượn Với thực thể độc giả có các thuộc tính: Mã thẻ độc giả, Tên độc giả, Địa chỉ Với thực thể Sách có các thuộc tính Mã sách, tên sách, tác giả, năm xuất bản,  nhà xuất bản. Hãy vẽ biểu đồ E­ R cho mô hình trên. 15
  16. Nhập môn cơ sở dữ liệu – Phạm Thị Thanh, Khoa Ngoại ngữ & Tin học 3.3.1.2 Mô hình hướng đối tượng:  Dựa trên cơ  sở  tập các đối tượng. Mỗi đối tượng chứa các thuộc tính   (Property) được lưu trữ qua các biến thể hiện (Instance variables)  ở bên trong  đối   tượng.   Một   đối   tượng   chứa   phần   mã   thao   tác   trên   đối   tượng   gọi   là  phương thức (method). VD: Đối tượng tài khoản ngân hàng chứa biến thể  hiện là số  hiệu tài khoản   và số dư. Nó chứa 1 phương thức là trả lãi 3.3.2. Mô hình logic trên cơ sở bản ghi.  Có 3 loại:  - Mô hình quan hệ (Relation Data model):  Sử  dụng các khái niệm về  quan hệ: lược đồ  quan hệ, thuộc tính (cột), bộ  (hàng). Trong mô hình quan hệ, dữ liệu được biểu diễn dưới 1 dạng duy nhất  là các quan hệ (bảng) gồm các thuộc tính (cột) và các bộ (hàng). Mối liên kết giữa các quan hệ có 3 loại liên kết như mô hình thực thể Lop   sinhvien, xác định một lớp có nhiều sinh viên. Đặc điểm của mô hình quan hệ: + Có sơ  sở  chặt chẽ  cho phép áp dụng rộng rãi các công cụ  đại số  và   logic. + Khá tự nhiên, gần gũi với quan niệm thông thường của người sử dụng. + Ngôn ngữ rõ ràng, dễ học dễ hiểu, dễ cập nhật tới các đơn vị dữ liệu + Dễ đảm bảo tính độc lập dữ liệu. VD: bảng SINHVIÊN MA  Ho_Ten Ngay_Sinh Dia_Chi Ma_Nganh SV K1301 Nguyễn An 10/10/91 Hoa Lư TT K1302 Trần Cường 5/9/90 Hoa Lư LK K1303 Lê Lan 15/3/89 Kim Sơn VS - Mô hình phân cấp (Hierarchical data model) Trong mô hình phân cấp, dữ  liệu được biểu diễn theo dạng cây. Mỗi đối  tượng của cơ  sở  dữ liệu được thể  hiện như  một nút của cây và các liên kết   được thể hiện như các cung. 16
  17. Nhập môn cơ sở dữ liệu – Phạm Thị Thanh, Khoa Ngoại ngữ & Tin học ĐH Hoa lư Khoa tự nhiên Khoa Kt & CN Khoa xã hội T12A T12B T13A T13B T13C DH Văn Hình 1.7 Ví dụ mô hình phân cấp - Mô hình mạng (Network data model): Là trường hợp đặc  biệt của mô hình phân cấp. Trong đó CSDL được biểu diễn dưới  dạng một đồ thị, các đối tượng là các nút, các cung là các liên kết. 3.3.3. Mô hình vật lý  Mô tả dữ liệu  ở mức thấp nhất, nghĩa là mô tả  dữ liệu được lưu trữ  như  thế  nào trong máy tính, mô tả  các cấu trúc bản ghi, thứ  tự  các bản ghi và con  đường truy cập. Mô hình vật lý có 2 loại cơ  bản: mô hình thống nhất và mô hình khung ­ bộ  nhớ. (không nghiên cứu trong nội dung giáo trình) Kết chương Chương này đã trình bày các khái niệm cơ bản nhất về  cơ sở dữ liệu. Trình  bày về tổ chức dữ liệu mức vật lý với ba phương pháp tổ chức cụ thể và giới  thiệu các mô hình dữ liệu cơ bản Câu hỏi và bài tập Câu 1: Nêu khái niệm CSDL, hệ quản trị cơ sở dữ liệu, hệ cơ sở dữ liệu? Câu 2: Mục đích của kiến trúc 3 mức trong CSDL? Nêu rõ từng mức kiến trúc  đó? Câu 3: Phân biệt độc lập dữ liệu mức vật lý và độc lập dữ liệu mức logic Câu 4: Nêu cách tổ chức dữ liệu dạng tệp băm. Các thao tác với bản ghi trong  mô hình này? 17
  18. Nhập môn cơ sở dữ liệu – Phạm Thị Thanh, Khoa Ngoại ngữ & Tin học Câu 5: Nêu cách tổ chức dữ liệu dạng tệp chỉ số. Các thao tác với bản ghi  trong mô hình này? Câu 6: Nêu cách tổ chức dữ liệu dạng cây cân bằng. Các thao tác với bản ghi  trong mô hình này? Câu 7: Nêu các loại mô hình dữ liệu mà Anh (Chị) biết? 18
  19. Nhập môn cơ sở dữ liệu – Phạm Thị Thanh, Khoa Ngoại ngữ & Tin học CHƯƠNG II: NGÔN NGỮ THAO TÁC  DỮ LIỆU  1. Cơ sở dữ liệu quan hệ 1.1. Khái niệm cơ bản  - Mô hình quan hệ: là các dữ liệu của bài toán quản lý được  tổ chức dưới dạng các bảng dữ liệu. Bảng được tổ chức theo hàng, cột.  - Thuộc tính: là một đặc trưng của đối tượng được mô tả. - Lược đồ quan hệ: Bao gồm tên lược đồ và tập các thuộc  tính. ký hiệu: R(U), R(A1,A2,..An) - Khái niệm miền trị: Cho tập thuộc tính U có n thuộc tính,  lược đồ  quan hệ  R(U)= R(A1,A2,…Rn), mỗi thuộc tính Ai có một miền  giá trị ký hiệu là Dom(Ai) - Quan hệ  (r) trên tập thuộc tính R là một tập con của tích  đề_các các miền giá trị Dom(Ai). Như vậy mỗi phần tử của quan hệ r là  một bộ t=(t1,t2…tn) trong đó ti Dom(Ai) - VD1:Cho   quan   hệ   r1={SBD,HoDem,   Ten,   NgaySinh,  QueQuan} Dom(SBD)={C2701, C2702,C2703…} ký hiệu gồm chữ và số Dom(HoDem)={Nguyễn Thị, Nguyễn Văn, Phạm Thị…} tập hợp họ đệm  của người VN Dom(Ten)={Lan, Hoa, Mai…} tập hợp tên của người VN Dom(NgaySinh }={ngày/tháng/năm} Dom(QueQuan)={Hoa Lư, Gia viễn…} tập hợp tên các huyện thị t=(C2734, Nguyễn Thị, Lan, 16/5/1988, Hoa Lư, 7, 9, 6) - VD2: Cho quan hệ r2={SBD, Đmôn1, Đmôn2, Đmôn3} Dom (Đmôn1)={0­>10} ….. 19
  20. Nhập môn cơ sở dữ liệu – Phạm Thị Thanh, Khoa Ngoại ngữ & Tin học - Khoá: Là một tập con các thuộc tính, khoá đảm bảo rằng  không có cặp bộ nào trong quan hệ hoàn toàn giống nhau. Trong VD1 thì   SBD là khoá. - Khoá kết nối:  Là một loại khoá dùng để  kết nối 2 quan  hệ. Chẳng hạn ở 2 VD trên để liên kết 2 quan hệ r1 và r2 thì khoá kết nối  là SBD. 1.2. Các thao tác cập nhật dữ liệu trên quan hệ Có 3 phép cơ bản trên một quan hệ: phép chèn, phép xoá và phép sửa đổi. Giả  sử  ta có quan hệ  r trên tập các thuộc tính {A 1, A2, A3,…,An} khoá của  quan hệ là thuộc tính Ak. - Phép chèn: Phép này bổ xung thêm 1 bộ  vào một quan hệ.  Ký hiệu Insert(r;A1=a1,A2=a2,….An=an). Nếu  coi thứ tự các thuộc tính là cố  định thì có thể viết Insert (r; a1, a2,…an).   - VD cho quan hệ: r MaSV HoDem Ten NgaySinh DiaChi MaNganh K1301 Nguyễn An Anh 10/10/91 Hoa Lư TT K1302 Trần Lê Mai 5/9/90 Hoa Lư LK K1303 Lê Lan Ninh 15/3/89 Kim Sơn VS Phép   chèn:   Insert(r;   “K1304”;   “Nguyễn   Hoàng”,   “Oanh”,   “12/7/88”,   “Gia  Viễn”, “TT”) lúc đó quan hệ trở thành  MaSV HoDem Ten NgaySinh DiaChi MaNganh K1301 Nguyễn An Anh 10/10/91 Hoa Lư TT K1302 Trần Lê Mai 5/9/90 Hoa Lư LK K1303 Lê Lan Ninh 15/3/89 Kim Sơn VS K1304 Nguyễn Hoàng Oanh 12/7/88 Gia Viễn TT Lưu ý: Khi chèn thêm bộ, khóa của bộ mới thêm không được trùng với bất cứ  khóa nào đã có trong quan hệ - Phép xoá:  Xoá đi một bộ  đã có trong quan hệ  r, ký hiệu   Delete (r; A1=a1, A2=a2, …, An=an) hoặc Delete (r; a1, a2, …, an) hoặc thuộc  tính khoá là Ak thì Delete (r; Ak=ak). - VD với quan hệ r trên, Delete (r; K1302) thì quan hệ r biến   đối thành MaSV HoDem Ten NgaySinh DiaChi MaNganh 20
ADSENSE

CÓ THỂ BẠN MUỐN DOWNLOAD

 

Đồng bộ tài khoản
2=>2