Search Algorithms for Conceptual Graph Databases

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.


Introduction
Knowledge representation and reasoning has been recognized as a central issue in Artificial Intelligence. Knowledge can be represented symbolically in many ways. One of these ways, called conceptual graph (CG) representation, is graph formalism, that is, knowledge is represented by labelled graphs, and reasoning mechanism is based on graph homomorphism. All kinds of knowledge -ontology, facts, rules and constraints -can be represented by conceptual graphs. In this paper, we consider a database composed of a set of conceptual graphs, representing some assertions about a modelled world. Using conceptual graphs and graph homomorphism a basic queryanswering mechanism can be built based on semantic search. A query made to this base is itself a conceptual graph. An element f of the database is a real answer candidate for query q if and only if there is a homomorphism from q to f. We note that graph homomorphism checking is an NP-Complete problem, that is, homomorphism check is an expensive operation. Therefore the main requirement for conceptual graph database organizing and managing algorithms is to reduce the number of homomorphism checks. Graph homomorphism defines a partial order over conceptual graphs. A finite poset (of CGs) can be considered a database model for a conceptual graph database. Ordering, updating and retrieval are the main operations of organizing and managing of CG databases. All these operations can be represented by the more basic operations: Searching and Finding Parents/Children. In this paper we consider the searching operation only. The problem of searching in partially ordered sets has recently received considerable attention. Motivating this research are practical problems in filesystem synchronization, software testing, information retrieval, and so on. In practical applications, the elements of partially ordered sets can be complicated and comparison of elements may be expensive. In the conceptual graph case, comparison of elements is equivalent to graph homomorphism check. Since graph homomorphism is an NP-Complete problem, CG comparison takes a lot of time and there is no hope to reduce this time. Therefore the efficiency of a search algorithm depends directly on the number of CG comparisons.
The binary search technique is a fundamental method for finding an element in a totally ordered set. As in the totally ordered case, 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. ___________________________________________________________________________ *This research is sponsored in part by the Science Fund Grant 06-03-04-SF0032 from MOSTI, Malaysia

Related Works
Conceptual graphs constitute formalism for knowledge representation. Conceptual graphs were introduced by Sowa [1] as a combination of existential graphs (Peirce, 1909) and semantic networks (Richens, 1956). The first book on conceptual graphs [2] applied them to a wide range of topics in artificial intelligence, computer science, and cognitive science. Since 1991, Conceptual Graphs have been mathematically developed by Chein and Mugnier [3]. One of the main requirements for knowledge representation formalism is to be logically founded, which should have two essential properties with respect to deduction in the target logic: soundness and completeness. For conceptual graphs the equivalent logic is First Order Logic (FOL). The FOL semantic was defined in [2], and the soundness of conceptual graph homomorphism with respect to logical deduction was shown. The first proof of the completeness result, based on the resolution method, is given by Chein and Mugnier [4]. The NP-Completeness of conceptual graph homomorphism checking was proven in [4]. Several algorithms have been proposed for checking conceptual graph homomorphism [5][6][7][8][9]. The simplest case of a partially ordered set is a totally ordered set. The binary search technique is an optimal algorithm for finding an element in a totally ordered set [10]. In [11], Mozes, Onak, and Weimann present a linear-time algorithm that finds the optimal strategy for searching a tree-like partially ordered set. Levinson [12] and Ellis [13] have proposed several modifications of breadth/depth first search technique using some simple properties of partially ordered sets. Dereniowski [14] proves that finding an optimal search strategy for general posets is hard and gives a polynomial-time approximation algorithm with sublogarithmic approximation ratio. In [15], a sorting problem in a partially ordered set is studied.

Partially Ordered Set (Poset) Definition.
A partial order is a binary relation over a set which is reflexive, antisymmetric, and transitive, that is, for all and in , we have that: (i) (reflexivity); (ii) if and then (antisymmetry); (iii) if and then (transitivity). A set with a partial order is called a partially ordered set or poset ( ). For any two elements and of a poset we use if . Also we use ( ) if ( ) and . Let be a poset. If such that , , then is called the top element of (the bottom element ⊥ is dually defined); a poset does not necessarily have a top (bottom) element, but if it has a top (bottom) element then it is unique. Let be a poset and be any non-empty, finite subset of , | | , where is a positive integer. We note that is also a poset. Let be an element of : . The following definitions are useful for future description.
, and for an element of , and respectively.

Representation of Posets
The list of ancestors is dually defined.

Lattice Definition.
A lattice is a partially ordered set in which any two elements have a unique least upper bound (also called the join) and a unique greatest lower bound (also called the meet).
be a finite lattice. An element L j  is join-irreducible if j has exactly one child.

Definitions
A conceptual graph is a labeled bipartite multigraph. One set of nodes is called the set C of concept nodes, and the other set R is called the set of relation nodes. If a concept is the -th argument of a relation then there is an edge between and that is labeled . Concept and relation nodes are labeled by two partially ordered sets. These pair of partially ordered sets is called vocabulary. An edge labeled i between a relation r and a concept c is denoted R , which preserves edges and may decrease concept and relation labels, that is: Let and be two CGs defined over the same vocabulary. We say if there is a homomorphism from to . It is easy to show that the introduced order is transitive and reflexive, but it is not antisymmetric. Definition. Two CGs and are said to be hom-equivalent if and , also denoted . Let G and H be two hom-equivalence classes of CGs defined over the same vocabulary. We say G H if for some G and H . It is clear that it does not matter how and are chosen from G and H, they can be any representatives of respective hom-equivalence classes. We note that the introduced order is a partial order. Let be the set of all hom-equivalence classes of CGs defined over a given vocabulary. Let be a non-empty finite subset of . Without loss of generality, we can consider a set of representatives of elements of Δ. We call it a CG dataset. We note that a CG dataset is also a partially ordered set. Let be any element of , , and let q be any representative of Q, . We call q a query element. A query comparison is a comparison between query element and an element of a dataset. Only query comparison needs to check graph homomorphism, but comparison of two elements of a dataset can be done without graph homomorphism.

Organizing and Managing Operations
There are three main operations: Ordering, Updating and Retrieval. We note that since a CG database is a knowledgebase, the inference operation can be also considered. However we limit ourselves to the first three operations. It is clear that Ordering (generating initial dataset) is consecutively Inserting of query CG into dataset. Updating can be done using Inserting and Deleting of query CG. Retrieval uses only Finding Descendants of query CG. Next representations look like:  Deleting = Searching + something;  Inserting = Finding Parents + Finding Children + something;  Finding Descendants = Finding Children + something. It can be easily checked that the "something" parts of the above representations do not depend on query comparisons and take insignificant time. Finding Parents and Finding Children are dual operations.
Therefore only two operations -Searching and Finding Parents/Children -are enough for manipulating a CG database. We consider only the Searching operation in a poset. The formal definition of the Searching problem can be seen in the input-output part of Algorithm 2.

Searching in Matryoshka-Lattices
There are different classes of posets. We can order poset classes according to how easy they are to search: 1. Totally ordered sets (chains); 2. Tree-like posets; 3. Lattices; 4. General posets. In Figure 1 you can see examples of each class of posets. It is clear that for the searching operation the most amenable class is chains. Existing works show that the next best class is tree-like posets, then lattices, and the worst class is general posets. In the conceptual graph case we usually have lattices or general posets.  , y x  if and only if the binary code of x is less than or equal to the binary code of y. In Figure 3, lattice has six join-irreducible elements. We assigned a binary code of length 6 to each element of the lattice. Habib and Nourine [16] have used binary codes for lattice operations. In the searching problem, if query element has already been compared with join-irreducible elements then it can be compared with other elements using binary code comparisons. For example, a Boolean lattice with elements has join-irreducible elements and this is enough query comparisons; all other comparisons can be done using binary code comparison. Let be a finite lattice. Let be the set of join-irreducible elements of . We consider the set = { ⊥}. The partially ordered set is called the poset generated by join-irreducible elements of . We note that is not necessarily a lattice. In Figure 2 you can see a counterexample. If is a lattice then we can construct a poset generated by the join-irreducible elements of . We can have a sequence of lattices, where is a poset generated by the joinirreducible elements of lattice . We assumed that for all , posets are lattices. If a lattice certifies the just explained property then we call it a matryoshka-lattice. The lattice in Figure 3 is a matryoshka-lattice, but the (left) lattice in Figure 2 is not. It is clear that | | | |. There exists a positive integer such that all elements of the lattice , except the bottom and may be the top elements, are join-irreducible. Let be a first such integer. Then any lattice is the same Tree-like poset Lattice General poset Chain as lattice . Now we have a finite sequence of mutually different lattices . It is clear that { } is a tree-like poset and it has fewer elements than the original lattice L. It is enough to know comparisons between a query element and elements of { }. Therefore we have a more simple search space than in the original one. Using binary codes we can compare a query element with elements of , then with elements of , and so on, finally with elements of . This is the idea of Algorithm 1. Algorithm 1 first constructs the sequence . Then using an efficient search algorithm for a tree, for example the algorithm from [11], a query element is compared with elements of { }. Using binary codes a query element is then compared with elements of the previous lattice, and so on. Finally Algorithm 1 finds comparisons between query element and elements of the original lattice . Algorithm 1 is based on replacement of comparisons of two elements of the lattice with binary code comparisons. We note that comparison of binary codes is insignificant relative to comparison of CGs using graph homomorphism. Algorithm 1: SearchInMat-Lattice(Matryoshka-lattice, query element); Input: Matryoshka-lattice L and query element q; Output: An element of matryoshka-lattice L, which is equal to query element q or "No q in a given matryoshka-lattice L"; 1. 2. ; 3. If has a non-join-irreducible element ( ⊥) then 3.1 Find and numerate all join-irreducible elements of ; 3.2 Assign binary code to each element of ; 3.3 Construct next lattice generated by the join-irreducible elements of ; 3.4 ; Go to 3; 4. Using search algorithm in a tree { } find binary code of query element q; 5. If then else 7; 6. Extend binary code of query element q using binary code comparisons in ; Go to 5; 7. Search for query element q using binary code comparisons in L.
In Figure 3, lattice is generated by the join-irreducible elements of , and lattice is generated by the join-irreducible elements of .
{ } is a tree-like poset. The bold nodes of , , and are join-irreducible elements. A binary code is assigned to each node of and . For any given query element, Algorithm 1 uses only three query comparisons. These are comparisons between a query element and three join-irreducible elements of a tree-like poset { }.

Parallel Search Algorithm
Now we consider a general poset. First we propose a simple sequential search algorithm in a poset, and then using it we suggest a parallel algorithm.

Sequential Search Algorithm
Let be a poset and be any non-empty, finite subset of , | | , where is a positive integer. We call the set as a dataset. We assume that the dataset has both top and bottom elements and that they are different: ⊥. Assume are elements of and and ⊥. Let be an element of : . We call the element a query element. Our search algorithm is based on the following very simple property of posets: Let be elements of some poset. If is FALSE then for any such that , we have that is also FALSE. Figure 3 Algorithm 2 starts from the top element and moves to depth or width for further searching. Algorithm 2 asks a question of the form " ". If the answer is "Yes" then it continues the search in the set of descendants of the selected element (moving to depth). If the answer is "No" then it searches in the complimentary part (moving to width). We note that the ) function returns the -th child of in . Because , the function can be done in constant time since it corresponds to an access to an element of the descendant list D . The Descendant function is a similar. Also we note that the dual algorithm of Algorithm 2 can be easily obtained. It can be used if it is known that the query element is closer to the bottom element.

Parallel Search Algorithm
For parallel computing we use the parallel random-access machine (PRAM) model of computation with processors. In the PRAM model of computation all processors can access common a RAM in a single algorithm-step. In parallel Algorithm 3, the first processor uses Algorithm 2; all other processors use Algorithm 2 with random chosen initial element (step 1.3). Shared information for processors is the Status of an element, which can be ANC (ancestor), NONANC (non-ancestor), and DES (descendant). In Algorithm 3 any query comparison (in steps 1.4, 1.10, and 1.14) will be done once only, that is, two or more processors do not check the same query comparison if they do not come to it at exactly the same time. In other words, there is no overlapping of partition of search space up to query comparisons. The whole algorithm stops when one of the processors returns or the first processor returns "No in ". If the processor , reaches the bottom element, but cannot find a searching element then it chooses a new initial element and searches again. This provides uniform distribution of tasks among the processors.

Conclusions
We analyzed conceptual graph database organizing and managing operations. We proposed a search algorithm for a particular case, when the search space is a special subclass of lattices, so called matryoshka-lattices. In the general case we suggested a parallel search algorithm which is based on simple sequential algorithm. Since the searching in lattices problem is replaced with searching in a tree-like poset with fewer elements than original one we believe that Algorithm 1 is very efficient. However, we do not know how large/small the class of matryoshka-lattices is. There is no easy way to check whether a given lattice is a matryoshka-lattice or not. We remark that the efficiency of Algorithm 3 can be increased by replacing the basic sequential algorithm (Algorithm 2) with a faster one.