Abstrakt. Vi studerar tillfredsställande problem för XPath fragment som stöder följande-sibling och föregående-sibling axlar. Även om detta problem nyligen undersöktes för XPath-fragment utan syskonyxor, är föga känt om hur syskonaxlarna påverkar tillfredsställelseanalysen. I detta syfte ser vi över tillfredsställelseproblemet för en mängd XPath-fragment med syskonaxlar, i närvaro av DTD:er, i avsaknad av DTD:er, och under olika begränsade DTD:er. I dessa inställningar etablerar vi komplexa gränser som sträcker sig från NLOGSPACE till obeslutbara. Vår huvudsakliga slutsats är att förekomsten av syskonaxlar i många fall komplicerar tillfredsställelseanalysen. Vi visar faktiskt att det finns XPath tillfredsställande problem som finns i PTIME och PSPACE i avsaknad av syskon axlar, men som blir NP-hård respektive EXPTIME-hård, respektive när syskon axlar används i stället för motsvarande vertikala villkor (t.ex. jokertecken och nedstigande axel).
I REF behandlas flera fragment med horisontella axlar.
Satisfiability of XPath queries with sibling axes
{'venue': 'In DBPL’05', 'journal': None, 'mag_field_of_study': ['Mathematics', 'Computer Science']}