Graph data management has received a lot of attention in the last decade, fueled by rapid development of two vertical domains, Linked Data and Social Media. The former is centered around graphs represented as RDF data and queried with SPARQL, while the latter features small-world graphs that fit into the emerging Property Graph model.
This thesis deals with the database aspects of graph processing problems in these two domains. We start with incorporating path and reachability query processing into the state-of-the-art RDF query processing engine, RDF-3X. We then devise a new technique for join ordering and cardinality estimation for general graph pattern matching queries expressed in SPARQL over large RDF datasets. We also present an efficient algorithm for shortest path estimation in small-world graphs and its application to the keyword search on graphs (the Steiner tree problem). In the Property Graph data model, we design the query optimizer’s architecture for the popular graph database Neo4j and its query language. Finally, we solve the problem of selecting parameters for query templates as part of our benchmark for the broad class of graph-processing systems.
Graph data management has received a lot of attention in the last decade, fueled by rapid development of two vertical domains, Linked Data and Social Media. The former is centered around graphs represented as RDF data and queried with SPARQL, while the latter features small-world graphs that fit into the emerging Property Graph model.
This thesis deals with the database aspects of graph processing problems in these two domains. We start with incorporating path and reachability query processing into the state-of-the-art RDF query processing engine, RDF-3X. We then devise a new technique for join ordering and cardinality estimation for general graph pattern matching queries expressed in SPARQL over large RDF datasets. We also present an efficient algorithm for shortest path estimation in small-world graphs and its application to the keyword search on graphs (the Steiner tree problem). In the Property Graph data model, we design the query optimizer’s architecture for the popular graph database Neo4j and its query language. Finally, we solve the problem of selecting parameters for query templates as part of our benchmark for the broad class of graph-processing systems.