Constraint satisfaction in semi-structured data graphs

Abstract

XML data can be modeled as node-labeled graphs and XML queries can be expressed by structural relationships between labeled elements. XML query evaluation has been addressed using mainly database, and in some cases graph search, techniques. We propose an alternative method that models and solves such queries as constraint satisfaction problems (CSPs). We describe common constraint types occurring in XML queries and show how query evaluation can benefit from methods for preprocessing and solving CSPs. We identify an important non-binary constraint that is a common module of XML queries and describe a generalized arc consistency algorithm with low cost that can ensure polynomial query evaluation. Finally, we demonstrate that maintaining the consistency of such non-binary constraints can greatly accelerate search in intractable queries that include referential relationships. © Springer-Verlag Berlin Heidelberg 2004.