Adding Logical Operators to Tree Pattern Queries on Graph Structured Data
As data are increasingly modeled as graphs for expressing complex relationships, the tree pattern query on graph-structured data becomes an important type of queries in real-world applications. Most practical query languages, such as XQuery and SPARQL, support logical expressions using logical-AND/OR/NOT operators to define structural constraints of tree patterns. In this paper, the authors propose Generalized Tree Pattern Queries (GTPQs) over graph-structured data, which fully support propositional logic of structural constraints. They make a thorough study of fundamental problems including satisfiability, containment and minimization, and analyze the computational complexity and the decision procedures of these problems.