Nhập môn Cơ sở dữ liệu - Phạm Thị Thanh
lượt xem 25
download
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.
Bình luận(0) Đăng nhập để gửi bình luận!
Nội dung Text: Nhập môn Cơ sở dữ liệu - Phạm Thị Thanh
- 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
- 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 DefendencyFD) ................................................ 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
- 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
- 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
- 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
- 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 AdministratorDBA) 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
- 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
- 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 k1. Ở đầ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
- Nhập môn cơ sở dữ liệu – Phạm Thị Thanh, Khoa Ngoại ngữ & Tin học 0 * Null 1 * Null k1 * 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
- 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
- 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
- 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
- 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
- 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 (Objectbased 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 ER): 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
- 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 11: A –B o Liên kết 1n: A B o Liên kết nn : A B Thông thường liên kết 11 được đưa về cùng một thực thể, liên kết nn được tách thành 2 liên kết 1n, 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 đồ ER, đượ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 ER 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
- 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
- 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
- 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
- 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
- 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
CÓ THỂ BẠN MUỐN DOWNLOAD
-
Nhập môn Cơ sở Dữ liệu
4 p | 385 | 118
-
Nhập môn Cơ sở Dữ liệu ( Ths. Phan Võ Minh Thắng) - Phần 1
61 p | 286 | 97
-
Nhập môn Cơ sở Dữ liệu ( Ths. Phan Võ Minh Thắng ) - Phần 2
64 p | 292 | 80
-
Bài giảng Nhập môn cơ sở dữ liệu
188 p | 341 | 54
-
Bài giảng nhập môn cơ sở dữ liệu - Nguyễn Duy Nhất
26 p | 307 | 44
-
Nhập môn Cơ sở Dữ liệu - Phần 5
51 p | 204 | 38
-
Bài giảng môn học Cơ sở dữ liệu - ThS. Lê Ngọc Lãm
168 p | 103 | 11
-
Bài giảng môn học Nhập môn cơ sở dữ liệu
126 p | 136 | 10
-
Chương 1: Nhập môn cơ sở dữ liệu
62 p | 174 | 10
-
Bài giảng Giới thiệu về đồ án môn học Nhập môn cơ sở dữ liệu - Vũ Tuyết Trinh
8 p | 95 | 5
-
Bài giảng Nhập môn cơ sở dữ liệu: Chương 3 - Vũ Tuyết Trinh
45 p | 41 | 5
-
Bài giảng Nhập môn cơ sở dữ liệu: Chương 2 - Vũ Tuyết Trinh
27 p | 78 | 4
-
Bài giảng Nhập môn cơ sở dữ liệu: Giới thiệu - Vũ Tuyết Trinh
6 p | 91 | 4
-
Bài giảng Nhập môn cơ sở dữ liệu: Giới thiệu môn học - Vũ Tuyết Trinh
8 p | 80 | 4
-
Bài giảng Nhập môn cơ sở dữ liệu: Chương 1 - Vũ Tuyết Trinh
17 p | 86 | 3
-
Bài giảng Nhập môn cơ sở dữ liệu: Chương 4 - Vũ Tuyết Trinh
25 p | 52 | 3
-
Bài giảng Nhập môn cơ sở dữ liệu: Chương 5 - Vũ Tuyết Trinh
13 p | 72 | 2
Chịu trách nhiệm nội dung:
Nguyễn Công Hà - Giám đốc Công ty TNHH TÀI LIỆU TRỰC TUYẾN VI NA
LIÊN HỆ
Địa chỉ: P402, 54A Nơ Trang Long, Phường 14, Q.Bình Thạnh, TP.HCM
Hotline: 093 303 0098
Email: support@tailieu.vn