Một số tính chất của lược đồ khối cân bằng trên khối và lát cắt

Bài viết này phát biểu và chứng minh một số tính chất của lược đồ khối cân bằng khi thực hiện các phép toán trên các lược đồ khối và lược đồ lát cắt. Mối quan hệ giữa lược đồ khối cân bằng với giao của các khóa trên các lược đồ khối và lát cắt.
Nội dung trích xuất từ tài liệu:
Một số tính chất của lược đồ khối cân bằng trên khối và lát cắt Kỷ yếu Hội nghị KHCN Quốc gia lần thứ XIV về Nghiên cứu cơ bản và ứng dụng Công nghệ thông tin (FAIR), TP. HCM, ngày 23-24/12/2021 DOI: 10.15625/vap.2021.0083 MỘT SỐ TÍNH CHẤT CỦA LƯỢC ĐỒ KHỐI CÂN BẰNG TRÊN KHỐI VÀ LÁT CẮT Trịnh Đình Thắng1, Đỗ Thị Lan Anh1, Trần Minh Tuyến2, Nguyễn Thị Hà3 1 Đại học Sư phạm Hà Nội 2, 2Đại học Công đoàn, 3Trường Trung học Phổ thông Nguyễn Viết Xuân thangdhsp2@hpu2.edu.vn, dothilananh@hpu2.edu.vn, tuyentm@dhcd.edu.vn, hant.nvx@gmail.com TÓM TẮT: Bài báo này phát biểu và chứng minh một số tính chất của lược đồ khối cân bằng khi thực hiện các phép toán trên các lược đồ khối và lược đồ lát cắt. Mối quan hệ giữa lược đồ khối cân bằng với giao của các khóa trên các lược đồ khối và lát cắt. Khi các khối suy biến thành quan hệ thì các tính chất của lược đồ khối cân bằng lại trở thành các tính chất của lược đồ quan hệ cân bằng. Ngoài ra một số tính chất của mối quan hệ giữa lược đồ khối cân bằng và khóa cũng được phát biểu và chứng minh ở đây. Từ khóa: Lược đồ khối cân bằng, lược đồ lát cắt, khóa của lược đồ khối, lược đồ cân bằng và khóa. I. GIỚI THIỆU Mô hình dữ liệu dạng khối là một mở rộng của mô hình dữ liệu quan hệ. Việc mở rộng sang mô hình dữ liệu dạng khối giúp cho việc biểu diễn dữ liệu động, có cấu trúc phi tuyến và đáp ứng nhu cầu thực tế tốt hơn. Tuy nhiên, việc chuyển từ biểu diễn dữ liệu phẳng sang dạng khối cũng sẽ phức tạp hơn. Để xây dựng một khối dữ liệu tốt trên thực tế thì việc xác định khóa của lược đồ khối là vô cùng quan trọng. Trên khối thì số thuộc tính chỉ số nhiều hơn hẳn so với số thuộc tính của quan hệ nên việc xác định khóa của nó cũng phức tạp hơn. Từ khó khăn này mà việc nghiên cứu để tìm ra cách xác định khóa của khối nhanh hơn, đơn giản hơn là điều cần thiết. Việc nghiên cứu các tính chất của lược đồ khối cân bằng cũng nằm trong hướng nghiên cứu này. Việc chuyển từ lược đồ khối ban đầu sang lược đồ khối cân bằng sẽ giúp xác định khóa của lược đồ khối ban đầu nhanh hơn và dễ hơn vì khi đó số thuộc tính chỉ số đã giảm đi đáng kể. Các nghiên cứu trước đây [1], [5] đã đưa ra khái niệm về lược đồ khối cân bằng và chứng minh một số tính chất cơ bản của khái niệm này. Tuy nhiên, việc nghiên cứu về mối quan hệ giữa tính cân bằng với các phép toán trên lược đồ khối và khóa của khối còn chưa được quan tâm nhiều. Nội dung của bài báo này phát biểu và chứng minh một số kết quả mới về mối quan hệ đó. Các kết quả nghiên cứu về lược đồ khối cân bằng sẽ giúp ích nhiều cho việc xây dựng các khối dữ liệu trên thực tế. II. MÔ HÌNH DỮ LIỆU DẠNG KHỐI A. Khối, lát cắt của khối Định nghĩa II.1 [1] Gọi R = (id; A1, A2,..., An) là một bộ hữu hạn các phần tử, trong đó id là tập chỉ số hữu hạn khác rỗng, Ai (i=1..n) là các thuộc tính. Mỗi thuộc tính Ai (i=1..n) có miền giá trị tương ứng là dom(Ai). Một khối r trên R, kí hiệu r(R) gồm một số hữu hạn phần tử mà mỗi phần tử là một họ các ánh xạ từ tập chỉ số id đến các miền trị của các thuộc tính Ai (i=1..n). Nói một cách khác: t∈ r(R) ⇔ t = { ti : id → dom(Ai)}i=1..n . Ta kí hiệu khối đó là r(R) hoặc r(id; A1, A2,..., An ), đôi khi nếu không sợ nhầm lẫn ta kí hiệu đơn giản là r. Định nghĩa II.2 [1] Cho R = (id; A1, A2,..., An ), r(R) là một khối trên R. Với mỗi x∈ id ta kí hiệu r(Rx) là một khối với Rx = ({x}; A1, A2,..., An ) sao cho: tx∈ r(Rx) ⇔ tx = {tix = ti } i=1..n , t∈ r(R), t = { ti : id → dom(Ai)}i=1..n . x ở đây tax(x) = ti(x) , i =1..n. Khi đó r(Rx) được gọi là một lát cắt trên khối r(R) tại điểm x. B. Phụ thuộc hàm Sau đây, để cho đơn giản ta sử dụng các kí hiệu: x(i) = (x; Ai ) ; id(i) = {x(i) | x ∈ id}. Ta gọi x(i) (x ∈ id, i = 1..n) là các thuộc tính chỉ số của lược đồ khối R = (id; A1,A2,...,An ). 406 MỘT SỐ TÍNH CHẤT CỦA LƯỢC ĐỒ KHỐI CÂN BẰNG TRÊN KHỐI VÀ LÁT CẮT Định nghĩa II.3 [2] n Cho R = (id; A1,A2,...,An ), r(R) là một khối trên R; X, Y ⊆  id ( i ) , X → Y là kí hiệu một phụ thuộc hàm. i =1 Một khối r thoả X → Y nếu ∀ t1, t2 ∈ R sao cho t1(X) = t2(X) thì t1(Y) = t2(Y). Giả sử ta có: f: X → Y ∈ F là một phụ thuộc hàm, khi đó ta kí hiệu: LS(f) = X, RS(f) = Y, ∀ f ∈ F: LS(F) =  LS ( f ) , RS(F) =  RS ( f ). f∈F f∈F Định nghĩa II.4 [2] Cho lược đồ khối α=(R,F), R=(id; A1, A2,..., An), F là tập các phụ thuộc hàm trên R. Khi đó bao đóng của F kí hiệu F+ được xác định như sau: F+ = { X → Y | F ⇒ X → Y } . Nếu X = {x(m)} ⊆ id(m) , Y = {y(k)} ⊆ id(k) thì ta kí hiệu phụ thuộc hàm X → Y đơn giản là x(m) → y(k) . Khối r thoả x(m) → y(k) nếu ∀ t1, t2 ∈ r sao cho t1(x(m)) = t2(x(m)) thì t1(y(k)) = t2(y(k)) . Trong đó: t1(x(m)) = t1(x; Am), t2(x(m)) = t2(x; Am) , t1(y(k)) = t1(y; Ak ), t2(y(k)) = t2(y; Ak ) . C. Bao đóng của tập thuộc tính chỉ số Định nghĩa II.5 [3] n Cho lược đồ khối α=(R,F), R=(id; A1, A2,..., An ), F là tập các phụ thuộc hàm trên R. Với mỗi X ⊆  id (i ) , ta định nghĩa bao đóng của X đối với F kí hiệu X+ như sau: ...