Adding Logical Operators to Tree Pattern Queries on Graph-Structured Data

Details Adding Logical Operators to Tree Pattern Queries on Graph-Structured Data Adding Logical Operators to Tree Pattern Queries on Graph-Structured Data

2011-09-20

arxiv.org/abs/1109.4288v4

Computer Science

Databases

16 pages

Scientific paper

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, (1) we propose generalized tree pattern queries (GTPQs) over graph-structured data, which fully support propositional logic of structural constraints. (2) We make a thorough study of fundamental problems including satisfiability, containment and minimization, and analyze the computational complexity and the decision procedures of these problems. (3) We propose a compact graph representation of intermediate results and a pruning approach to reduce the size of intermediate results and the number of join operations -- two factors that often impair the efficiency of traditional algorithms for evaluating tree pattern queries. (4) We present an efficient algorithm for evaluating GTPQs using 3-hop as the underlying reachability index. (5) Experiments on both real-life and synthetic data sets demonstrate the effectiveness and efficiency of our algorithm, from several times to orders of magnitude faster than state-of-the-art algorithms in terms of evaluation time, even for traditional tree pattern queries with only conjunctive operations.

Affiliated with

Also associated with

No associations

Rating

Adding Logical Operators to Tree Pattern Queries on Graph-Structured Data does not yet have a rating. At this time, there are no reviews or comments for this scientific paper.

If you have personal experience with Adding Logical Operators to Tree Pattern Queries on Graph-Structured Data, we encourage you to share that experience with our LandOfFree.com community. Your opinion is very important and Adding Logical Operators to Tree Pattern Queries on Graph-Structured Data will most certainly appreciate the feedback.

Rate now

Comments { 0 }

Profile ID: LFWR-SCP-O-147169