{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2024,2,20]],"date-time":"2024-02-20T21:08:32Z","timestamp":1708463312814},"reference-count":31,"publisher":"Association for Computing Machinery (ACM)","issue":"8","content-domain":{"domain":[],"crossmark-restriction":false},"short-container-title":["Proc. VLDB Endow."],"published-print":{"date-parts":[[2012,4]]},"abstract":"<jats:p>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.<\/jats:p>","DOI":"10.14778\/2212351.2212355","type":"journal-article","created":{"date-parts":[[2014,6,24]],"date-time":"2014-06-24T12:17:57Z","timestamp":1403612277000},"page":"728-739","source":"Crossref","is-referenced-by-count":8,"title":["Adding logical operators to tree pattern queries on graph-structured data"],"prefix":"10.14778","volume":"5","author":[{"given":"Qiang","family":"Zeng","sequence":"first","affiliation":[{"name":"Institute of Computing Technology, Chinese Academy of Sciences, Beijing, China"}],"role":[{"role":"author","vocabulary":"crossref"}]},{"given":"Xiaorui","family":"Jiang","sequence":"additional","affiliation":[{"name":"Institute of Computing Technology, Chinese Academy of Sciences, Beijing, China"}],"role":[{"role":"author","vocabulary":"crossref"}]},{"given":"Hai","family":"Zhuge","sequence":"additional","affiliation":[{"name":"Institute of Computing Technology, Chinese Academy of Sciences, Beijing, China"}],"role":[{"role":"author","vocabulary":"crossref"}]}],"member":"320","published-online":{"date-parts":[[2012,4]]},"reference":[{"key":"e_1_2_1_1_1","unstructured":"Full version. CoRR abs\/1109.4288 2011.  Full version. CoRR abs\/1109.4288 2011."},{"key":"e_1_2_1_2_1","doi-asserted-by":"publisher","DOI":"10.1145\/67544.66950"},{"key":"e_1_2_1_3_1","doi-asserted-by":"publisher","DOI":"10.1145\/375663.375730"},{"key":"e_1_2_1_4_1","doi-asserted-by":"publisher","DOI":"10.1145\/564691.564727"},{"key":"e_1_2_1_5_1","doi-asserted-by":"publisher","DOI":"10.1109\/TKDE.2011.128"},{"key":"e_1_2_1_6_1","doi-asserted-by":"publisher","DOI":"10.1145\/1376616.1376678"},{"key":"e_1_2_1_7_1","volume-title":"VLDB","author":"Chen L.","year":"2005"},{"key":"e_1_2_1_8_1","volume-title":"VLDB","author":"Chen S.","year":"2006"},{"key":"e_1_2_1_9_1","doi-asserted-by":"publisher","DOI":"10.1109\/ICDE.2008.4497498"},{"key":"e_1_2_1_10_1","volume-title":"VLDB","author":"Chen Z.","year":"2003"},{"key":"e_1_2_1_11_1","doi-asserted-by":"publisher","DOI":"10.1109\/TKDE.2010.169"},{"key":"e_1_2_1_12_1","volume-title":"SODA","author":"Cohen E.","year":"2002"},{"key":"e_1_2_1_13_1","doi-asserted-by":"publisher","DOI":"10.14778\/1920841.1920878"},{"key":"e_1_2_1_14_1","doi-asserted-by":"publisher","DOI":"10.1109\/TKDE.2007.1060"},{"key":"e_1_2_1_15_1","doi-asserted-by":"publisher","DOI":"10.1145\/1376616.1376660"},{"key":"e_1_2_1_16_1","doi-asserted-by":"publisher","DOI":"10.1145\/1007568.1007578"},{"key":"e_1_2_1_17_1","doi-asserted-by":"publisher","DOI":"10.1007\/11408079_12"},{"key":"e_1_2_1_18_1","doi-asserted-by":"publisher","DOI":"10.1145\/1929934.1929941"},{"key":"e_1_2_1_19_1","doi-asserted-by":"publisher","DOI":"10.1145\/1559845.1559930"},{"key":"e_1_2_1_20_1","doi-asserted-by":"publisher","DOI":"10.1109\/TKDE.2010.126"},{"key":"e_1_2_1_21_1","volume-title":"VLDB","author":"Lu J.","year":"2005"},{"key":"e_1_2_1_22_1","doi-asserted-by":"publisher","DOI":"10.5555\/977401.978089"},{"key":"e_1_2_1_23_1","doi-asserted-by":"publisher","DOI":"10.1145\/564691.564726"},{"key":"e_1_2_1_24_1","volume-title":"VLDB","author":"Schmidt A.","year":"2002"},{"key":"e_1_2_1_25_1","doi-asserted-by":"publisher","DOI":"10.1109\/ICDE.2008.4497491"},{"key":"e_1_2_1_26_1","doi-asserted-by":"publisher","DOI":"10.1109\/ICDE.2006.53"},{"key":"e_1_2_1_27_1","doi-asserted-by":"publisher","DOI":"10.14778\/1453856.1453909"},{"key":"e_1_2_1_28_1","doi-asserted-by":"publisher","DOI":"10.1145\/872757.872774"},{"key":"e_1_2_1_29_1","doi-asserted-by":"publisher","DOI":"10.1007\/11733836_19"},{"key":"e_1_2_1_30_1","doi-asserted-by":"publisher","DOI":"10.14778\/2180912.2180919"},{"key":"e_1_2_1_31_1","doi-asserted-by":"publisher","DOI":"10.14778\/1687627.1687727"}],"container-title":["Proceedings of the VLDB Endowment"],"original-title":[],"language":"en","link":[{"URL":"https:\/\/dl.acm.org\/doi\/pdf\/10.14778\/2212351.2212355","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2022,12,28]],"date-time":"2022-12-28T09:35:21Z","timestamp":1672220121000},"score":1,"resource":{"primary":{"URL":"https:\/\/dl.acm.org\/doi\/10.14778\/2212351.2212355"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2012,4]]},"references-count":31,"journal-issue":{"issue":"8","published-print":{"date-parts":[[2012,4]]}},"alternative-id":["10.14778\/2212351.2212355"],"URL":"https:\/\/doi.org\/10.14778\/2212351.2212355","relation":{},"ISSN":["2150-8097"],"issn-type":[{"value":"2150-8097","type":"print"}],"subject":[],"published":{"date-parts":[[2012,4]]}}}