Komplexiteten i inneslutning och tillfredsställande konjunktiva frågor över ändliga, orankade, märkta träd studeras med avseende på axlarna Child, NextSibling, deras transitiva och reflexiva stängningar, och följande. För inneslutning problemet presenteras en trikotomi, klassificera problemen som i PTIME, coNP-fullständig, eller Π P 2 -fullständig. För tillfredsställande problem de flesta problem klassificeras som antingen i PTIME eller NP-komplett.
REF studerade inneslutning av konjunktiva frågor över trädstrukturerade data och visade en trikotomi, klassificera problemen som i PTIME, COPP-fullständig, eller Π p 2 -fullständig.
Conjunctive query containment over trees
{'venue': 'In 11th International Symposium on Database Programming Languages (DBPL', 'journal': None, 'mag_field_of_study': ['Mathematics', 'Computer Science']}