On the Complexity of Verifying Consistency of XML Specifications

DOI10.1137/050646895MaRDI QIDQ3631894zbMATH OpenOpenAlexWikidataFDO

Authors Marcelo Arenas, Wenfei Fan, Leonid 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

complexityconsistencydocument type definitionkeys and foreign keysXML

Mathematics Subject Classification ID

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

Recommendations

• Satisfiability of Constraint Specifications on XML Documents
• On the complexity of typechecking top-down XML transformations
• Inconsistency Tolerance
• Modulo constraints and the complexity of typechecking XML views
• On XML integrity constraints in the presence of DTDs
• Frontiers of tractability for typechecking simple XML transformations
• Paraconsistent reasoning based on XML

Cited in

(22)

• Preserving key in XML data transformation
• Integrity constraints for XML
• Reasoning about integrity constraints for tree-structured data
• Consistencies of fuzzy spatiotemporal data in XML documents
• Reasoning about XML constraints based on XML-to-relational mappings
• On the data complexity of consistent query answering over graph databases
• Reasoning about functional and full hierarchical dependencies over partial relations
• Testing XML constraint satisfiability
• Satisfiability of Constraint Specifications on XML Documents
• On XML integrity constraints in the presence of DTDs
• scientific article; zbMATH DE number 1945841 (Why is no real title available?)
• scientific article; zbMATH DE number 1951121 (Why is no real title available?)
• XML normalization based on entity segments
• scientific article; zbMATH DE number 7407777 (Why is no real title available?)
• Extending two-variable logic on data trees with order on data values and its automata
• Inconsistency Tolerance
• On the Notion of an XML Key
• Data graphs with incomplete information (and a way to complete them)
• Corrections to: ``On the data complexity of consistent query answering over graph databases
• On the complexity of convex and reverse convex prequadratic constraints
• Propagating XML constraints to relations
• Dependency-preserving normalization of relational and XML data

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

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q3631894)