Technique for Transformation of DL Knowledge Base to Boolean Representation

Abstract

Knowledge Cartography (KC) allows for fast answering of Description Logic (DL) knowledge base queries, but requires expensive preprocessing to represent knowledge in internal representation, i.e., the algorithm for computation of map of concepts as binary signatures is exponential time (however, for taxonomies—as many practical cases have shown—it is at most quadratic time). Preprocessing is already part of DL reasoning process and some computations are pre-calculated before user issues query to knowledge base. Using another method—Tableaux, no knowledge preprocessing is performed, however, all reasoning is done after user issues query. That’s why KC is faster than Tableaux during query answering. The chapter focuses on preprocessing issue for KC. It mainly considers the research on efficient generation of binary signatures and signatures rebuilding by employing the methods for logic synthesis. It has been confirmed that logic synthesis Complement algorithm is efficient when applied to the construction of the map of concepts. The research has shown that strategy of construction should be adjusted depending on ontology size. For smaller ontologies—the non-recursive approach should be used, on the contrary—for larger ontologies—recursive approach with bi-partitioning of the ontology graph. The recursive procedure indicated good scaling for large taxonomies. Another observation was that Complement algorithm works faster for non-sorted CNFs.