Chương 1 Tổng quan về phụ thuộc hàm và phần tử ngoại lai trong CSDL quan hệ 1. Phụ thuộc hàm 1.1 Định nghĩa phụ thuộc hàm Phụ thuộc hàm (functional dependency) là một công cụ dùng để biểu diễn một cách hình thức các ràng buộc. Phương pháp biểu diễn này có rất nhiều ưu điểm, và đây là một công cụ cực kỳ quan trọng, gắn chặt với lý thuyết thiết kế cơ sở dữ liệu (CSDL). Phụ thuộc hàm được ứng dụng trong việc giải quyết các bài toán tìm khóa, tìm phủ tối thiểu và chuẩn hóa CSDL.
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 Codd đã 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. Định nghĩa: Cho R = {a1, a2,., an} là tập các 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 f (ký pháp A ⎯⎯ r → B) nếu: ( hi, hj r) ((a A) ( hi(a) = hj(a)) (b B) ( hi(b) = hj(b) )) nghĩa là đối số trùng nhau thì hàm có cùng giá trị [2]. f Người ta còn viết (A, B) hay A → B thay cho ⎯⎯ r→ B 7 Luan van Lúc đó tập hợp tất cả (A, B) như thế xác định một họ f trên 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. Ý 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. Ví dụ : Xét một quan hệ : THISINH SBD Họtên Điạchỉ Tỉnh Khu vực HP0001 Bùi văn An 14 Kiến Hải 3 An Phòng HP0002 Nguyễn Hải 15 Cát Hải Đăng Hải Phòng 3 HP0003 Nguyễn vân Văn Lạng Anh Lãng Sơn 1 HP0004 Vũ thúy Liên 52 Quang Nam Trung Định 2 Bảng 1 Bảng quan hệ THÍ SINH Trong quan hệ THISINH dựa vào định nghĩa phụ thuộc hàm của quan hệ , có thể kết luận: 8 Luan van f {Tỉnh} ⎯⎯ r → { Khuvực} f {SBD} ⎯⎯ r → { Họtên, Địachỉ, Tỉnh, Khuvực} 1.2 Hệ tiên đề Armstrong Gọi F là tập xác định các phụ thuộc hàm đối với lược đồ quan hệ R và X → Y là một phụ thuộc hàm. Nói rằng X → Y được suy diễn logic từ F nếu mối quan hệ r trên R đều thoả mãn phụ thuộc hàm của F thì cũng thoả mãn X → Y.
Chẳng hạn F ={A → B, B → C} thì A → C suy ra từ F. Gọi F+ là bao đóng (closure) của F, tức là tập tất cả các phụ thuộc hàm được suy diễn logic từ F. Nếu F = F+ thì F là họ đầy đủ (full family) của các phụ thuộc hàm [3]. Để có thể xác định khoá của một lược đồ quan hệ và các suy diễn logic giữa các phụ thuộc hàm cần thiết phải tính được F+ từ F.
Do đó đòi hỏi phải có các hệ tiên đề. Tập các quy tắc của hệ tiên đề được Armstrong (1974) đưa ra, được gọi là hệ tiên đề Armstrong. Định nghĩa: Cho R = {a1,.,an} là tập các thuộc tính. Hệ tiên đề Armstrong bao gồm 3 tính chất cơ bản sau: ➢ A1 (phản xạ) : Nếu Y X thì X → Y ➢ A2 (tăng trưởng) : Nếu Z R và X → Y thì XZ → YZ.
9 Luan van Trong đó ký hiệu XZ là hợp của hai tập X và Z thay cho ký hiệu X Z. ➢ A3 (bắc cầu ) : Nếu X → Y và Y → Z thì X → Z. Nhận xét: ➢ Việc nghiên cứu phụ thuộc hàm không lệ thuộc vào các quan hệ (bảng) cụ thể. Vì vậy, áp dụng được các công cụ toán nhằm sáng tỏ cấu trúc logic của mô hình dữ liệu quan hệ ➢ Có nhiều quan hệ khác nhau nhưng các họ đầy đủ các phụ thuộc hàm của chúng lại như nhau Ví dụ: Cho r1, r2 là các quan hệ: A B A B 0 0 0 0 r1 = 1 1 r2 = 1 1 2 1 2 1 3 2 3 1 Có thể thấy rằng r1 và r2 khác nhau nhưng Fr1 = Fr2 vì chỉ có A → B 1.
Các dạng phụ thuộc hàm đặc biệt loại đơn giản Có một số phụ thuộc hàm có dạng rất đặc biệt. Chúng ta sẽ xét ở đây hai dạng rất đặc biệt trong số đó [4]. Dạng các phụ thuộc hàm dạng bằng nhau Cho bảng dữ liệu r trên R = (A1, A2,. Giả sử với Ap, Aq nào đó thuộc R, mà với mọi ti r ta có: ti(Ap) = ti(Aq).
Khi đó ta dễ thấy có phụ thuộc hàm: Ap → Aq ( cũng đồng thời có Aq → Ap). Người ta gọi các phụ thuộc hàm dạng này là các phụ thuộc hàm dạng bằng nhau [2]. 10 Luan van Các phụ thuộc hàm dạng bằng nhau có trong các bảng dữ liệu được sinh ra trong trường hợp chúng ta kết nối hai hoặc nhiều bảng dữ liệu với nhau. Dạng phụ thuộc hàm dạng tỉ lệ Cho r là một bảng dữ liệu trên tập thuộc tính R.
Giả sử có các thuộc tính số: As, As1, As2, .Ask R và các số thực: p1, p2, .pk với pj 1; j = 1.k k Và p j = 1; với mọi ti r sao cho: j =1 ti(As1) = p1 * ti(As) ti(As2) = p2 * ti(As). ti(Ask) = pk * ti(As) Trong trường hợp này ta có phụ thuộc hàm: As → As1. Ta gọi phụ thuộc hàm dạng này là phụ thuộc hàm dạng tỉ lệ. Gọi pj là tỉ lệ đối với phụ thuộc tính Asj (j = 1.
Trong thực tế chúng ta gặp loại phụ thuộc hàm loại này trong các trường hợp tạo các bảng kê về khối lượng một loại sản phẩm được sản xuất ra cùng với các thành phần dùng để tạo nên sản phẩm đó (theo định mức qui định) [4].3 Phần tử ngoại lai và mối quan hệ giữa chúng với khai phá dữ liệu 1.1 Khái niệm về phần tử ngoại lai Một cách hình thức người ta có thể định nghĩa phần tử ngoại lại (outliers) của một tập dữ liệu là các phần tử mà theo một cách nhìn nào đó có các đặc tình không giống với tập hợp đa số còn lại của tập dữ liệu [1]. Chẳng hạn trong hình dưới đây cho thấy một phần tử ngoại lai theo vị trí hình học: 11 Luan van Hình 1 Phần tử ngoại lai trong tập điểm có tọa độ (x,y) trên mặt phẳng có giá trị tung độ y nhỏ hơn hẳn các phần tử khác của tập hợp Các khái niệm về ngoại lai đầu tiên có nguồn gốc từ lĩnh vực thống kê. Barnett và Lewis định nghĩa: một phần tử ngoại lai là một quan trắc hoặc một tập con các quan trắc mà sự xuất hiện của chúng trái ngược với những quan trắc còn lại. Phần tử ngoại lai cũng có thể được hiểu như một quan trắc mà giá trị của nó khác biệt quá nhiều so với những quan trắc khác gây cho người người ta nghi ngờ rằng nó đã được thực hiện bằng một kỹ thuật khác.
Có nhiều cách định nghĩa và hiểu khác nhau về phần tử ngoại lai. Tuy nhiên chúng có điểm chung là: phần tử ngoại lai của một file dữ liệu là những phần tử của file dữ liệu có sự khác biệt đáng kể đối với những phần tử còn lại. Và khi tiến hành xác định phần tử ngoại lai, trước hết người ta đưa ra định nghĩa, sau đó sẽ xây dựng phương pháp để xác định. Vai trò của phần tử ngoại lai trong mô hình CSDL quan hệ: Cho một bảng dữ liệu r trên một tập thuộc tính R.
Kí hiệu T là tập các qui tắc, ràng buộc (gọi là các luật) mà các phần tử của r phải tuân theo. Phần tử ngoại lai của r là những phần tử của bảng dữ liệu này không tuân theo một trong các qui tắc, ràng buộc đó [4]. Một phần tử của bảng dữ liệu được hiểu là một bộ các giá trị của các thuộc tính. 12 Luan van Các qui tắc, ràng buộc được đề cập bao gồm những ràng buộc về cấu của CSDL (khóa, phụ thuộc hàm, các dạng chuẩn phải tuân theo đối với một quan hệ và các ràng buộc theo ngữ nghĩa phụ thuộc vào yêu cầu, ý nghĩa của ứng dụng mà trong đó CSDL được sử dụng).
Phần tử ngoại lai giữ một vai trò đặc biệt quan trọng trong mô hình CSDL quan hệ, đặc biệt là đối với phụ thuộc hàm của bảng dữ liệu r. Cho r là một bảng dữ liệu trên sơ đồ quan hệ (R,F). Giải thiết r là một quan hệ. Ta gọi một cặp bộ t1, t2 r không thỏa mãn điều kiện phụ thuộc hàm của F là cặp phần tử ngoại lai đối với phụ thuộc hàm của bảng dữ liệu r.
Người ta biểu diễn một cách hình thức như sau: Giả sử X → Y là một phụ thuộc hàm thuộc F. Khi đó cặp t1, t2 r là cặp phần tử ngoại lai đối với phụ thuộc hàm X → Y nếu: t1(X) = t2(X) và t1(Y) t2(Y). Khái niệm phần tử ngoại lai đi cùng với mô hình CSDL quan hệ ngày nay đã ngày càng đi sâu vào mọi mặt trong đời sống kinh tế -xã hội [1]. Chúng dùng để: - Phát hiện xâm nhập (phát hiện các hoạt động nguy hiểm (phá vỡ thâm nhập và các hình thức khác của máy tính lạm dụng) trong một hệ thống máy tính liên quan từ một vấn đề bảo mật.
Khác với hệ thống hành vi bình thường, phát hiện xâm nhập là một ứng cử viên hoàn hảo cho việc áp dụng các kỹ thuật phát hiện ngoại lai). -Phát hiện gian lận (liên quan đến hoạt động tội phạm xảy ra trong các tổ chức thương mại, các tổ chức như ngân hàng, các công ty thẻ tín dụng, cơ quan bảo hiểm, các công ty điện thoại di động, thị trường chứng khoán,… Người sử dụng độc hại có thể là khách hàng thực tế của tổ chức hoặc phải dùng đến hành vi trộm cắp danh tính (giả làm khách hàng). Các hoạt động phát hiện nhằm mục đích 13 Luan van phát hiện tiêu thụ trái phép các nguồn tài nguyên được cung cấp bởi tổ chức để ngăn chặn thiệt hại kinh tế). - Phát hiện bảo hiểm yêu cầu bồi thường gian lận (ví dụ xe hơi gian lận bảo hiểm.