Vi anser att problemet med förfrågan inneslutning för XML-frågor med häckning. Eftersom två frågor, Q och Q, Q sägs finnas i Q om Q producerar en delmängd av svaren av Q för någon databas instans. Fråga inneslutning är viktigt för frågeoptimering, verifiering av integritet begränsningar, informationsintegration och verifiering av kunskapsbaser. Fråga inneslutning har studerats i relationssammanhang och för XPath frågor, men inte för XML frågor med häckning. Vi börjar med att överväga konjunktiva XML-frågor (c-XQueries), och visa att inneslutning är i PTIME om vi begränsar fanout (antal syskon delblock) att vara 1. Vi visar att för godtycklig fanout, inneslutning är coNP-hård redan för frågor med bodjup 2, även om frågan inte innehåller variabler i returklausulerna. Vi visar sedan att för frågor med fast bodjup, inneslutning är coNP-fullständig. Vi överväger flera tillägg till c-XQueries, inklusive frågor med union, negation och frågor där XPath uttryck kan innehålla nedstigande kanter (förutom jokertecken och förgrening). I vart och ett av dessa fall visar vi att även med fanout 1, fråge inneslutning är coNP-komplett, och fråge inneslutning för frågor med fast bodjup är fortfarande coNP-komplett. Slutligen visar vi att för frågor med likheter på taggvariabler, inneslutning är NP-komplett för frågor med fanout 1 och Π p 2 -komplett för frågor med godtycklig fanout men fast bodjup; för frågor med aritmetiska jämförelser på taggvariabler, inneslutning är Π p 2 -komplett för båda fallen.
Dong m.fl. REF studerar ytterligare de inbäddade XML-frågor och visar för frågor med fast bodjup, inneslutning problemet är coNP-fullständig.
Containment of Nested XML Queries
{'venue': 'VLDB', 'journal': None, 'mag_field_of_study': ['Computer Science']}