Error message

  • Deprecated function: TYPO3\PharStreamWrapper\Manager::initialize(): Implicitly marking parameter $resolver as nullable is deprecated, the explicit nullable type must be used instead in include_once() (line 19 of /is/htdocs/wp1066709_HN3MCMCRY7/www/swj/includes/file.phar.inc).
  • Deprecated function: TYPO3\PharStreamWrapper\Manager::initialize(): Implicitly marking parameter $collection as nullable is deprecated, the explicit nullable type must be used instead in include_once() (line 19 of /is/htdocs/wp1066709_HN3MCMCRY7/www/swj/includes/file.phar.inc).
  • Deprecated function: TYPO3\PharStreamWrapper\Manager::__construct(): Implicitly marking parameter $resolver as nullable is deprecated, the explicit nullable type must be used instead in include_once() (line 19 of /is/htdocs/wp1066709_HN3MCMCRY7/www/swj/includes/file.phar.inc).
  • Deprecated function: TYPO3\PharStreamWrapper\Manager::__construct(): Implicitly marking parameter $collection as nullable is deprecated, the explicit nullable type must be used instead in include_once() (line 19 of /is/htdocs/wp1066709_HN3MCMCRY7/www/swj/includes/file.phar.inc).
  • Warning: ini_set(): Session ini settings cannot be changed after headers have already been sent in include_once() (line 354 of /is/htdocs/wp1066709_HN3MCMCRY7/www/swj/sites/default/settings.php).
  • Warning: ini_set(): Session ini settings cannot be changed after headers have already been sent in include_once() (line 355 of /is/htdocs/wp1066709_HN3MCMCRY7/www/swj/sites/default/settings.php).
  • Warning: ini_set(): Session ini settings cannot be changed after headers have already been sent in include_once() (line 363 of /is/htdocs/wp1066709_HN3MCMCRY7/www/swj/sites/default/settings.php).
  • Warning: ini_set(): Session ini settings cannot be changed after headers have already been sent in include_once() (line 370 of /is/htdocs/wp1066709_HN3MCMCRY7/www/swj/sites/default/settings.php).
  • Warning: ini_set(): Session ini settings cannot be changed after headers have already been sent in drupal_settings_initialize() (line 826 of /is/htdocs/wp1066709_HN3MCMCRY7/www/swj/includes/bootstrap.inc).
  • Warning: ini_set(): Session ini settings cannot be changed after headers have already been sent in drupal_settings_initialize() (line 835 of /is/htdocs/wp1066709_HN3MCMCRY7/www/swj/includes/bootstrap.inc).
  • Warning: session_name(): Session name cannot be changed after headers have already been sent in drupal_settings_initialize() (line 838 of /is/htdocs/wp1066709_HN3MCMCRY7/www/swj/includes/bootstrap.inc).

PathFinder: Returning Paths in Graph Queries

Tracking #: 4105-5319

This paper is currently under review
Authors: 
Benjamín Farías
Wim Martens
Carlos Rojas
Domagoj Vrgoč

Responsible editor: 
Marta Sabou

Submission type: 
Full Paper
Abstract: 
Path queries are a central feature of all modern graph query languages and standards, such as SPARQL, Cypher, SQL/PGQ, and GQL. While SPARQL returns endpoints of path queries, it is possible in Cypher, SQL/PGQ, and GQL to return entire paths. In this paper, we present the first framework for returning paths that match regular path queries under all twenty seven modes supported by the SQL/PGQ and GQL standards. At the core of our approach is the product graph construction combined with a way to compactly represent a huge number of results that can match a path query. We describe the approach on a conceptual level and provide runtime guarantees for evaluating path queries. We also show how it can be incorporated into the SPARQL query language, thus extending RDF engines with the ability to return witnesses to property path queries (under the GQL semantics). To show the feasibility of our methods in practice, we develop a reference implementation on top of an existing open-source graph processing engine MillenniumDB, and perform a detailed analysis of path querying over several synthetic and real-world datasets. In particular, we test our implementation over Wikidata using property path queries posted by users, extending them with the ability to return paths. We obtain order-of-magnitude speedups over modern graph database engines and remarkably stable performance, even for theoretically intractable queries.
Full PDF Version: 
Tags: 
Under Review