On the Complexity of Verifying Consistency of XML Specifications

DOI10.1137/050646895zbMath1186.68156OpenAlexW2111789076WikidataQ57495496 ScholiaQ57495496MaRDI QIDQ3631894

Marcelo Arenas, Wenfei Fan, Leonid O. Libkin

Publication date: 22 June 2009

Published in: SIAM Journal on Computing (Search for Journal in Brave)

Full work available at URL: http://hdl.handle.net/10533/142671

zbMATH Keywords

XMLcomplexityconsistencydocument type definitionkeys and foreign keys

Mathematics Subject Classification ID

Analysis of algorithms and problem complexity (68Q25) Database theory (68P15) Specification and verification (program logics, model checking, etc.) (68Q60) Decidability of theories and sets of sentences (03B25)

Related Items (12)

On the data complexity of consistent query answering over graph databases ⋮ Reasoning about integrity constraints for tree-structured data ⋮ Propagating XML constraints to relations ⋮ Dependency-preserving normalization of relational and XML data ⋮ Reasoning about functional and full hierarchical dependencies over partial relations ⋮ XML normalization based on entity segments ⋮ Extending two-variable logic on data trees with order on data values and its automata ⋮ Consistencies of fuzzy spatiotemporal data in XML documents ⋮ Preserving key in XML data transformation ⋮ Reasoning about XML constraints based on XML-to-relational mappings ⋮ On the Notion of an XML Key ⋮ Unnamed Item

This page was built for publication: On the Complexity of Verifying Consistency of XML Specifications