Constraint objects. Divesh Srivastava, Raghu Ramakrishnan and Peter Z. Revesz. We describe the Constraint Object Data Model (CODM), which enhances an object-based data model with existential constraints to naturally represent partially specified information. We present the Constraint Object Query Language (COQL), a declarative, rule-based, language that can be used to infer relationships about and monotonically refine information represented in the CODM. COQL has a model-theoretic and a fixpoint semantics based on the notions of constraint entailment and ``proofs in all possible worlds''. We also provide a novel polynomial-time algorithm for quantifier elimination for set-order constraints, a restricted class of set constraints that uses $\in$ and $\subseteq$.