Semantic Acyclicity on Graph Databases

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

zbMATH Keywords

acyclicityquery evaluationconstraint satisfaction problemsconjunctive queriesgraph databasesquery approximationconjunctive regular path queries

Mathematics Subject Classification ID

Database theory (68P15)

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

• XPath
• GraphLog

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