Universal Marker and Functional Relation: Semantics and Operations

The universal marker (i.e., universal quantifier) and the functional relation are two useful notations that make Conceptual Graph (CG) representations more concise in expressing universally quantified facts and functional dependencies, which are commonly used in knowledge bases, logic programs and data conceptual schemas. We introduce an expansion rule that formally defines the semantics of CGs containing universal markers and/or functional relations. On the basis of this formal semantics, we define two reasoning operations that are performed directly on CGs with these two notations to make them more useful. One operation is the universal CG projection defining the subsump tion relation on the extended CGs. The other operation is the universal concept join performing universal instantiations and inheritances simultaneously in one graph operation. Both the operations are proved to be sound with respect to their described interpretations.