Adding Logical Operators to Tree Pattern Queries onGraph-Structured Data

Qiang Zeng, Xiaorui Jiang, Hai Zhuge

Research output: Chapter in Book/Report/Conference proceedingChapterpeer-review

Abstract

As data are increasingly modeled as graphs for expressing com-plex relationships, the tree pattern query on graph-structured databecomes 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 operatorsto 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 struc-tural constraints. (2) We make a thorough study of fundamentalproblems including satisfiability, containment and minimization,and analyze the computational complexity and the decision pro-cedures of these problems. (3) We propose a compact graph repre-sentation of intermediate results and a pruning approach to reducethe size of intermediate results and the number of join operations –two factors that often impair the efficiency of traditional algorithmsfor evaluating tree pattern queries. (4) We present an efficient algo-rithm for evaluating GTPQs using 3-hop as the underlying reach-ability index. (5) Experiments on both real-life and synthetic datasets 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 treepattern queries with only conjunctive operations.
Original languageEnglish
Title of host publicationProceedings of the VLDB Endowment
EditorsZ. M. Ozsoyoglu
PublisherVLDB Endowment Inc.
Pages728-739
Volume5
Edition8
ISBN (Electronic)9781622767588
Publication statusPublished - Aug 2012
Event38th International Conference on Very Large Data Bases - Istanbul, Turkey
Duration: 27 Aug 201231 Aug 2012
Conference number: 38

Conference

Conference38th International Conference on Very Large Data Bases
Abbreviated titleVLDB
CountryTurkey
CityIstanbul
Period27/08/1231/08/12

Fingerprint Dive into the research topics of 'Adding Logical Operators to Tree Pattern Queries onGraph-Structured Data'. Together they form a unique fingerprint.

Cite this