Y.: XKvalidator: a constraint validator for XML

The role of XML in data exchange is evolving from one of merely conveying the structure of data to one that also con-veys its semantics. In particular, several proposals for key and foreign key constraints have recently appeared, and as-pects of these proposals have been adopted within XMLSchema. In this paper, we examine the problem of checking keys and foreign keys in XML documents using a validator based on SAX. The algorithm relies on an indexing technique based on the paths found in key denitions, and can be used for checking the correctness of an entire document (bulk check-ing) as well as for checking updates as they are made to the document (incremental checking). The asymptotic perfor-mance of the algorithm is linear in the size of the document or update. Furthermore, experimental results demonstrate reasonable performance