Paper Info
Title
Conjunctive query containment over trees
Abstract
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, and Following. For the containment problem a trichotomy is presented, classifying the problems as in PTIME, coNP-complete, or �P2 -complete. For the satisfiability problem most problems are classified as either in PTIME or NP-complete.
Year
DOI
Venue
2007
10.1007/978-3-540-75987-4_5
Workshop on Database Programming Languages
Keywords
Field
DocType
satisfiability problem,axes child,conjunctive query containment,reflexive closure,containment problem,conjunctive query,conjunctive queries,satisfiability
Conjunctive query,Programming language,Computer science,P,Boolean satisfiability problem,Satisfiability,Algorithm,Theoretical computer science,Boolean conjunctive query,Transitive relation,Trichotomy (philosophy)
Conference
Volume
Issue
ISSN
77
3
0022-0000
ISBN
Citations 
PageRank 
3-540-75986-7
32
1.29
References 
Authors
12
3
Name
Order
Citations
PageRank
Henrik Björklund131120.41
wim martens260929.78
Thomas Schwentick32373155.10