Giáo Trình SQL Bài 2

BÀI 2 – MÔ HÌNH DỮ LIỆU QUAN HỆ
CƠ SỞ DỮ LIỆU
I. Các khái niệm cơ bản
II. Các phép toán cơ bản
III. Tổ chức dữ liệu vật lý
BÀI 2 – MÔ HÌNH DỮ LIỆU QUAN HỆ
I. Các khái niệm cơ bản
1. Quan hệ
* Miền (Domain)
- Là một tập các giá trị.
- Ví dụ:
Tập các số nguyên là một miền.
Tập các xâu ký tự tạo thành tên người trong tiếng anh có dài không quá 30 ký tự là một miền.
Tập hai số {0,1} là một miền …
- Các thuộc tính của đối tượng sẽ nhận các giá trị trong miền.
BÀI 2 – MÔ HÌNH DỮ LIỆU QUAN HỆ
1. Quan hệ
* Tích đề các của các miền
- Gọi D1, D2, D3, …, Dn là n miềm. Tích đề các của n miền là D1x D2 x D3 x …x Dn là tập tất cả n bộ (n-tuples) (V1, V2,…, Vn) sao cho Vi thuộc Di với i = 1..n.
Ví dụ, với n = 2, D1= {0,1}, D2 = {a,b,c}
 Tích đề các của D1 x D2 = {(0,a), (0,b), (0,c),(1,a), (1,b), (1,c)}.
I. Các khái niệm cơ bản
BÀI 2 – MÔ HÌNH DỮ LIỆU QUAN HỆ
1. Quan hệ
* Quan hệ (Ralation)
- Quan hệ là một tập con của tích đề các của một hoặc nhiều miền.
Như vậy ta có thể xem quan hệ là bảng 2 chiều (bảng quan hệ) có các dòng và các cột:
Các cột ứng với các miền.
Các dòng ứng với các bộ của tích đề các.
- Do tích chất của tích đề các, thứ tự các cột cũng như thứ tự các dòng trong bảng là không quan trọng.
* Thuộc tính (Atribute)
- Thuộc tính của một quan hệ là cột của bảng quan hệ, đặc trưng bởi một tên.
I. Các khái niệm cơ bản
BÀI 2 – MÔ HÌNH DỮ LIỆU QUAN HỆ
1. Quan hệ
* Định nghĩa quan hệ một cách hình thức
 Với định nghĩa quan hệ này thì chúng ta gọi R là sơ đồ (lược đồ) quan hệ và nói quan hệ r xác định trên sơ đồ (lược đồ) quan hệ R.
I. Các khái niệm cơ bản
BÀI 2 – MÔ HÌNH DỮ LIỆU QUAN HỆ
1. Quan hệ
- Ví dụ: Hình 1 cho thấy quan hệ NHAN_VIEN bao gồm các thuộc tính HO_TEN, NAM_SINH, NOI_LAM_VIEC và LUONG.
 Khi đó t1 = (Lê văn A, 1960, Viện KHNV, 425) là một bộ của quan hệ NHAN_VIEN.
I. Các khái niệm cơ bản
BÀI 2 – MÔ HÌNH DỮ LIỆU QUAN HỆ
2. Khóa (key)
Định nghĩa 2.1: Khóa của một quan hệ r trên tập thuộc tính R={A1,…,An} là một tập con K{A1,…,An} thỏa mãn tính chất sau:
Với bất kỳ 2 bộ t1, t2 thuộc r đều tồn tại một thuộc tính A thuộc K sao cho t1(A) ≠ t2(A).
Nói cách khác, không tồn tại 2 bộ mà có giá trị bằng nhau trên mọi thuộc tính của K. Khi đó ta có thể viết t1(K)≠t2(K). Do vậy mỗi giá trị của K là xác định duy nhất.
I. Các khái niệm cơ bản
BÀI 2 – MÔ HÌNH DỮ LIỆU QUAN HỆ
2. Khóa (key)
- Để có thể định nghĩa khóa một cách tốt hơn, lưu ý rằng, nếu K’ là khóa của quan hệ r(A1,…,An) thì với mọi K sao cho K’ K, K cũng là khóa của r, nghĩa là bất kỳ t1, t2 thuộc r từ t1(K’)≠t2(K’) luôn có t1(K)≠t2(K).
- Thông thường người ta lựa chọn một khóa tối thiểu tốt nhất làm khóa chính của quan hệ, các khóa tối thiểu khác được xem là khóa dự phòng.
I. Các khái niệm cơ bản
BÀI 2 – MÔ HÌNH DỮ LIỆU QUAN HỆ
2. Khóa (key)
Định nghĩa 2.3: Một tập con K R được gọi là khóa ngọai của quan hệ r xác định trên tập thuộc tính R tham chiếu đến quan hệ r’ nếu K là khóa chính của quan hệ r’.
- Ví dụ, Ta có quan hệ HANG_HOA như sau:
 Trong quan hệ này thì MSMH là khóa. Mỗi giá trị MSMH đều xác định duy nhất một loại mặt hàng trong quan hệ HANG_HOA.
I. Các khái niệm cơ bản
BÀI 2 – MÔ HÌNH DỮ LIỆU QUAN HỆ
II. Các phép toán trên cơ sở dữ liệu quan hệ
Các phép toán cơ bản nhờ đó là CSDL được thay đổi là
Chèn (insert)
Loại bỏ (delete)
Thay đổi (change)
- Trong mô hình quan hệ được nên trên thì các phép toán này đước áp dụng cho từng bộ của các quan hệ lưu trữ trong máy.
BÀI 2 – MÔ HÌNH DỮ LIỆU QUAN HỆ
1. Phép chèn (INSERT)
- Phép chèn là phép thêm một bộ vào quan hệ r(A1,…, An) có dạng r = r t.
- Nó có dạng: INSERT(r; A1=d1, A2=d2,…,An=dn). Trong đó Ai với i=1..n là tên của các thuộc tính và di thuộc vào dom(Ai) là các giá trị thuộc miền trị tương ứng của thuộc tính Ai.
- Ví dụ: Thêm một bộ t4 = (Vũ văn tần, 1960, Trường ĐHBK, 425) vào quan hệ NHAN_VIEN trong hình 1 như sau:
INSERT(NHAN_VIEN; HO_TEN = Vũ văn tần, NAM_SINH = 1960, NOI_LAM_VIEC = Trường ĐHBK, LUONG = 425).
- Nếu xem thứ tự các trường là cố định, khi đó ta có thể biểu diễn phép chèn như sau:
INSERT(r; d1,d2,…,dn).
II. Các phép toán trên cơ sở dữ liệu quan hệ
BÀI 2 – MÔ HÌNH DỮ LIỆU QUAN HỆ
1. Phép chèn (INSERT)
- Kết quả của phép chèn có thể gây ra một số sai sót với những lý do sau:
II. Các phép toán trên cơ sở dữ liệu quan hệ
BÀI 2 – MÔ HÌNH DỮ LIỆU QUAN HỆ
Bộ mới được thêm vào là không phù hợp với lược đồ quan hệ cho trước.
Một số giá trị của một số thuộc tính nằm nằm ngoài miền giá trị của thuộc tính đó.
Giá trị khóa của bộ mới có thể là giá trị đã có trong quan hệ đang lưu trữ.
2. Phép loại bỏ (DEL)
Phép loại bỏ là phép xóa một bộ ra khỏi quan hệ cho trước, nó có dạng: r=r – t
DEL (r;A1=d1,A2=d2,…,An=dn) hoặc DEL (r; d1,d2,…,dn).
Ví dụ, cần loại bỏ t1 từ quan hệ NHAN_VIEN trong hình 1 như sau:
DEL (NHAN_VIEN; Lê văn A, 1960, Viện KHNV, 425)
II. Các phép toán trên cơ sở dữ liệu quan hệ
BÀI 2 – MÔ HÌNH DỮ LIỆU QUAN HỆ
2. Phép loại bỏ (DEL)
- Tuy nhiên không phải lúc nào phép loại bỏ cũng cần đầy đủ thông tin về cả bộ. Nếu có giá trị về bộ đó tại thuộc tính khóa K={B1,…,Bn}khi đó phép loại bỏ chỉ cần viết:
DEL (r; B1=e1, B2=e2,…,Bi=ei).
- Ví dụ, cần loại bỏ sắt phi 6 ra khỏi quan hệ HANG_HOA (hình 2), khi đó chỉ cần viết:
DEL (HANG_HOA; MSMH=10101)
II. Các phép toán trên cơ sở dữ liệu quan hệ
BÀI 2 – MÔ HÌNH DỮ LIỆU QUAN HỆ
3. Phép thay đổi (CH)
- Dùng để sửa đổi một số giá trị nào đó tại một số thuộc tính nào đó của quan hệ r.
- Nếu K={B1,…,Bm}là khóa của quan hệ, khi đó chỉ cần viết phép thay đổi như sau:
CH(r;B1=d1,B2=d2,…,Bm=dm; C1=e1,C2=e2,…,Cp=ep)
Ví dụ, cần thay đổi số lượng sắt phi 8 trong quan hệ HANG_HOA (hình 2) còn 150 tấn như sau:
CH(HANG_HOA; MSMH=10102;SOLUONG=150)
II. Các phép toán trên cơ sở dữ liệu quan hệ
BÀI 2 – MÔ HÌNH DỮ LIỆU QUAN HỆ
III. Tổ chức dữ liệu vật lý
1. Mô hình tổ chức bộ nhớ ngoài
BÀI 2 – MÔ HÌNH DỮ LIỆU QUAN HỆ
2. Tổ chức dữ liệu dạng Tệp băm (Hashed File)
3. Tổ chức dữ liệu dạng Tệp chỉ số (Indexed Files)
4. Tổ chức dữ liệu dạng B-cây (Balanced trees) (cây cân bằng)
III. Tổ chức dữ liệu vật lý
1. Mô hình tổ chức bộ nhớ ngoài
- Bộ nhớ ngoài được phân chia thành các khối vật lý có kích cỡ như nhau. Mỗi khối chiếm khoảng 512 bytes đến 4090 bytes và được đánh địa chỉ khối. Địa chỉ này là địa chỉ tuyệt đối trên đĩa.
- Mỗi tệp dữ liệu lưu trữ trên đĩa sẽ chiếm một hoặc nhiều khối, mỗi khối chứa một hoặc nhiều bản ghi. Việc thao tác với các tệp dữ liệu sẽ thông qua tên của tệp mà thực chất là thông qua địa chỉ tuyệt đối của các khối.
BÀI 2 – MÔ HÌNH DỮ LIỆU QUAN HỆ
1. Mô hình tổ chức bộ nhớ ngoài
- Các bản ghi đều có địa chỉ và thường được xem là địa chỉ tuyệt đối của byte đầu tiên của bản ghi hoặc là địa chỉ của khối chứa bản ghi đó.
- Địa chỉ của các bản ghi hoặc các khối thường được lưu ở một tệp hoặc một vị trí nào đó để khi cần, qua đó có thể truy nhập tới dữ liệu cần thiết. Chỉ dẫn đó được gọi là con trỏ (pointer).
III. Tổ chức dữ liệu vật lý
BÀI 2 – MÔ HÌNH DỮ LIỆU QUAN HỆ
2. Tổ chức dữ liệu dạng Tệp băm (Hashed File)
2.1. Tổ chức tệp dữ liệu
- Khái niệm hàm băm: Nếu mỗi bản ghi đều có một khóa là giá trị số (ví dụ là x), hàm băm h(x) (đối số là x) nhận một giá trị trong khoảng [0,k] với k là một giá trị nguyên dương nào đó (thường lấy k là một số nguyên tố) khi đó ta xác định hàm băm như sau: h(x) = x mod k.
- Tư tưởng cơ bản của tổ chức tệp băm là 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. Mỗi cụm bao gồm một hoặc nhiều khối. Mỗi khối chứa một số lượng cố định các bản ghi.
III. Tổ chức dữ liệu vật lý
BÀI 2 – MÔ HÌNH DỮ LIỆU QUAN HỆ
2. Tổ chức dữ liệu dạng Tệp băm (Hashed File)
2.1. Tổ chức tệp dữ liệu
- Mỗi cụm ứng với một địa chỉ băm. Địa chỉ băm được đánh số từ 0 tới 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ó một bảng chỉ dẫn cụm chứa k con trỏ, mỗi con trỏ ứng với mỗi cụm, đó là địa chỉ của khối đầu tiên trong cụm.
III. Tổ chức dữ liệu vật lý
BÀI 2 – MÔ HÌNH DỮ LIỆU QUAN HỆ
2. Tổ chức dữ liệu dạng Tệp băm (Hashed File)
2.1. Tổ chức tệp dữ liệu
- Ví dụ, hình 3 là mô hình tổ chức tệp băm với k cụm:
Cụm 0 có 2 khối b1 và b2. Khối b2 có con trỏ rỗng “Null”.
Cụm 1 có 1 khối b3 và một con trỏ rỗng.
Cụm k-1 có 3 khối b4, b5, b6. Khối b6 có con trỏ rỗng.
III. Tổ chức dữ liệu vật lý
BÀI 2 – MÔ HÌNH DỮ LIỆU QUAN HỆ
2. Tổ chức dữ liệu dạng Tệp băm (Hashed File)
2.1. Tổ chức tệp dữ liệu
- Nếu bảng chí dẫn có kích thước nhỏ thì có thể lưu ở bộ nhớ trong, ngược lại phải lưu ở bộ nhớ ngoài.
III. Tổ chức dữ liệu vật lý
BÀI 2 – MÔ HÌNH DỮ LIỆU QUAN HỆ
2. Tổ chức dữ liệu dạng Tệp băm (Hashed File)
2.2. Các thao tác trên tổ chức tệp băm
2.2.1. Tìm kiếm một bản ghi
Đê tìm bản ghi có khóa x trước hết ta phải tính hàm băm h(x).
III. Tổ chức dữ liệu vật lý
BÀI 2 – MÔ HÌNH DỮ LIỆU QUAN HỆ
Giả sử h(x) = i, i sẽ là địa chỉ băm của cụm i.
Tìm trong khối này xem liệu có bản ghi có khóa x hay không, theo con trỏ ở đầu khối tìm đến khối tiếp theo cho tới khi tìm được bản ghi mong muốn hoặc tới khối cuối cùng của cụm i mà không có bản ghi đó.
Trong bảng chỉ dẫn cụm cho biết con trỏ tới khối đầu tiên (nếu có) tương ứng với i.
2. Tổ chức dữ liệu dạng Tệp băm (Hashed File)
2.2. Các thao tác trên tổ chức tệp băm
2.2.2. Thêm một bản ghi
- Giả sử cần thêm bản ghi có khóa x vào tệp, thủ tục được thực hiện giống như việc tìm kiếm một bản ghi:
Nếu trong tệp đã có một bản ghi có trùng khóa x chứng tỏ bản ghi mới là sai.
Nếu không có bản ghi trùng khóa, bản ghi có khóa x được thêm vào khối đầu tiên trong cụm còn chỗ trống.
III. Tổ chức dữ liệu vật lý
BÀI 2 – MÔ HÌNH DỮ LIỆU QUAN HỆ
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 một khối mới, con trỏ null của khối cuối cùng được trỏ sang khối mới này. Trong trường hợp này thì bản ghi mới sẽ là bản ghi đầu tiên của khối vừa được thiết lập và khối này trở thành khối cuối cùng.
2. Tổ chức dữ liệu dạng Tệp băm (Hashed File)
2.2. Các thao tác trên tổ chức tệp băm
2.2.3. Xóa một bản ghi
Để xóa một bản ghi có khóa x, ta cũng sử dụng thủ tục tìm bản ghi.
III. Tổ chức dữ liệu vật lý
BÀI 2 – MÔ HÌNH DỮ LIỆU QUAN HỆ
Nếu bản ghi thuộc một khối nào đó có nhiều bản ghi khác, khi đó bản ghi có khóa x được loại bỏ.
Nếu bản ghi đó là duy nhất trong khối khi đó sẽ đồng thời việc giải phóng khối khỏi cụm chứa khối.
2. Tổ chức dữ liệu dạng Tệp băm (Hashed File)
2.2. Các thao tác trên tổ chức tệp băm
2.2.4. Sửa bản ghi
- Giả sử cần sửa một số trường của 1 bản ghi có khóa x.
III. Tổ chức dữ liệu vật lý
BÀI 2 – MÔ HÌNH DỮ LIỆU QUAN HỆ
Nếu trường cần sửa có tham gia trong khóa x, việc sửa sẽ loại bỏ bản ghi này và thêm vào bản ghi mới cho tệp.
Nếu trường cần sửa không thuộc khóa, sau khi sử dụng thủ tục tìm bản ghi cần thiết, tiến hành sửa giá trị trong các trường.
Nếu bản ghi không tồn tại xem như có lỗi.
2. Tổ chức dữ liệu dạng Tệp băm (Hashed File)
2.3. Ví dụ
- Cho quan hệ CUNG_CAP(S#, SNAME, STATUS, CITY). Khi đó mỗi bản ghi gồm:
S#: Có kiểu số nguyên và chiếm 4 bytes và là trường khóa.
SNAME: Có kiểu ký tự chiếm 30 bytes.
STATUS: Có kiểu số nguyên chiếm 4 bytes.
CITY: Có kiểu ký tự chiếm 40 bytes.
- Giả sử bây giờ ta lưu trữ tệp CUNG_CAP với 16 bản ghi, mỗi bản ghi chiếm 78 bytes theo tổ chức tệp băm với số cụm là 5.
III. Tổ chức dữ liệu vật lý
BÀI 2 – MÔ HÌNH DỮ LIỆU QUAN HỆ
2. Tổ chức dữ liệu dạng Tệp băm (Hashed File)
2.3. Ví dụ
- Chúng ta sử dụng hàm băm h tác động lên giá trị khóa là một số nguyên như sau: h(x)=x mod5. với x là giá trị khóa cùa bản ghi. Tổ chức băm được chỉ ra trong hình 4.
III. Tổ chức dữ liệu vật lý
BÀI 2 – MÔ HÌNH DỮ LIỆU QUAN HỆ
2. Tổ chức dữ liệu dạng Tệp băm (Hashed File)
2.3. Ví dụ
Giả sử bây giờ chúng ta muốn thêm một bản ghi có khóa 32.
III. Tổ chức dữ liệu vật lý
BÀI 2 – MÔ HÌNH DỮ LIỆU QUAN HỆ
Trước hết chúng ta thực hiện tìm kiếm bản ghi có giá trị khóa là 32. Để tìm kiếm bản ghi này, ta tính hàm băm h(32) = 32 mod 5 =2.
Tra cứu bản chỉ dẫn cụm chúng ta biết con trỏ tới khối đầu tiên của cụm có địa chỉ băm là 2. Ta thực hiện tìm kiếm trong cụm này và không có. Như vậy bản ghi này chưa tồn tại. Chúng ta sẽ thêm nó vào khối đầu tiên trong cụm còn chỗ trống (hình 5)
2. Tổ chức dữ liệu dạng Tệp băm (Hashed File)
2.3. Ví dụ
III. Tổ chức dữ liệu vật lý
BÀI 2 – MÔ HÌNH DỮ LIỆU QUAN HỆ
2. Tổ chức dữ liệu dạng Tệp băm (Hashed File)
2.3. Ví dụ
Giả sử bây giờ chúng ta muốn xóa bản ghi có khóa 64.
III. Tổ chức dữ liệu vật lý
BÀI 2 – MÔ HÌNH DỮ LIỆU QUAN HỆ
Trước hết chúng ta thực hiện tìm kiếm bản ghi có giá trị khóa là 64.
Ta tính hàm băm h(64)= 64mod5=4.
Tra cứu bảng chỉ dẫn cụm ta thấy con trỏ trỏ tới khối đầu tiên của cụm có địa chỉ băm là 4.
Thực hiện tìm kiếm ta thấy 64 có ngay trong khối đầu tiên của cụm và bản ghi này thuộc một khối có nhiều bản ghi khác nữa. Do đó bản ghi này được loại bỏ (hình 6).
2. Tổ chức dữ liệu dạng Tệp băm (Hashed File)
2.3. Ví dụ
III. Tổ chức dữ liệu vật lý
BÀI 2 – MÔ HÌNH DỮ LIỆU QUAN HỆ
3. Tổ chức dữ liệu dạng Tệp chỉ số (Indexed Files)
III. Tổ chức dữ liệu vật lý
BÀI 2 – MÔ HÌNH DỮ LIỆU QUAN HỆ
Là được áp dụng phổ biến nhất trong các hệ cơ sở dữ liệu.
3.1. Tổ chức tệp dữ liệu
- Ta giả thiết rằng tệp dữ liệu chính luôn luôn là tệp được sắp xếp theo khóa (ví dụ theo thứ tự tăng dần).
- Khóa luôn được quan niệm rằng, bao gồm một hoặc nhiều trường có thứ tự và có độ dài cố định.
- Giá trị khóa có thể là số, cũng có thể là một xâu ký tự. Nếu là xâu ký tự thì sắp theo A, B, C…hay thứ tự từ điển.
3. Tổ chức dữ liệu dạng Tệp chỉ số (Indexed Files)
III. Tổ chức dữ liệu vật lý
BÀI 2 – MÔ HÌNH DỮ LIỆU QUAN HỆ
3.1. Tổ chức tệp dữ liệu
- Để hỗ trợ cho tệp dữ liệu chính, cấu tạo một tệp chỉ số theo khóa được chọn.
- Tệp chỉ số bao gồm các cặp (k,d) trong đó k là giá trị của khóa, d là địa chỉ của khối (hay con trỏ khối).
- Các cặp này được sắp xếp theo giá trị của khóa (hình 7)
3. Tổ chức dữ liệu dạng Tệp chỉ số (Indexed Files)
III. Tổ chức dữ liệu vật lý
BÀI 2 – MÔ HÌNH DỮ LIỆU QUAN HỆ
3.1. Tổ chức tệp dữ liệu
3. Tổ chức dữ liệu dạng Tệp chỉ số (Indexed Files)
III. Tổ chức dữ liệu vật lý
BÀI 2 – MÔ HÌNH DỮ LIỆU QUAN HỆ
3.1. Tổ chức tệp dữ liệu
- Mỗi khối trong tệp dữ liệu chính chứa một số lượng bản ghi cố định và được đại diện bởi một cặp (k,d) trong tệp chỉ số, trong đó k là giá trị khóa của bản ghi đầu tiên trong khối và d là địa chỉ khối.
- Trong hình 7 ta thấy một tệp chỉ số với một tệp dữ liệu chính được lưu trữ trên m khối. Do vậy tệp chỉ số bao gồm m bản ghi tương ứng với m cặp (k,d). Trong đó k là khóa của bản ghi đầu tiên trong khối và d là địa chỉ của khối hay con trỏ khối
3. Tổ chức dữ liệu dạng Tệp chỉ số (Indexed Files)
III. Tổ chức dữ liệu vật lý
BÀI 2 – MÔ HÌNH DỮ LIỆU QUAN HỆ
3.2. Các phép toán trên tệp chỉ số
3.2.1. Tìm kiếm một bản ghi trên tệp chỉ số
- Giả sử cần tìm một bản ghi có khóa x, có thể sử dụng 2 cách sau để duyệt trong tệp chỉ số:
* Tìm tuần tự
* Tìm kiếm nhị phân
3. Tổ chức dữ liệu dạng Tệp chỉ số (Indexed Files)
III. Tổ chức dữ liệu vật lý
BÀI 2 – MÔ HÌNH DỮ LIỆU QUAN HỆ
3.2. Các phép toán trên tệp chỉ số
3.2.1. Tìm kiếm một bản ghi trên tệp chỉ số
* Tìm tuần tự
- Duyệt trong tệp chỉ số các cặp (k,d), 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ể thuộc khối đứng ngang trước khối (k’,d’), ví dụ là (k1,d1).
- Trong khối (k1,d1) sẽ tìm tuần tự theo tệp chỉ số cho tới khi gặp giá trị k nào đó bằng x thì giá trị d tương ứng là địa chỉ của bộ cần tìm. Nếu không có giá trị k nào trong khối (k1,d1) bằng x, thì xem như bản ghi không tồn tại.
3. Tổ chức dữ liệu dạng Tệp chỉ số (Indexed Files)
III. Tổ chức dữ liệu vật lý
BÀI 2 – MÔ HÌNH DỮ LIỆU QUAN HỆ
3.2. Các phép toán trên tệp chỉ số
3.2.1. Tìm kiếm một bản ghi trên tệp chỉ số
* Tìm kiếm nhị phân
* Tìm kiếm nhị phân
- Giả sử tệp chỉ số được sắp xếp trên m khối (b1,..,bm).
- Để tìm một bản ghi có khóa x, trước hết chọn khối b[m/2]. So sánh giá trị k thuộc khối b[m/2] và x.
 Nếu k > x thì bộ cần tìm nằm trong các khối từ (b1,…, b[m/2]), ngược lại trong khối từ b[m/2+1],..,bm. ngược lại trong khối từ b[m/2+1],..,bm.
- Quá trình lặp lại cho đến khi còn một khối chứa bản ghi có khóa x. Trong khối này tiếp tục tìm tuần tự trong các cặp (k,d) như phương pháp tìm tuần tự.
3. Tổ chức dữ liệu dạng Tệp chỉ số (Indexed Files)
III. Tổ chức dữ liệu vật lý
BÀI 2 – MÔ HÌNH DỮ LIỆU QUAN HỆ
3.2. Các phép toán trên tệp chỉ số
3.2.2. Thêm một bản ghi
- Muốn thêm một bản ghi có khóa x vào tệp chỉ số, ta sử dụng thủ tục tìm bản ghi để xác định khối bi (i=1..m) sẽ chứa bản ghi đó.
 Nếu trong khối bi còn chỗ thì thêm bản ghi này vào khối đó đúng theo thứ tự sắp xếp của khóa. 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ó khóa x trong khối bi.
 Nếu bản ghi khóa x là bản ghi đầu tiên của khối thì phải sửa lại khóa k thành x trong tệp chỉ số.
3. Tổ chức dữ liệu dạng Tệp chỉ số (Indexed Files)
III. Tổ chức dữ liệu vật lý
BÀI 2 – MÔ HÌNH DỮ LIỆU QUAN HỆ
3.2. Các phép toán trên tệp chỉ số
3.2.2. Thêm một bản ghi
 Nếu thêm bản ghi vào khối bi hết chỗ thì bản ghi cuối cùng của khối bi sẽ chuyển sang làm bản ghi đầu tiên của khối bi+1, khi đó phải sửa lại giá trị (k,d) của khối bi+1 tương ứng.
 Nếu bản ghi có khóa x là bản ghi cuối cùng , tức x lớn hơn mọi khóa k trong tệp chỉ số và mọi bi đều hết chỗ, khi đó thiết lập một khối mới bi+1, bản ghi này sẽ là bản ghi đầu tiên của khối mới.
3. Tổ chức dữ liệu dạng Tệp chỉ số (Indexed Files)
III. Tổ chức dữ liệu vật lý
BÀI 2 – MÔ HÌNH DỮ LIỆU QUAN HỆ
3.2. Các phép toán trên tệp chỉ số
3.2.3. Xóa một bản ghi
- Quá trình giống như thêm một bản ghi, lưu ý nếu khi xóa một bản ghi tạo nên một khối rỗng, khi đó có thể loại bỏ cả khối đó.
3. Tổ chức dữ liệu dạng Tệp chỉ số (Indexed Files)
III. Tổ chức dữ liệu vật lý
BÀI 2 – MÔ HÌNH DỮ LIỆU QUAN HỆ
3.2. Các phép toán trên tệp chỉ số
3.2.4. Sửa một bản ghi
- Sử dụng thủ tục tìm bản ghi để xác định bản ghi cần sửa:
Nếu trường cần sửa không là khóa, việc sửa đổi các giá trị của bản ghi chỉ 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 cần sửa là khóa thì quá trình sửa lại là quá trình thêm và xóa bản ghi.
3. Tổ chức dữ liệu dạng Tệp chỉ số (Indexed Files)
III. Tổ chức dữ liệu vật lý
BÀI 2 – MÔ HÌNH DỮ LIỆU QUAN HỆ
3.3. Ví dụ
- Cho quan hệ CUNG_CAP(S#, SNAME, STATUS, CITY). Khi đó mỗi bản ghi gồm:
S#: Có kiểu số nguyên và chiếm 4 bytes và là trường khóa.
SNAME: Có kiểu ký tự chiếm 30 bytes.
STATUS: Có kiểu số nguyên chiếm 4 bytes.
CITY: Có kiểu ký tự chiếm 40 bytes.
- Giả sử bây giờ ta lưu trữ tệp CUNG_CAP với 16 bản ghi, mỗi bản ghi chiếm 78 bytes theo tổ chức tệpchỉ số. Ta giả sử rằng các khối có kích thước là 256 bytes  Mỗi khối có thể chứa tối đa là 3 bản ghi (hình 8)
3. Tổ chức dữ liệu dạng Tệp chỉ số (Indexed Files)
III. Tổ chức dữ liệu vật lý
BÀI 2 – MÔ HÌNH DỮ LIỆU QUAN HỆ
3.3. Ví dụ
3. Tổ chức dữ liệu dạng Tệp chỉ số (Indexed Files)
III. Tổ chức dữ liệu vật lý
BÀI 2 – MÔ HÌNH DỮ LIỆU QUAN HỆ
3.3. Ví dụ
- Thêm một bản ghi mới có khóa là 32 vào tệp.
Trước tiên chúng ta thực hiện tìm một bản ghi để xác định khối bi (i=1..m) sẽ chứa bản ghi đó.
Áp dụng cách tìm tuần tự ta tìm được trên bản chỉ dẫn có khóa là 25.
Theo con trỏ của bản chỉ dẫn này, chúng ta đi tới khối có thê chứa bản ghi có khóa là 32.
Tìm trong khối này thấy không có bản ghi nào có khóa là 32 vậy có thể thêm mới nhưng khối này không còn chỗ để thêm một bản ghi nữa.
3. Tổ chức dữ liệu dạng Tệp chỉ số (Indexed Files)
III. Tổ chức dữ liệu vật lý
BÀI 2 – MÔ HÌNH DỮ LIỆU QUAN HỆ
3.3. Ví dụ
Do vậy bản ghi cuối cùng của khối này chuyển thành bản ghi đầu tiên của khối tiếp theo. Khi đó chúng ta phải sửa lại bản chỉ dẫn giá trị (k,d) của khối tiếp theo trong tệp chỉ dẫn. Bây giờ chúng ta mới thêm bản ghi mới có giá trị khóa là 32 vào khối đó đúng theo thứ tự sắp xếp của khóa (hình 9).
3. Tổ chức dữ liệu dạng Tệp chỉ số (Indexed Files)
III. Tổ chức dữ liệu vật lý
BÀI 2 – MÔ HÌNH DỮ LIỆU QUAN HỆ
3.3. Ví dụ
- Xóa bản ghi có khóa 64 với tổ chức tệp chỉ dẫn trong hình 9.
Trước tiên chúng ta sử dụng thủ tục tìm kiếm để xác định khối bi (i=1..m) sẽ chứa bản ghi đó.
Áp dụng tìm kiếm tuần tự ta tìm được khóa 49 trong tệp chỉ số. Theo con trỏ của bản chỉ số này, tìm bản ghi có khóa là 64.
Trong khối này còn chứa bản ghi khác do đó cúng ta xóa bản ghi có khóa là 64 và đưa bản ghi có khóa là 65 vào chỗ bản ghi đã xóa (hình 10).
3. Tổ chức dữ liệu dạng Tệp chỉ số (Indexed Files)
III. Tổ chức dữ liệu vật lý
BÀI 2 – MÔ HÌNH DỮ LIỆU QUAN HỆ
3.3. Ví dụ