Virtually all semantic or object-oriented data models assume objects have an identity separate from any of their parts. These models allow users to define complex object types in which property values may be any other objects. Often the query language allows a user to navigate from object to object by following a property value path. In this paper, we consider the combination of three forms of constraints over complex object types: equations, functional dependencies, and typing constraints. The constraints are novel since component attributes may correspond to property paths instead of single properties. The kind of equational constraint we consider is also important: it abstracts the class of conjunctive queries for query languages that support property value navigation. Our form of typing constraint is novel for two reasons: it allows us to characterize well-formedness conditions on constraints in more appropriate semantic terms, and it can be used to support a form of molecular abstraction.
We present a sound and complete axiomatization for the case in which interpretations are permitted to be infinite, where the generalization taxonomy is a lower semi-lattice, and where the typing constraints apply only to simple paths. An interpretation corresponds to a form of directed labelled graph. Our proof of completeness is constructive in the sense that it yields a set of semi-decision procedures for all three forms of constraints. The procedures become decision procedures when a schema is “acyclic.” However, the implication problem for our form of equational constraint alone, over arbitrary schema, is undecidable. Our summary reviews applications of the theory to problems in object-oriented query optimization.