Semantic Acyclicity on Graph Databases
From MaRDI portal
Publication:3187172
DOI10.1137/15M1034714zbMath1407.68123OpenAlexW2480499276MaRDI QIDQ3187172
Moshe Y. Vardi, Pablo Barceló, Miguel Romero
Publication date: 16 August 2016
Published in: SIAM Journal on Computing (Search for Journal in Brave)
Full work available at URL: https://doi.org/10.1137/15m1034714
acyclicityquery evaluationconstraint satisfaction problemsconjunctive queriesgraph databasesquery approximationconjunctive regular path queries
Related Items (8)
The Power of Local Consistency in Conjunctive Queries and Constraint Satisfaction Problems ⋮ Semantic Acyclicity on Graph Databases ⋮ Regular queries on graph databases ⋮ A More General Theory of Static Approximations for Conjunctive Queries ⋮ Foundations of graph path query languages. Course notes for the reasoning web summer school 2021 ⋮ A navigational logic for reasoning about graph properties ⋮ Unnamed Item ⋮ A more general theory of static approximations for conjunctive queries
Uses Software
Cites Work
- Unnamed Item
- Unnamed Item
- Unnamed Item
- Unnamed Item
- Enumerating homomorphisms
- Relative expressive power of navigational querying on graphs
- Rewriting of regular expressions and regular path queries
- Hypertree decompositions and tractable queries
- On the expressive power of Datalog: tools and a case study.
- The complexity of facets (and some facets of complexity)
- A note on the reduction of two-way automata to one-way automata
- Conjunctive query containment revisited
- Conjunctive-query containment and constraint satisfaction
- Adding regular expressions to graph reachability and pattern queries
- Structural tractability of enumerating CSP solutions
- Degrees of acyclicity for hypergraphs and relational database schemes
- Semantic Acyclicity on Graph Databases
- Efficient Approximations of Conjunctive Queries
- The complexity of acyclic conjunctive queries
- Alternating Pushdown and Stack Automata
- Simple Linear-Time Algorithms to Test Chordality of Graphs, Test Acyclicity of Hypergraphs, and Selectively Reduce Acyclic Hypergraphs
- Query evaluation via tree-decompositions
- Beyond Hypertree Width: Decomposition Methods Without Decompositions
- Equivalences Among Relational Expressions with the Union and Difference Operators
- The Computational Structure of Monotone Monadic SNP and Constraint Satisfaction: A Study through Datalog and Group Theory
- A Logical Approach to Constraint Satisfaction
- Regular Queries on Graph Databases.
This page was built for publication: Semantic Acyclicity on Graph Databases