Various technologies and techniques are disclosed for processing identity constraints in a relational database. Values are extracted from an XML document during a submit operation. References that potentially participate in an identity constraint are identified. The reference information is stored. An identity constraint graph is generated from the stored reference information. Techniques for facilitating key-sequence comparisons are described. Techniques for identifying violations to identity constraints are described. Techniques for identifying which identity constraint graphs are affected by a new or changed document are described.