We investigated the efficient realisation of object data models for the support of knowledge based systems (KBS) in the Swiss National Science Foundation Priority Program project ``Hybride Wissensbank Systeme''. A major part of the investigation was the exploitation of database technologies to provide the support necessary for efficient retrieval and update in large knowledge bases. Because of the large semantic gap between the knowledge representation and the relational structures, it is difficult to utilise data semantics in query optimisation when mapping directly to a relational storage system. We therefore choose a two-level mapping by first mapping to the object data model COCOON and then from COCOON to the relational multiprocessor system ORACLE which is used as the storage system with query and update strategies controlled primarily at the object system level.

In the mapping of COCOON to ORACLE, we employ extensive replication and view materialisation to minimise retrieval costs. For example, a class is represented explicitly as a relation even though it could be specified in terms of a query expression (view) over other classes. Since an object may belong to many classes, an object representation may be replicated in several relations. The penalty associated with such an approach is the increased cost for executing update operations; a single update operation on a specific object may require updates on a large number of relations involved in the representation of that object. To reduce the update time, we employ intra-transaction parallelism by breaking such an operation down into shorter relational operations. These operations are executed as parallel subtransactions of the object level's update operation. In other words, we exploit inter-transaction parallelism on the relational level to achieve intra-transaction parallelism on the object level. The Picture shows such a decomposition and the dependencies between the different relational transactions of an update statement.

Figure: Update dependency graph

To ensure the correctness and recoverability of the operation's execution, we use multi-level transaction management as the parallelisation framework. In addition, we minimise the resulting overhead for the logging of the compensating inverse operation required by the multi-level concept by logging the compensation for nonderived data only. Our performance evaluations show that we can efficiently maintain the replicated data and materialised views in the context of large classification structures.

Figure: Elapsed time of an update

References

Michael Rys, Moira C. Norrie, Hans-Jörg Schek, Intra-Transaction Parallelism in the Mapping of an Object Model to a Relational Multi-Processor System. In: Proc. of the 22nd Internat. Conference VLDB, Mumbai (Bombay), India, September 1996.

M.C. Norrie, U. Reimer, P. Lippuner, M. Rys and H.-J. Schek, Frames, Objects and Relations: Three Semantic Levels for Knowledge Base Systems. In: Workshop on "Reasoning about Structured Objects: Knowledge Representation meets Databases" (KRDB-94), Saarbrücken, Germany, September 1994.

contacts: Prof. H.-J. Schek