Relative expressive power of navigational querying on graphs
From MaRDI portal
Publication:528686
DOI10.1016/J.INS.2014.11.031zbMATH Open1360.68394arXiv1401.8201OpenAlexW2962721563MaRDI QIDQ528686FDOQ528686
Dirk Leinders, Dimitri Surinx, Marc Gyssens, Yuqing Wu, George H. L. Fletcher, Stijn Vansummeren, D. Van Gucht, Jan Van den Bussche
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
Cites Work
- Title not available (Why is that?)
- Title not available (Why is that?)
- Title not available (Why is that?)
- Title not available (Why is that?)
- Title not available (Why is that?)
- Title not available (Why is that?)
- Title not available (Why is that?)
- Structural properties of XPath fragments
- Relation algebras
- Relation algebras by games
- 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
- 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 (9)
- The impact of transitive closure on the expressiveness of navigational query languages on unlabeled graphs
- Regular queries on graph databases
- Navigational and Rule-Based Languages for Graph Databases
- Structural characterizations of the navigational expressiveness of relation algebras on a tree
- Inputs, Outputs, and Composition in the Logic of Information Flows
- Nesting Depth of Operators in Graph Database Queries: Expressiveness Vs. Evaluation Complexity
- Semantic Acyclicity on Graph Databases
- Relative expressive power of navigational querying on graphs
- A framework for comparing query languages in their ability to express Boolean queries
Uses Software
Recommendations
- Title not available (Why is that?) 👍 👎
- The impact of transitive closure on the expressiveness of navigational query languages on unlabeled graphs 👍 👎
- Expressive Path Queries on Graphs with Data 👍 👎
- The Impact of Transitive Closure on the Boolean Expressiveness of Navigational Query Languages on Graphs 👍 👎
- Expressive Path Queries on Graph with Data 👍 👎
- Nesting Depth of Operators in Graph Database Queries: Expressiveness Vs. Evaluation Complexity 👍 👎
- Path Logics for Querying Graphs: Combining Expressiveness and Efficiency 👍 👎
- Relative expressive power of navigational querying on graphs using transitive closure 👍 👎
- Optimal query complexity bounds for finding graphs 👍 👎
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)
