Vi studerar komplexiteten och uttryckskraften hos konjunktiva frågor över orankade märkta träd, där trädstrukturerna representeras med hjälp av "axelrelationer" såsom "barn", "decendent", och "följa" (vi anser en superuppsättning av XPath axlarna) samt unary relationer för nod etiketter. (Cyclic) Konjunktiva frågor om träd förekommer i ett brett spektrum av datahanteringsscenarier relaterade till XML, webben och beräkningslingvistik. Vi etablerar en ram för att karakterisera strukturer som representerar träd för vilka konjunktiva frågor kan utvärderas effektivt. Sedan kartlägger vi helt den dragbarhet gräns för problemet för våra axelrelationer, dvs. vi hittar alla delmängdmaximal uppsättningar av axlar för vilka frågebedömning är i polynom tid. Alla polynom-tid resultat erhålls omedelbart med hjälp av bevistekniker från vårt ramverk. Slutligen studerar vi det uttrycksfulla i konjunktiva frågor över träd och jämför det med den uttrycksfulla kraften hos fragment av XPath. Vi visar att för varje konjunktiv fråga, det finns en likvärdig acyklisk positiv fråga (d.v.s. en uppsättning acykliska konjunktiva frågor), men att i allmänhet denna fråga inte är av polynom storlek.
Liknande resultat, uttryckt i konjunktiva frågor erhålls i REF.
Conjunctive queries over trees
{'venue': "PODS '04", 'journal': None, 'mag_field_of_study': ['Computer Science']}