Testing the satisfiability of tree pattern queries with node identity constraints

This research deals with testing the satisfiability of a subclass of XQuery and XPath expressions that contain node identity constraints. This subclass of expressions is called Conjunctive XPath. A query is satisfiable if there exists a database of XML documents that will result in a non-empty answer to the query, whereas a query that is not satisfiable will result in an empty answer when run against any database. Determining that a query is unsatisfiable prior to execution will result in savings in computer run-time by not executing unsatisfiable queries. Although the general problem is undecidable, we examine a subclass of queries called Conjunctive XPath where satisfiability is decidable. Previous researchers have presented algorithms for determining satisfiability based on predicate logic and also using non-deterministic finite automata. We present an algorithm for XPath queries with a single node identity constraint, based on topological sorting. This algorithm has faster run-time compared to previously known algorithms.