Conjunctive query containment over trees
2011 (English)In: Journal of computer and system sciences (Print), ISSN 0022-0000, E-ISSN 1090-2724, Vol. 77, no 3, 450-472 p.Article in journal (Refereed) Published
The complexity of containment and satisfiability of conjunctive queries over finite, unranked, labeled trees is studied with respect to the axes Child, NextSibling, their transitive and reflexive closures, andFollowing. For the containment problem a trichotomy is presented, classifying the problems as in PTIME, coNP-complete, or -complete. For the satisfiability problem most problems are classified as either in PTIME or NP-complete.
Place, publisher, year, edition, pages
2011. Vol. 77, no 3, 450-472 p.
Data management, XML, Query optimization, Logic
IdentifiersURN: urn:nbn:se:umu:diva-40610DOI: 10.1016/j.jcss.2010.04.005OAI: oai:DiVA.org:umu-40610DiVA: diva2:401320