Paper Info
Title
Between tree patterns and conjunctive queries: is there tractability beyond acyclicity?
Abstract
In static analysis of queries over trees in the presence of schemas, there is an exponential complexity gap between conjunctive queries (CQs, positive existential first-order formulae without disjunction) and tree patterns (tree-like acyclic CQs). Motivated by applications in XML data management, we consider various restrictions of CQs that bring their complexity down to that of tree patterns. Most importantly, we show that vertical tree patterns can be costlessly extended with full horizontal CQs over children. We also consider restricted classes of schemas and show that under disjunction-free schemas the complexity of static analysis sometimes drops dramatically.
Year
DOI
Venue
2012
10.1007/978-3-642-32589-2_61
MFCS
Keywords
Field
DocType
disjunction-free schema,conjunctive query,tree-like acyclic cqs,xml data management,static analysis,exponential complexity gap,full horizontal cqs,positive existential first-order formula,vertical tree pattern,tree pattern
Discrete mathematics,Conjunctive query,Combinatorics,Computer science,Xml data,Static analysis,Theoretical computer science,Exponential complexity,Tree automaton,Schema (psychology),Tree pattern
Conference
Volume
ISSN
Citations 
7464
0302-9743
2
PageRank 
References 
Authors
0.38
24
3
Name
Order
Citations
PageRank
Filip Murlak118419.14
Michał Ogiński220.38
Marcin Przybyłko320.38