Servicenavigation

Project Details

Back

Projekt Print View

Query- and Specification Languages for Graph- and Grid-Structured Data

Subject Area Theoretical Computer Science
Term from 2017 to 2023
Project identifier Deutsche Forschungsgemeinschaft (DFG) - Project number 369116833
 
Final Report Year 2023

Final Report Abstract

The present project investigated foundations of graph- and grid-structured data. In terms of grid-structured data (aka tabular data or csv-like data), we have shown that the proposal of schema for tabular data of the World Wide Web Consortium can be significantly extended while still allowing efficient validation and static analysis algorithms. Furthermore, we have built a validation engine for this more extended fragment. Since some of these goals had already been reached during the review phase of the project proposal, we continued our work on grid-structured data in the framework of document spanners, which was the basis of a proposal by Arenas et al. (PVLDB 2016) for handling csv-like data. We obtained numerous fundamental results on speeding up the evaluation of document spanners by parallelization, and on how to extend the document spanner framework with weights and aggregation. The core of the present project was on evaluation of navigational queries on graphs. Here, we produced a number of theoretical papers on the efficiency of evaluating modern graph database queries, i.e., under simple paths, trail, and shortest paths semantics, as will be implemented in GQL and SQL/PGQ. We note that two of these modes (simple paths and trail) were already possible in Cypher. We could go significantly beyond the goals of the project by collaborating in several papers around the ISO standardization of query languages for property graphs. We feel that especially this work shows that the project achieved its goal of bringing theory and practice closer together. Furthermore, one of the papers in this part of the project won a prestigious SIGMOD Research Highlight Award. In terms of static analysis of navigational queries on graphs, we have provided a detailed overview of the complexity of containment of CRPQs (the core of pattern matching queries in today’s systems). We focused in practically relevant fragments of CRPQs, guided on our analysis of real-world queries. Our work shows a detailed overview of when containment is expected to be feasible in practice. Finally, we have built a number of practical tools that connect theory with practice. Our tool for validating csv-like data was already finished during the review phase of the project. The other important tool that we built was for analyzing huge amounts of SPARQL queries. We managed to analyze logs consisting of around 800 million SPARQL queries using the tool, which gave us invaluable insights for the fundamental work packages (B,C) in the project. The work packages (A,B,C,E) were therefore completed successfully.

Publications

 
 

Additional Information

© 2025 DFG Disclaimer / Copyright / Privacy Policy

Textvergrößerung und Kontrastanpassung