Conjunctive query containment over trees using schema information

DOI10.1007/s00236-016-0282-1zbMath1386.68066OpenAlexW2536272706MaRDI QIDQ1702301

Henrik Björklund, Wim Martens, Thomas Schwentick

Publication date: 28 February 2018

Published in: Acta Informatica (Search for Journal in Brave)

Full work available at URL: https://doi.org/10.1007/s00236-016-0282-1

Mathematics Subject Classification ID

Analysis of algorithms and problem complexity (68Q25) Database theory (68P15) Computational difficulty of problems (lower bounds, completeness, difficulty of approximation, etc.) (68Q17) Data structures (68P05)

Uses Software

• XPath
• Relax NG

Cites Work

• Unnamed Item
• Unnamed Item
• Solutions in XML data exchange
• Deciding determinism of regular languages
• Conjunctive query containment over trees
• On the complexity of typechecking top-down XML transformations
• On finding minimal length superstrings
• The shortest common supersequence problem over binary alphabet is NP- complete
• Conjunctive-query containment and constraint satisfaction
• Domino-tiling games
• Validity of Tree Pattern Queries with Respect to Schema Information
• Between Tree Patterns and Conjunctive Queries: Is There Tractability beyond Acyclicity?
• XML with incomplete information
• Relational and XML Data Exchange
• Monadic Datalog Containment
• Containment of Monadic Datalog Programs via Bounded Clique-Width
• Two-variable logic on data trees and XML reasoning
• The complexity of query containment in expressive fragments of XPath 2.0
• Query evaluation via tree-decompositions
• Conjunctive queries over trees
• XPath satisfiability in the presence of DTDs
• Complexity of Decision Problems for XML Schemas and Chain Regular Expressions
• Complexity of Data Tree Patterns over XML Documents
• Alternation
• Generalizations of regular sets and their application to a study of context-free languages
• Minimization of Tree Patterns
• Deciding Definability by Deterministic Regular Expressions
• On the complexity of XPath containment in the presence of disjunction, DTDs, and variables
• Database Programming Languages
• Containment and equivalence for a fragment of XPath
• Generalized finite automata theory with an application to a decision problem of second-order logic
• A variant of a recursively unsolvable problem
• One-unambiguous regular languages

This page was built for publication: Conjunctive query containment over trees using schema information