Độ đo phụ thuộc hàm xấp xỉ trong cơ sở dữ liệu mô hình dạng khối

- ĐỘ ĐO PHỤ THUỘC H(M XẤP XỈ TRONG CƠ SỞ ĐỘ ĐO PHỤ THUỘC H(M XẤP XỈ TRONG CƠ SỞ ĐỘ ĐO PHỤ THUỘC H(M XẤP XỈ TRONG CƠ SỞ ĐỘ ĐO PHỤ THUỘC H(M XẤP XỈ TRONG CƠ SỞ.
- DỮ LIỆU DỮ LIỆU DỮ LIỆU.
- DỮ LIỆU MÔ HI MÔ HI MÔ HI›NH DA MÔ HI NH DA NH DA NH DAœNG KHỐI NG KHỐI NG KHỐI NG KHỐI.
- Tóm tắt ắt ắt ắt: Trong báo cáo này, chúng tôi trình bày mô hình dữ liệu dạng khối ñược xem là mở rộng của mô hình dữ liệu quan hệ.
- Phụ thuộc hàm là một loại ràng buộc dữ liệu giữa các thuộc tính trong một cơ sở dữ liệu quan hệ, góp phần vào việc ñảm bảo tính nhất quán của dữ liệu, loại bỏ bớt dữ liệu dư thừa.
- Phụ thuộc hàm trong mô hình dữ liệu dạng khối và các tính chất ñược quan tâm và nghiên cứu..
- Trong bài bào trình bày phương pháp xây dựng ñộ ño phụ thuộc xấp xỉ trong mô hình dữ liệu dạng khối.
- Với hai tập thuộc tính X và Y thuộc khối R, ñộ ño ñược xây dựng dựa trên việc tính toán các ñộ ño xấp xỉ từ các lát cắt (giá trị ñộ ño xấp xỉ nằm trong khoảng từ 0 ñến 1) và lấy giá trị lớn nhất của các ñộ ño ñó.
- Giá trị ñộ ño xấp xỉ của phụ thuộc hàm trên khối R nằm trong khoảng [0-1].
- Một phụ thuộc hàm xấp xỉ trên khối có ñộ ño bằng 0 thì tất cả các phụ thuộc hàm xấp xỉ trên lát cắt chính là phụ thuộc hàm(kinh ñiển)..
- Từ khoá ừ khoá ừ khoá ừ khoá: Phụ thuộc hàm, Khai phá dữ liệu, Phụ thuộc hàm xấp xỉ, Mô hình dữ liệu quan hệ, Mô hình dữ liệu dạng khối..
- Cơ sở dữ liệu là một trong những lĩnh vực quan trọng của công nghệ thông tin.
- Cơ sở dữ liệu ñã ñược nghiên cứu, ứng dụng thành công trong nhiều lĩnh vực và ñem lại hiệu quả kinh tế cao cho ñời sống và xã hội.
- Đã có rất nhiều bài báo nghiên cứu về cơ sở dữ liệu và mô hình cơ sở dữ liệu.
- Có 3 mô hình thường ñược sử dụng: mô hình phân cấp, mô hình mạng và mô hình quan hệ.
- Trong ñó, mô hình quan hệ ñược quan tâm hơn cả.
- Do các quan hệ có cấu trúc phẳng (tuyến tính) nên mô hình này chưa ñủ ñáp ứng ñối với các ứng dụng phức tạp, các cơ sở dữ liệu có cấu trúc phi tuyến… Do ñó việc mở rộng mô hình dữ liệu quan hệ thành mô hình dữ liệu dạng khối nhằm mở ra khả năng quản lí dữ liệu, ñáp ứng nhu cầu thực tế tốt hơn [2]..
- Phụ thuộc hàm (Functional Dependency) là một loại ràng buộc dữ liệu giữa các thuộc tính trong một cơ sở dữ liệu quan hệ, góp phần vào việc ñảm bảo tính nhất quán của dữ liệu, loại bỏ bớt dữ liệu dư thừa.
- Phụ thuộc hàm cũng thể hiện tính chất ngữ nghĩa giữa các thuộc tính và có thể tồn tại trong một tập dữ liệu ñộc lập với mô hình quan hệ.
- Nghiên cứu về các phụ thuộc hàm là một hướng quan trọng trong thiết kế cơ sở dữ liệu quan hệ và ñã ñạt ñược nhiều thành tựu .
- bên cạnh ñó, nghiên cứu về phụ thuộc hàm trong mô hình dữ liệu dạng khối [2] ñã có những kết quả [2, 5] ñể tăng cường hơn nữa khả năng ñảm bảo ngữ nghĩa, góp phần hoàn chỉnh thêm về mô hình dữ liệu dạng khối..
- r(R) là một khối trên R,.
- X → Y là kí hiệu một phụ thuộc hàm.
- Từ ñịnh nghĩa phụ thuộc hàm ở trên, ta nhận thấy: nếu tồn tại 1, 2 t t ∈ r sao cho t 1 (X.
- t(Y), thì có thể kết luận rằng r không thoả phụ thuộc hàm X → Y (hay phụ thuộc hàm X → Y không ñúng trên r.
- Trong thực hành, ñiều này tỏ ra quá chặt và cứng nhắc khi ta hình dung quan hệ r có hàng nghìn bộ, trong ñó chỉ có một vài bộ vi phạm phụ thuộc hàm X → Y do có một số dữ liệu bị sai lệch hoặc ngoại lệ.
- Do ñó việc mở rộng khái niệm phụ thuộc hàm (kinh ñiển) thành phụ thuộc hàm xấp xỉ (trong mô hình dữ liệu quan hệ, mô hình dữ liệu dạng khối) theo một cách thức, một nghĩa nào ñó là nhu cầu tất yếu và tự nhiên..
- Các phụ thuộc hàm xấp xỉ khai phá ñược từ mô hình cơ sở dữ liệu quan hệ, mô hình dữ liệu dạng khối là các mẫu quan trọng, là những tri thức có giá trị về cấu trúc của các bộ dữ liệu..
- MÔ HÌNH DỮ LIỆU DẠNG KHỐI 2.1.
- Khái niệm toán học làm nền tảng cho mô hình cơ sở dữ liệu dạng khối (gọi tắt là mô hình khối) là các khối hiểu theo nghĩa của lí thuyết tập hợp.
- Lát cắt.
- r(R) là một khối trên R.
- Với mỗi x ∈ id ta kí hiệu r(R x ) là một khối với R x = ({x}.
- PHỤ THUỘC HÀM XẤP XỈ TRONG MÔ HÌNH DỮ LIỆU DẠNG KHỐI 3.1.
- Phụ thuộc hàm trong mô hình dữ liệu dạng khối.
- Phụ thuộc hàm ñược suy diễn từ tập phụ thuộc hàm F.
- F là tập các phụ thuộc hàm trên R và X → Y là một phụ thuộc hàm với ∪ n.
- Nói rằng X → Y ñược suy diễn logic từ F nếu với mỗi khối r xác ñịnh trên R thoả các phụ thuộc hàm trong F thì cũng thoả X → Y .
- Các tính chất của phụ thuộc hàm trên khối.
- r(R) là một khối bất kì, F là tập các phụ.
- thuộc hàm và.
- ta có một số tính chất cơ bản của các phụ thuộc hàm như sau:.
- Khái niệm phụ thuộc hàm trong mô hình dữ liệu khối, một khối r thoả X → Y là ñúng nếu với mọi t 1 , t 2 ∈ r sao cho t 1 (X.
- Điều này trong thực hành tỏ ra quá cứng ngắt bởi có thể phụ thuộc hàm X → Y trong khối dữ liệu R= (id, A 1 , A 2.
- Do ñó việc mở rộng phụ thuộc hàm trong mô hình dữ liệu khối thành phụ thuộc hàm xấp xỉ trong mô hình dữ liệu khối là ñiều tất yếu..
- Nói cách khác là phụ thuộc hàm trong mô hình dữ liệu khối chỉ ñúng trên các tập con của khối r(R), tức là khối r’(R) nhận ñược bằng cách loại bỏ ñi một số rất ít các phần tử trong khối r(R).
- Có thể xem phụ thuộc hàm xấp xỉ trong mô hình dữ liệu khối là mở rộng của phụ thuộc hàm xấp xỉ trong mô hình dữ liệu quan hệ..
- r là một khối trên R.
- Giả sử r thoả phụ thuộc hàm X → Y là ñúng.
- r trở thành quan hệ r(id;A 1, A 2 ,…..A n.
- Phụ thuộc hàm X → Y trở thành phụ thuộc hàm trong mô hình dữ liệu quan hệ..
- Phụ thuộc hàm xấp xỉ trong mô hình dữ liệu quan hệ.
- Định nghĩa 3.2: Cho U là một tập thuộc tính, R(U) là một lược ñồ quan hệ trên U .
- Khi ñó, Y ñược gọi là phụ thuộc hàm xấp xỉ vào X trên lược ñồ R(U) với mức ñộ α ∈ [0,1] và kí hiệu X ≈ α Y , dựa trên số tối thiểu những hàng cần loại bỏ khỏi r ñể phụ thuộc X ≈ α Y thành X → Y ñược xác ñịnh như sau:.
- Định nghĩa 3.3: Cho U là một tập thuộc tính, R(U) là một lược ñồ quan hệ trên U .
- Cho , X Y ⊆ U , Độ ño lỗi của phụ thuộc hàm xấp xỉ X ≈ α Y ñược xác ñịnh như sau:.
- X → Y là phụ thuộc hàm khi và chỉ khi g 3 = 0 Một số tính chất:.
- Tính chất 1: Cho r là một quan hệ trên tập thuộc tính R.
- Một phụ thuộc hàm ñúng trên r cũng là phụ thuộc hàm xấp xỉ loại 2 với mức  tuỳ ý (0 δ  <1) ñúng trên r..
- Tính chất này dễ dàng suy theo ñịnh nghĩa của phụ thuộc hàm xấp xỉ loại 2..
- Tính chất 2: Cho r là một quan hệ trên R.
- Kí hiêu X ≈ δ 1 Y và X ≈ δ 2 Y là 2 phụ thuộc hàm xấp xỉ loại 2 mức 1 δ và mức 2 δ giữa X và Y trên r, khi ñó nếu X ≈ δ 1 Y ñúng trên r thì X ≈ δ 2 Y cũng ñúng trên r..
- Nếu Y ≈ X khi ñó X ≈ δ Y là phụ thuộc hàm xấp xỉ loại 2 với mức δ tuỳ ý ( 0 ≤ <.
- Phụ thuộc hàm xấp xỉ trong mô hình dữ liệu dạng khối.
- Khi ñó, Y ñược gọi là phụ thuộc hàm xấp xỉ và X trên khối R là số hàng nhiều nhất cần phải loại bổ trong tất cả các lát cắt thuộc khối R ñể phụ thuộc hàm X → Y id (trên lát cắt id) và X → Y R trên khối R là ñúng..
- Kí hiệu g 3 ( X → Y ) R là ñộ ño lỗi của phụ thuộc hàm X → Y trên khối R.
- X → Y ) id là phụ thuộc hàm X → Y trên lát cắt id, id ∈ R.
- Khi g 3 = 0 thì tất cả các phụ thuộc hàm xấp xỉ trên lát cắt chính là phụ thuộc hàm (kinh ñiển)..
- Có thể biểu diễn khối dữ liệu trên ở hình 1.
- dưới dạng bảng dữ liệu như sau:.
- Bảng biểu diễn khối dữ liệu ảng 1..
- Xét phụ thuộc hàm xấp xỉ X → Y trên khối R, ta tính ñược g 3 ( X → Y .
- Phụ thuộc hàm X → Y trên lát cắt 1 là ñúng.
- Phụ thuộc hàm X → Y trên lát cắt 2 là ñúng..
- Phụ thuộc hàm X → Y trên lát cắt 3 có ñộ lỗi là 0.34.
- 0.34 Như vậy, ñộ lỗi của phụ thuộc hàm X → Y trên khối R là 0.34.
- Trong báo cáo này, chúng tôi trình bày mô hình dữ liệu dạng khối ñược xem là mở rộng của mô hình dữ liệu quan hệ.
- Trình bày phụ thuộc hàm trong mô hình dữ liệu dạng khối và các tính chất của phụ thuộc hàm trong mô hình dữ liệu quan hệ..
- Với hai tập thuộc tính X và Y thuộc khối R, ñộ ño ñược xây dựng dựa trên việc tính toán các ñộ ño xấp xỉ từ các lát cắt và lấy giá trị lớn nhất của các ñộ ño ñó..
- Một phụ thuộc hàm xấp xỉ trên khối có ñộ ño bằng 0 thì tất cả các phụ thuộc hàm xấp xỉ trên lát cắt chính là phụ thuộc hàm..
- Dựa trên các nghiên cứu về phụ thuộc hàm xấp xỉ trong mô hình dữ liệu dạng khối chúng tôi sẽ nghiên cứu thuật toán khai phá các phụ thuộc hàm xấp xỉ trên khối với ngưỡng phụ thuộc cho trước..
- Nguyễn Xuân Huy (2006), Các phụ thuộc logic trong cơ sở dữ liệu, Nxb Thống kê, Hà Nội..
- Trịnh Đình Thắng (2011), Mô hình dữ liệu dạng khối , Nxb Lao ñộng..
- Vũ Đức Thi (1997), Cơ sở dữ liệu- Kiến thức và thực hành , Nxb Thống kê, Hà Nội..
- Nguyễn Tuệ (2008), Giáo trình cơ sở dữ liệu , Nxb Đại học Quốc gia Hà Nội..
- Trịnh Đình Vinh (2011), Một số phụ thuộc dữ liệu trong cơ sở dữ liệu dạng khối, Luận án Tiến sĩ, Viện Công nghệ Thông tin..
- Lê Tiến Vương (1997), Nhập môn Cơ sở dữ liệu quan hệ , Nxb Khoa học và kĩ thuật, Hà Nội.

Xem thử không khả dụng, vui lòng xem tại trang nguồn
hoặc xem Tóm tắt