Relative expressive power of navigational querying on graphs
From MaRDI portal
(Redirected from Publication:528686)
Abstract: Motivated by both established and new applications, we study navigational query languages for graphs (binary relations). The simplest language has only the two operators union and composition, together with the identity relation. We make more powerful languages by adding any of the following operators: intersection; set difference; projection; coprojection; converse; and the diversity relation. All these operators map binary relations to binary relations. We compare the expressive power of all resulting languages. We do this not only for general path queries (queries where the result may be any binary relation) but also for boolean or yes/no queries (expressed by the nonemptiness of an expression). For both cases, we present the complete Hasse diagram of relative expressiveness. In particular the Hasse diagram for boolean queries contains some nontrivial separations and a few surprising collapses.
Recommendations
- Relative expressive power of navigational querying on graphs using transitive closure
- Expressive path queries on graphs with data
- Expressive path queries on graph with data
- The impact of transitive closure on the expressiveness of navigational query languages on unlabeled graphs
- The impact of transitive closure on the Boolean expressiveness of navigational query languages on graphs
- Querying best paths in graph databases
- Nesting Depth of Operators in Graph Database Queries: Expressiveness Vs. Evaluation Complexity
- Path logics for querying graphs: combining expressiveness and efficiency
- Optimal query complexity bounds for finding graphs
Cites work
- scientific article; zbMATH DE number 193143 (Why is no real title available?)
- scientific article; zbMATH DE number 1324669 (Why is no real title available?)
- scientific article; zbMATH DE number 1936671 (Why is no real title available?)
- scientific article; zbMATH DE number 1556014 (Why is no real title available?)
- scientific article; zbMATH DE number 839556 (Why is no real title available?)
- First-order logic with two variables and unary temporal logic
- Forward node-selecting queries over trees
- Handbook of modal logic
- Model theoretic methods for fragments of FO and special classes of (finite) structures
- Multi-dimensional modal logic
- PDL with intersection and converse: satisfiability and infinite-state model checking
- Program constructions that are safe for bisimulation
- Relation algebras
- Relation algebras by games
- Relative expressive power of navigational querying on graphs
- Similarity and bisimilarity notions appropriate for characterizing indistinguishability in fragments of the calculus of relations
- Structural properties of XPath fragments
- The impact of transitive closure on the expressiveness of navigational query languages on unlabeled graphs
Cited in
(22)- Foundations of graph path query languages. Course notes for the reasoning web summer school 2021
- The impact of transitive closure on the Boolean expressiveness of navigational query languages on graphs
- Static analysis of navigational XPath over graph databases
- On the expressive power of linear algebra on graphs
- The power of Tarski's relation algebra on trees
- Expressive path queries on graphs with data
- Relative expressive power of navigational querying on graphs using transitive closure
- An Algebra for Path Manipulation in Graph Databases
- On the expressive power of linear algebra on graphs
- Semantic acyclicity on graph databases
- Structural characterizations of the navigational expressiveness of relation algebras on a tree
- Regular queries on graph databases
- The impact of transitive closure on the expressiveness of navigational query languages on unlabeled graphs
- scientific article; zbMATH DE number 2086655 (Why is no real title available?)
- Inputs, Outputs, and Composition in the Logic of Information Flows
- Relative expressive power of navigational querying on graphs
- Navigational and rule-based languages for graph databases
- TriAL: a navigational algebra for RDF triplestores
- A framework for comparing query languages in their ability to express Boolean queries
- A framework for comparing query languages in their ability to express Boolean queries
- Nesting Depth of Operators in Graph Database Queries: Expressiveness Vs. Evaluation Complexity
- A navigational logic for reasoning about graph properties
This page was built for publication: Relative expressive power of navigational querying on graphs
Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q528686)
