[FONT=Times New Roman]Mã hóa các hệ đa cấp kế thừa bội

[FONT=Times New Roman]thay thế cho phép tính lưới

[FONT=Times New Roman]

[FONT=Times New Roman]Tóm tắt:

[FONT=Times New Roman]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

[FONT=Times New Roman]1. Giới thiệu

[FONT=Times New Roman]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

[FONT=Times New Roman]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

[FONT=Times New Roman]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

[FONT=Times New Roman]

[FONT=Times New Roman]Tham khảo

[FONT=Times New Roman] R.G.G. Cattell et al. (Eds.), The Object Data Standard: ODMG 3.0, Morgan Kaufmann, San Francisco, CA, 2000.

[FONT=Times New Roman] 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.

[FONT=Times New Roman] 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.

[FONT=Times New Roman] B. Kolman, R. Busby, S. Ross, Discrete Mathematical Structures, third ed., Prentice Hall, New Jersey, 1996.

[FONT=Times New Roman] G. Markowsky, The representation of posets and lattices by sets, Algebra Universalis 11 (1980) 173–192.

[FONT=Times New Roman] 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.

[FONT=Times New Roman] Y. Caseau, M. Habib, L. Nourine, O. Raynaud, Encoding of multiple inheritance hierarchies and partial orders, Computational Intelligence 15 (1) (1999) 50–62.

[FONT=Times New Roman] 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.

[FONT=Times New Roman] 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.

[FONT=Times New Roman] 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.

[FONT=Times New Roman] 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

[FONT=Times New Roman] 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).

[FONT=Times New Roman] 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.

[FONT=Times New Roman]

[FONT=Times New Roman]

[FONT=Times New Roman]

[FONT=Times New Roman]

[FONT=Times New Roman]