Search Algorithms for Conceptual Graph Databases

arXiv1207.2837MaRDI QIDQ6234319FDOQ6234319

Publication date: 11 July 2012

Abstract: We consider a database composed of a set of conceptual graphs. Using conceptual graphs and graph homomorphism it is possible to build a basic query-answering mechanism based on semantic search. Graph homomorphism defines a partial order over conceptual graphs. Since graph homomorphism checking is an NP-Complete problem, the main requirement for database organizing and managing algorithms is to reduce the number of homomorphism checks. Searching is a basic operation for database manipulating problems. We consider the problem of searching for an element in a partially ordered set. The goal is to minimize the number of queries required to find a target element in the worst case. First we analyse conceptual graph database operations. Then we propose a new algorithm for a subclass of lattices. Finally, we suggest a parallel search algorithm for a general poset. Keywords. Conceptual Graph, Graph Homomorphism, Partial Order, Lattice, Search, Database.

This page was built for publication: Search Algorithms for Conceptual Graph Databases

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q6234319)