Conjunctive query containment over trees using schema information
DOI10.1007/S00236-016-0282-1zbMATH Open1386.68066OpenAlexW2536272706MaRDI QIDQ1702301FDOQ1702301
Authors: 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
Recommendations
Analysis of algorithms and problem complexity (68Q25) Data structures (68P05) Computational difficulty of problems (lower bounds, completeness, difficulty of approximation, etc.) (68Q17) Database theory (68P15)
Cites Work
- Deciding definability by deterministic regular expressions
- Deciding determinism of regular languages
- One-unambiguous regular languages
- Conjunctive-query containment and constraint satisfaction
- XML with incomplete information
- 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
- Alternation
- On the complexity of XPath containment in the presence of disjunction, DTDs, and variables
- Conjunctive query containment over trees
- Containment and equivalence for a fragment of XPath
- A variant of a recursively unsolvable problem
- Relational and XML Data Exchange
- Generalized finite automata theory with an application to a decision problem of second-order logic
- Title not available (Why is that?)
- On finding minimal length superstrings
- Domino-tiling games
- Complexity of Data Tree Patterns over XML Documents
- Solutions in XML data exchange
- The shortest common supersequence problem over binary alphabet is NP- complete
- Title not available (Why is that?)
- On the complexity of typechecking top-down XML transformations
- Generalizations of regular sets and their application to a study of context-free languages
- Validity of tree pattern queries with respect to schema information
- Containment of monadic Datalog programs via bounded clique-width
- Between tree patterns and conjunctive queries: is there tractability beyond acyclicity?
- Monadic Datalog Containment
- Minimization of tree patterns
- Database Programming Languages
Cited In (16)
- Satisfiability for SCULPT-schemas for CSV-like data
- Containment for conditional tree patterns
- Conjunctive query evaluation by search-tree revisited
- Conjunctive query containment over trees
- Title not available (Why is that?)
- Flexible Querying Using Criterion Trees: A Bipolar Approach
- Reasoning about integrity constraints for tree-structured data
- Reasoning about integrity constraints for tree-structured data
- Optimizing Conjunctive Queries over Trees Using Schema Information
- Static analysis and query answering for incomplete data trees with constraints
- Testing satisfiability of a class of object-oriented conjunctive queries
- A revised result on chasing tree patterns under schema graphs
- XML queries and constraints, containment and reformulation
- Validity of tree pattern queries with respect to schema information
- Conjunctive queries over trees
- Between tree patterns and conjunctive queries: is there tractability beyond acyclicity?
Uses Software
This page was built for publication: Conjunctive query containment over trees using schema information
Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q1702301)
