År [3] införde vi en ram för att fråga ut och uppdatera probabilistisk information om oordnade märkta träd, den probabilistiska trädmodellen. Datamodellen är baserad på träd där noder är kommenterade med samband med probabilistiska händelsevariabler. Vi beskrev kortfattat ett genomförande och scenarier för användning. Här utvecklar vi en matematisk grund för denna modell. Vi presenterar framför allt komplexa resultat. Vi identifierar en mycket stor klass av frågor för vilka enkla variationer av fråga och uppdatera algoritmer från [3] beräkna rätt svar. Ett viktigt bidrag är en fullständig komplexitetsanalys av frågor och uppdateringar. Vi uppvisar också ett beslutsförfarande för likvärdighet av probabilistiska träd och bevisar att det är i co-rp. Dessutom studerar vi frågan om att avlägsna mindre sannolika möjliga världar, och frågan om att validera ett probabilistiskt träd mot en DTD. Vi visar att dessa två problem är svåråtkomliga i det mest allmänna fallet.
De gav också en fullständig komplexitetsanalys av frågor och uppdateringar om de "fuzzy träd" i REF.
On the complexity of managing probabilistic XML data
{'venue': "PODS '07", 'journal': None, 'mag_field_of_study': ['Computer Science']}