Filtering unsatisfiable XPath queries

Jinghua Groppe, Sven Groppe*

*Corresponding author for this work
11 Citations (Scopus)


The satisfiability test checks, whether or not the evaluation of a query returns the empty set for any input document, and can be used in query optimization for avoiding the submission and the computation of unsatisfiable queries. Thus, applying the satisfiability test before executing a query can save processing time and query costs. We focus on the satisfiability problem for queries formulated in the XML query language XPath, and propose a schema-based approach to the satisfiability test of XPath queries, which checks whether or not an XPath query conforms to the constraints in a given schema. If an XPath query does not conform to the constraints given in the schema, the evaluation of the query will return an empty result for any valid XML document. Thus, the XPath query is unsatisfiable. We present a complexity analysis of our approach, which proves that our approach is efficient for typical cases. We present an experimental analysis of our developed prototype, which shows the optimization potential of avoiding the evaluation of unsatisfiable queries.

Original languageEnglish
JournalData and Knowledge Engineering
Issue number1
Pages (from-to)134-169
Number of pages36
Publication statusPublished - 01.01.2008

Research Areas and Centers

  • Research Area: Intelligent Systems
  • Centers: Center for Artificial Intelligence Luebeck (ZKIL)

DFG Research Classification Scheme

  • 409-06 Information Systems, Process and Knowledge Management
  • 409-04 Operating, Communication, Database and Distributed Systems


Dive into the research topics of 'Filtering unsatisfiable XPath queries'. Together they form a unique fingerprint.

Cite this