Incremental encoding of multiple inheritance hierarchies

ABSTRACT

Incremental updates to multiple inheritance hierarchies are becoming more prevalent with the increasing number of persistent applications supporting complex objects, making the efficient computation of lattice operations such as greatest lower bound (GLB), least upper bound (LUB), and subsumption more and more important. General techniques for the compact encoding of a hierarchy are presented. One such method is to plunge the given ordering into a boolean lattice of binary words, leading to an almost constant-time complexity of the lattice operations. The method is based on an inverted version of the encoding of Ait-Kaci et al. to allow incremental update. Simple grouping is used to reduce the code space while keeping the lattice operations efficient. Comparisons are made to an incremental version of the range compression scheme of Agrawal et al., where each class is assigned an interval, and relationships are based on containment in the interval. The result is two encoding methods which have their relative merits. The former being better for smaller, more structured hierarchies, and the latter for larger, less organized hierarchies.

REFERENCES

• 1: R. Agrawal , A. Borgida , H. V. Jagadish, Efficient management of transitive relationships in large data and knowledge bases, Proceedings of the 1989 ACM SIGMOD international conference on Management of data, p.253-262, June 1989, Portland, Oregon, United States
• 2: Hassan Aït-Kaci , Robert Boyer , Patrick Lincoln , Roger Nasr, Efficient implementation of lattice operations, ACM Transactions on Programming Languages and Systems (TOPLAS), v.11 n.1, p.115-146, Jan. 1989 [doi>10.1145/59287.59293]
• 3: CASEAU, Y. An object-oriented deductive language. Annals of Mathematics and Artificial Intelligence 3, 2 (March 1991).
• 4: Yves Caseau, Efficient handling of multiple inheritance hierarchies, Proceedings of the eighth annual conference on Object-oriented programming systems, languages, and applications, p.271-287, September 26-October 01, 1993, Washington, D.C., United States
• 5: Andrew Fall, Sparse Term Encoding for Dynamic Taxonomies, Proceedings of the 4th International Conference on Conceptual Structures: Knowledge Representation as Interlingua, p.277-292, August 19-22, 1996
• 6: D. D. Ganguly , C. K. Mohan , S. Ranka, A Space-and-Time-Efficient Coding Algorithm for Lattice Computations, IEEE Transactions on Knowledge and Data Engineering, v.6 n.5, p.819-829, October 1994 [doi>10.1109/69.317709]
• 7: Matin Francis Van Bommel , Grant Weddell, Path constraints for graph-based data models, 1996

INDEX TERMS

Primary Classification:
  G. Mathematics of Computing
  G.2 DISCRETE MATHEMATICS

Additional Classification:
  H. Information Systems
  H.2 DATABASE MANAGEMENT

  I. Computing Methodologies
  I.6 SIMULATION AND MODELING

General Terms:
Design, Experimentation, Management, Measurement, Performance, Theory