Xkvalidator: A constraint validator for XML

Yi Chen, Susan B. Davidson, Yifeng Zheng

Research output: Chapter in Book/Report/Conference proceedingConference contribution

24 Scopus citations


The role of XML in data exchange is evolving from one of merely conveying the structure of data to one that also conveys its semantics. In particular, several proposals for key and foreign key constraints have recently appeared, and aspects 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 definitions, and can be used for checking the correctness of an entire document (bulk checking) as well as for checking updates as they are made to the document (incremental checking). The asymptotic performance of the algorithm is linear in the size of the document or update. Furthermore, experimental results demonstrate reasonable performance.

Original languageEnglish (US)
Title of host publicationInternational Conference on Information and Knowledge Management, Proceedings
EditorsK Kalpakis, N Goharian, D Grossman
Number of pages7
StatePublished - Dec 1 2002
Externally publishedYes
EventProceedings of the Eleventh International Conference on Information and Knowledge Management (CIKM 2002) - McLean, VA, United States
Duration: Nov 4 2002Nov 9 2002


OtherProceedings of the Eleventh International Conference on Information and Knowledge Management (CIKM 2002)
Country/TerritoryUnited States
CityMcLean, VA

All Science Journal Classification (ASJC) codes

  • General Decision Sciences
  • General Business, Management and Accounting


Dive into the research topics of 'Xkvalidator: A constraint validator for XML'. Together they form a unique fingerprint.

Cite this