XPath och XQuery (som inkluderar XPath som underspråk) är de viktigaste frågespråken för XML. En viktig fråga som uppstår vid effektiv utvärdering av frågor som uttrycks på dessa språk är tillfredsställande, dvs. om det finns en databas, i enlighet med schemat om man är tillgänglig, där frågan har ett icke-tomma svar. Vår erfarenhet visar att tillfredsställande kontroll kan leda till betydande besparingar i frågeutvärderingen. Vi studerar systematiskt tillfredsställelse av träd mönster frågor (som fångar en användbar fragment av XPath) tillsammans med ytterligare begränsningar, med eller utan ett schema. Vi identifierar fall där detta problem kan lösas i polynom tid och utveckla nya effektiva algoritmer för detta ändamål. Vi visar också att problemet i flera fall är NP-komplett. Vi gjorde en omfattande uppsättning experiment för att verifiera nyttan av tillfredsställande kontroll som en förbehandling steg i frågebehandling. Våra resultat visar att denna kontroll tar en försumbar del av den tid som behövs för att behandla frågan samtidigt som den ofta ger betydande besparingar.
Nyligen, Lakshmanan m.fl. REF har studerat den computational komplexiteten av tillfredsställande i träd mönster frågor, som fångar ett fragment av XPath (och därmed av XQuery).
On testing satisfiability of tree pattern queries
{'venue': 'VLDB', 'journal': None, 'mag_field_of_study': ['Computer Science']}