Relative expressive power of navigational querying on graphs
From MaRDI portal
Publication:528686
DOI10.1016/J.INS.2014.11.031zbMATH Open1360.68394arXiv1401.8201OpenAlexW2962721563MaRDI QIDQ528686FDOQ528686
Authors: George H. L. Fletcher, Marc Gyssens, Dirk Leinders, Dimitri Surinx, Jan Van den Bussche, D. Van Gucht, Stijn Vansummeren, Yuqing Wu 
Publication date: 16 May 2017
Published in: Information Sciences (Search for Journal in Brave)
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.
Full work available at URL: https://arxiv.org/abs/1401.8201
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
- Title not available (Why is that?)
- Title not available (Why is that?)
- Handbook of modal logic
- Title not available (Why is that?)
- Title not available (Why is that?)
- Structural properties of XPath fragments
- Relation algebras
- Relation algebras by games
- Title not available (Why is that?)
- First-order logic with two variables and unary temporal logic
- Multi-dimensional modal logic
- PDL with intersection and converse: satisfiability and infinite-state model checking
- Program constructions that are safe for bisimulation
- The impact of transitive closure on the expressiveness of navigational query languages on unlabeled graphs
- Model theoretic methods for fragments of FO and special classes of (finite) structures
- Forward node-selecting queries over trees
- Similarity and bisimilarity notions appropriate for characterizing indistinguishability in fragments of the calculus of relations
- Relative expressive power of navigational querying on graphs
Cited In (22)
- The power of Tarski's relation algebra on trees
- On the expressive power of linear algebra on graphs
- A navigational logic for reasoning about graph properties
- Static analysis of navigational XPath over graph databases
- Title not available (Why is that?)
- The impact of transitive closure on the Boolean expressiveness of navigational query languages on graphs
- Expressive path queries on graphs with data
- Navigational and rule-based languages for graph databases
- Foundations of graph path query languages. Course notes for the reasoning web summer school 2021
- The impact of transitive closure on the expressiveness of navigational query languages on unlabeled graphs
- Regular queries on graph databases
- Structural characterizations of the navigational expressiveness of relation algebras on a tree
- Inputs, Outputs, and Composition in the Logic of Information Flows
- Semantic acyclicity on graph databases
- Nesting Depth of Operators in Graph Database Queries: Expressiveness Vs. Evaluation Complexity
- Relative expressive power of navigational querying on graphs using transitive closure
- TriAL: a navigational algebra for RDF triplestores
- On the expressive power of linear algebra on graphs
- An Algebra for Path Manipulation in Graph Databases
- Relative expressive power of navigational querying on graphs
- 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
Uses Software
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)
