Motiverad av resonemangsuppgifter i samband med XML-språk undersöks det tillfredsställande problemet med logik på dataträd. Noderna i ett dataträd har en etikett från en ändlig uppsättning och ett datavärde från en möjligen oändlig uppsättning. Det visas att tillfredsställandet av tvåvariabel första ordningens logik är avgörande om trädstrukturen endast kan nås genom barnet och nästa syskonpredikat och tillgången till datavärden begränsas till jämlikhetstester. Av detta huvudsakliga resultat kan man fastställa tillfredsställande och inneslutning för ett datamedvetet fragment av XPath och av implikationsproblemet för unary nyckel- och integrationsbegränsningar.
Första ordningens logik med två variabler och datajämlikhetstester undersöks i REF.
Two-variable logic on data trees and XML reasoning
{'venue': "PODS '06", 'journal': None, 'mag_field_of_study': ['Computer Science']}