The present invention relates to a method, and system for implementing the method, for performing incremental validation of an XML document with respect to XML Schema key and keyref constraints, and handling the semantics dictated by the XML Schema specification. Several operations are defined that change the content of a document, i.e., add or remove nodes, or change the value of existing nodes. The present invention verifies whether performing such an operation would violate key or keyref constraints, and allows changing the document only if the operation maintains the validity of the document with respect to the constraints. The verification traverses only the parts of the document that may be affected by the change operation, and not the whole document. The invention maintains, in an efficient manner, data structures that hold information relevant to the validation of key and keyref constraints.