Querying Graphs

Foreword
Acknowledgments
Introduction
Data Models
	Property Graph Model
	Variations of the PGM
		Specializations
		Structural Extensions
		Data Representation Extensions
		Summary
	Bibliographic and Historical Notes
Query Languages
	Basic Functionality
		Regular Path Queries
		Conjunctive Graph Queries
		Conjunctive Regular Path Queries
		Unions of Conjunctive Regular Path Queries
		Relation Algebra
	Regular Property Graph Queries
		Regular Property Graph Logic
		Regular Property Graph Algebra
		Equivalence and Complexity of RPGLog and RPGA
	RPGQ in Context
		Important Fragments of RPGQ
		Extending RPGQ For Composability
		RPGQ and Practical Graph Query Languages
	Bibliographic and Historical Notes
Constraints
	Preliminaries
	Graph Functional Dependencies
		Syntax
		Semantics
		Satisfiability
		Implication
		Validation
	Graph Entity Dependencies
		Definition and Special Cases
		Preliminaries
		Chasing Graph Entity Dependencies
		Satisfiability, Implication, and Validation
		Extension to Graph Denial Constraints
		Applications and Practical Impact of Graph Dependencies
	Other Constraints for Graph Data Management
		Graph Neighborhood Constraints
		Graph-to-Graph Constraints
	Bibliographic and Historical Notes
Query Specification
	Path Query Specification
		The Definability Problem for Graph Queries
		Complexity of Definability for Graph Queries
		From Definability to Learnability of Graph Queries
		Interactive Graph Query Specification
	Graph Searching for Querying
	Query-Driven Graph Exploration
	Bibliographic Notes
Data Structures and Indexes
	Conceptual Schemas of PGM Representation
	Direct Representation of Ternary Relations
		Value Compression
		Value Indexing
	Pivoted Representation of Ternary Relations
	Adjacency Indexing
		Uncompressed Adjacency Representation
		Compressed Adjacency Representation
	Reachability Indexing
		General Considerations
		Techniques
	Structural Indexing
	Bibliographic and Historical Notes
Query Processing
	Query Pipeline
	Subgraph Matching Queries
		DFS-Based algorithms
		BFS-Based Algorithms
		Discussion
	Regular Path Queries
		Relational Algebra and Datalog-Based Approaches
		Finite Automata-Based Approaches
	Unions of Conjunctive Regular Path Queries
	Bibliographic and Historical Notes
Physical Operators
	Transitive Closure
	Multi-Way Joins
	Cardinality Estimation
		Cardinality of Paths
		Cardinality of Patterns
	Further Optimizations
	Bibliographic and Historical Notes
Research Challenges
Bibliography
Authors' Biographies