Luận Văn Mã hoá hệ đa cấp đa kế thừa thay cho phép tính lưới dựa trên tài liệu : encoding multiple inheritanc

Mã hóa các hệ đa cấp kế thừa bội​ thay thế cho phép tính lưới​ ​ Tóm tắt:
Sự cập nhật hóa ngày càng lớn đối với những hệ đa cấp kế thừa bội đang trở nên thông dụng với 1 số lượng gia tăng những ứng dụng lâu năm hỗ trợ những đối tượng phức tạp. Việc tính tóan hiệu quả của phép tính lưới kết hợp thấp hơn với lớn nhất (GLB) và cao hơn với nhỏ nhất (LUB), sự kết hợp đó bị chỉ trích. Phương pháp mã hóa chặt chẽ 1 hệ đa cấp bị yêu cầu hỗ trợ các phép tóan. Một phương pháp là lao vào những câu lệnh được đưa ra chuyển thành dãy logic với những từ nhị phân và biểu diễn những phép tóan lưới bằng tóan tử logic. Một cách nhìn tổng quan trong sự tiếp cận được đưa ra và 1 vài phương pháp đã được kiểm chứng và so sánh. Một phương pháp mới được đề nghị , dựa trên việc mã hóa từ trên xuống của Caseau nhưng không có yêu cầu hòan thành lưới, điều này cho phép cập nhật hóa các hệ đa cấp ngày càng lớn bằng cách thêm các node vào lá. Thuật tóan đòi hỏi việc mã hóa đa thức theo không gian và thời gian và ủng hộ hiệu quả những tính tóan lưới trong ứng dụng , nơi mà các lớp của đối tượng được lưu trữ như mã. Những kết quả thử nghiệm đưa ra những ấn tượng sâu sắc, và sự phân tích được cung cấp trên hiệu quả việc chèn có thứ tự trong việc mã hóa
1. Giới thiệu
Các hệ đa cấp kế thừa thì phổ biến trong nhiều lĩnh vực. Những ngôn ngữ lập trình hướng đối tượng như C++, Java và Smalltalk cho phép định nghĩa các lớp mà các lớp được tổ chức thành những hệ đa cấp kế thừa. Những đề nghị dữ liệu gần đây cho phép định nghĩa bằng giản đồ dựa trên những đối tượng phức tạp, và 1 vài đòi hỏi phép tính lưới để suy ra các lọai đối tượng. Mối quan hệ kế thừa cũng xuất hiện trong việc truy vấn dữ liệu, và việc kết hợp này thường xuyên được sử dụng trong việc quản lý các quan niệm. Cuối cùng, những hệ thống đại diện cho tri thức cho phép các khái niệm được tổ chức thành các hệ đa cấp phân lớp, với việc thừa kế là thành phần khóa của thuật tóan lập luận
Những hệ thống cho phép các hệ đa cấp kế thừa tổ chức đối tượng , mà các đối tượng là ví dụ của các lớp trong các kiểu thành phần, điều này có thể được mô hình hóa như là lưới. Thao tác đối tượng thì được vận hành bằng phép tính lưới GLB và LUB, đại diện cho sự kết hợp và sự phân rã của các lọai đối tượng. Một tóan tử khóa trong hệ thống này có thể thực hành kiểm tra thử sự kết hợp, đó là quyết định xem có tồn tại một mối quan hệ kế thừa giữa cặp đối tượng trên lý thuyết hay không. Phần 2 sẽ cung cấp tài liệu cơ bản và định nghĩa cần thiết để hiểu những vấn đề này
Một vài phương pháp đã được đề nghị trong việc mã hóa lưới để ủng hộ phép các phép tính lưới theo thời gian không đổi. Phần này sẽ được nhắc lại ở phần 3, cùng với việc phân tích giới hạn và lợi ích mối quan hệ của chúng. Sự phát triển của các ứng dụng lâu năm tận dụng các hệ đa cấp kế thừa, như là cơ sở tri thức và cơ sở dữ liệu

2. Background
Một hệ đa cấp kế thừa có thể được miêu tả như 1 bộ trật tự cục bộ, poset (P, ≤), mối quan hệ nhị phân ≤ , mối quan hệ phan xạ, phản đối xứng, và transitive. Mối quan hệ a ≤ b ngụ ý hoặc a và b cùng lớp, hoặc a là con trực tiếp của b, hoặc a là con trực tiếp của 1 vài lớp c, và c ≤ b. Hai phần tử a và b của poset P được cho rằng có thể so sánh được nếu a ≤ b hoặc b ≤ a
Xem xét 1 poset (P, ≤), và 1 bộ con A của P. Phần tử bP đđược gọi là ràng buộc ở trên của A nếu a ≤ b đối với tất cả aA. Ngòai ra b được gọi là ràng buộc trên nhỏ nhất (LUB) của A nếu nó cũng là 1 trường hợp của b ≤ a bất cứ khi nào a cũng là ràng buộc trên của A. Ngược lại, phần tử bP đđược gọi là ràng buộc dưới của A nếu b ≤ a đối với tất cả aA, và ràng buộc dưới lớn nhất (GLB) của A nếu nó cũng là trường hợp của a ≤ b bất cứ khi nào a cũng là ràng buộc dưới của A.
Một lattice là 1 poset mà bất cứ mỗi cặp phần tử đều có LUB và GLB. LUB của bộ hai phần tử {a,b} có nghĩa là a b và được gọi là hợp của a và b. Tương tự, GLB của {a,b} có nghĩa là ab và được gọi là giao của a và b. Một semilattice thấp hơn là 1 poset mà bất cứ mỗi cặp phần tử đều có GLB. Một sự thảo luận chi tiết hơn về poset và lattice có thể được tìm thấy những chủ đề chuẩn trong môn tóan riêng biệt ví dụ như [4]
Nói chung, 1 hệ đa cấp kế thừa không có cấu trúc lattice; đó là hợp và giao của mỗi cặp phần tử không thể định nghĩa. Trong những trường hợp như thế, GLB và LUB của 1 bộ phần tử không thể định nghĩa được. Để phân biệt những trường hợp này, các từ GCS và LCS được sử dụng và được định nghĩa như sau.
Trong poset (P, ≤) của 1 hệ đa cấp kế thừa, siêu lớp chung nhỏ nhất (LCS) của subset A của P là bộ nhỏ nhất của các phần tử B như là có sự tồn tại b B điều kiện b ≤ a, đối với mỗi phần tử a là 1 ràng buộc trên của A . Ngược lại, siêu lớp chung lớn nhất (GCS) của subset A của P là bộ nhỏ nhất củ phần tử B như là có sự tồn tại b B điều kiện a ≤ b, đối với mỗi phần tử a là ràng buộc dưới của của A.
Được đưa ra 1 poset (P,), đó là 1 lattice và 1 poset lattice nữa (L, ), đối với GLB và LUB có thể được tính tóan 1 cách hiệu quả, giả định rằng có tồn tại 1 hàm số từ P đến L như thế, đối với 2 phần tử a và b trong P ,
(ab) = (a)(b),
(ab) = (a)(b),
Đó là, là 1 đồng dạng lattice. Ngòai ra, cho rằng có thể đảo ngược; đó là, có tồn tại 1 hàm số -1 từ L đến P như thế, đối với bất kỳ a trong P ,-1((a)) = a.Sau đó, một cách tính tóan GLB và LUB của 2 phần tử a và b trong P là nối những mệnh đề bằng nhau, đưa ra
ab = -1((a) (b)),
ab = -1((a) (b)).
Đối với poset (P, ≤) đó không phải là 1 lattice, nó vẫn có thể sử dụng sự gắn vào lattice, nhưng đối với các phép tính phức tạp hơn nữa. Trước tiên, các phép tóan trần và sàn phải được định nghĩa.
Đối với subset A của P , trần của A được kí hiệu là subset B nhỏ nhất của A điều kiện tất cả a A, ở đó tồn tại a bB , khi a ≤ b. Sàn của A được kí hiệu là subset C nhỏ nhất của A điều kiện tất cả a A, ở đó tồn tại a cB , khi c ≤ a.
Bây giờ đối với định nghĩa phép tóan GCS và LCS. Đối với 1 poset (P, ≤) và 1 subset A = {a1, ,ak}của P , GCS có thể được tính tóan như sau:
GCS(A) =
Cách khác, GCS là phần tử lớn nhất của poset mà mã của nó ít hơn mã của GLB của phần tử tương ứng trong semilattice gắn vào. Tương tự, LCS cũng được tính tóan như sau:
LCS(A) =
2.1 Vấn đề
Xem xét poset (P, ≤). Để Anc(x) = { y P |y < x} và Desc(x) = { y P |y > x}. Một phần tử jX được nói là giao không thể tối giản nếu tồn tại xX chẳng hạn xDesc(j) và Anc(j) Anc(x) {x}. Tương tự, chúng ta có thể xác định hội không thể tối giản. Để J(P) biểu hiện rõ những phần của tất cả các yếu tố giao không thể tối giản và M(P) biểu hiện rõ những phần tất cả các yếu tố hợp không thể tối giản được. Markowsky [5] chỉ ra rằng mã hóa tối ưu chỉ dành cho những tóan tử giao (hội) đối với một lưới là những cái đó đạt được bằng liên kết số hay bit khác nhau đến mỗi yếu tố giao không thể tối giản (hội không thể tối giản)
Để (P, ≤) là một poset, và . Habib et al. [6] cung cấp những định nghĩa sau. Một mã hóa đơn giản là sự sắp xếp S với như là là một kết hợp từ P lên trên 2S ; đó là, x py iff . Sau đó vấn đề là quyết định sự thỏa thuận tốt nhất như là mã hóa. Thật không may mắn, Caseau et al. [7] chứng tỏ rằng mã hóa đơn giản là cân bằng đa thức đến vẽ đồ thị màu và lần lượt, nó là một vấn đề NP-hard. Thật vậy, vấn đề mã hóa thường (cũng được biết như vấn đề hai chiều) thì tìm thấy số k nhỏ nhất như là tồn tại một sự sắp xếp {1, ,k} như S với là một kết hợp từ P lên trên 2S ; đó là, x py iff . Rõ ràng, đây cũng là một vấn đề NP-hard.
3. Những phương pháp trước đây
Một số phương pháp đã được đề nghị để giải quyết phép tóan trên poset và lattice. Thật là không may mắn, mỗi phép tóan có giới hạn hoặc không hiệu quả hoặc kích thước hoặc giải quyết hệ đa cấp năng động và phép tóan lattice
3.1 Transitive closure
Một phương pháp thường để lưu trữ 1 poset bao gồm ma trận transitive closure của nó. Để cho x1, x2, ,xn là phần tử của poset. Một ma trận transitive closure là một ma trận n x n của 0 và 1, mà phần tử thứ (i, j) của ma trận là 1 iff xi là cha của xj . Một ma trận liền kề đối xứng A1 được định nghĩa là hợp của ma trận liền kề A và ma trận định dạng n x n I­nxn nơi mà phần tử thứ ( i, j) của ma trận liền kề là 1 iff xi là cha của xj . Ma trận transitive closure có thể đạt được bởi sự tuần tự của phép tóan ma trận được chỉ ra bởi
A0 = I­nxn ,
A1 = A x A0 ,
Ak = Ak-1 x Ak-1 ,
cho đến khi Ak = Ak-1 = A* . Sự tính tóan này hội tụ hầu hết tại phép nhân của ma trận logic n x n
Phương pháp này đòi hỏi O(n2) bit để lưu trữ. Để tìm GLB hoặc LUB của 2 phần tử, thì cần O(n) phép tóan trên vectơ n bit, đúng với nỗ lực cần để tìm thấy phần tử nhỏ nhất của bộ [8]. Những người trong Ait-Kaci [9] đưa ra thuật tóan pidgin-code để để chỉ định những mã trancitive closure đến phần tử của hệ đa cấp bắt đầu phần tử ở bên dưới và tiến hành theo hướng đi lên từng lớp từng lớp một. Mỗi nút là 1 mã nhị phân hoặc mã con của nó và 2p với p là số nút viếng thăm trong phạm vi.
Hai mẫu giải mã transitive closure được biểu diễn ở hình 1, bên dưới cột được đặt tên là “transitive”. Giải mã ở phía trên sử dụng tối thiểu 7 bit trên 1 mã là đối với 7 phần tử đầu tiên của hệ đa cấp (a-g), hình thành 1 cấu trúc cây. Giải mã ở phía dưới đối với tất cả 15 phần tử của hệ đa cấp (ngọai trừ nút q , là 1 nút ảo thay thế cho giao của nút e và f cho giải mã sau này). Việc giải mã này đòi hỏi tối thiểu chiều dài của mã là 15 bit, hoặc tổng chiều dài là 120 bit nếu không chú ý đến những số 0 ở đầu.



Tham khảo
[1] R.G.G. Cattell et al. (Eds.), The Object Data Standard: ODMG 3.0, Morgan Kaufmann, San Francisco, CA, 2000.
[2] I.F. Cruz, A.O. Mendelzon, P.T. Wood, A graphical query language supporting recursion, in: Proceedings of the ACM SIGMOD International Conference on Management of Data, 1987, pp. 323–330.
[3] A. Borgida, R.J. Brachman, D.L. McGuinness, L.A. Resnick, Classic: a structural data model for objects, in: Proceedings of the ACM SIGMOD International Conference on Management of Data, 1989, pp. 58–67.
[4] B. Kolman, R. Busby, S. Ross, Discrete Mathematical Structures, third ed., Prentice Hall, New Jersey, 1996.
[5] G. Markowsky, The representation of posets and lattices by sets, Algebra Universalis 11 (1980) 173–192.
[6] M. Habib, L. Nourine, O. Raynaud, A new lattice-based heuristic for taxonomy encoding, in: International KRUSE Symposium on Knowledge Retrival, Use and Storage for Efficiency, 1997, pp. 60–71.
[7] Y. Caseau, M. Habib, L. Nourine, O. Raynaud, Encoding of multiple inheritance hierarchies and partial orders, Computational Intelligence 15 (1) (1999) 50–62.
[8] D. Ganguly, C. Mohan, S. Ranka, A space-and-time efficient coding algorithm for lattice computations, IEEE Transactions on Knowledge and Data Engineering 6 (5) (1994) 819–829.
[9] H. Ait-Kaci, R. Boyer, P. Lincoln, R. Nasr, Efficient implementation of lattice operations, ACM Transactions on Programming Languages and Systems 11 (1) (1989) 115–146.
[10] Y. Caseau, Efficient handling of multiple inheritance hierarchies, in: Proceedings of the International Conference on Object-Oriented Systems, Languages, and Applications, 1993, pp. 271–287.
[11] R. Agrawal, A. Borgida, J.V. Jagadish, Efficient management of transitive relationships in large data and knowledge bases, in: Proceedings of the ACM SIGMOD International Conference on the Management of Data, 1989, pp. 253–262. M.F. van Bommel, P. Wang / Data & Knowledge Engineering 50 (2004) 175–194
[12] M.F. van Bommel, T.J. Beck, Incremental encoding of multiple inheritance hierarchies supporting lattice operations, Linkoping Electronic Articles in Computer and Information Science 5(1).
[13] Y. Caseau, An object-oriented deductive language, Annals of Mathematics and Artificial Intelligence 3 (2) (1991) 211–258. Martin van Bommel is an Associate Professor in the Department of Mathematics, Statistics and Computer Science, St. Francis Xavier University. He received his B.Sc. degree from St. Francis Xavier University; and received his Masters of Mathematics and Ph.D. degrees in Computer Science in 1990 and 1996, respectively, from the University of Waterloo. His research interests include object-oriented database design, schema management, query optimization, and complex object database constraints. He has published in the following topics: database design, database constraints, document indexing, and information science. He is a member of the Association for Computing Machinery and the ACM Special Interest Group on the Management of Data. Ping Wang is an Associate Professor in the Department of Mathematics, Statistics and Computer science, St. Francis Xavier University. He received his B.Sc. degree from Beijing Normal University, P.R. China, in 1989; and received his M.Sc. and Ph.D. in Mathematics in 1989 and 1993, respectively, from the University of Regina, Saskatchewan, Canada. His research interests include graph theory and algorithms. He has published in the following topics: construct cages, total graph coloring, simulated annealing, and genetic algorithms.