Title Querying Graphs
Subtitle (Synthesis Lectures on Data Management)
Author Angela Bonifati, George Fletcher, Hannes Voigt, Nikolay Yakovet
ISBN 9781681734309
List price USD 74.95
Price outside India Available on Request
Original price
Binding Paperback
No of pages 184
Book size 191 X 235 mm
Publishing year 2018
Original publisher Morgan & Claypool Publishers (Eurospan Group)
Published in India by .
Exclusive distributors Viva Books Private Limited
Sales territory India, Sri Lanka, Bangladesh, Pakistan, Nepal, .
Status New Arrival
About the book Send Enquiry


Graph data modeling and querying arises in many practical application domains such as social and biological networks where the primary focus is on concepts and their relationships and the rich patterns in these complex webs of interconnectivity. In this book, we present a concise unified view on the basic challenges which arise over the complete life cycle of formulating and processing queries on graph databases. To that purpose, we present all major concepts relevant to this life cycle, formulated in terms of a common and unifying ground: the property graph data model (the pre-dominant data model adopted by modern graph database systems).

We aim especially to give a coherent and in-depth perspective on current graph querying and an outlook for future developments. Our presentation is self-contained, covering the relevant topics from: graph data models, graph query languages and graph query specification, graph constraints, and graph query processing. We conclude by indicating major open research challenges towards the next generation of graph data management systems.




Chapter 1. Introduction

Chapter 2. Data Models • Property Graph Model • Variations of the PGM • Specializations • Structural Extensions • Data Representation Extensions • Summary • Bibliographic and Historical Notes

Chapter 3. 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 RPGQExtending RPGQ For ComposabilityRPGQ and Practical Graph Query Languages • Bibliographic and Historical Notes

Chapter 4. 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

Chapter 5. 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

Chapter 6. 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

Chapter 7. 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

Chapter 8. Physical Operators • Transitive Closure • Multi-Way Joins • Cardinality Estimation • Cardinality of Paths • Cardinality of Patterns • Further Optimizations • Bibliographic and Historical Notes

Chapter 9. Research Challenges


Authors’ Biographies

About the Authors:

Angela Bonifati is a full professor of computer science at Université Claude Bernard Lyon 1 and affiliated with the CNRS Liris research lab. She received her Ph.D. from Politecnico di Milano in 2002 and right after she was a postdoctoral researcher at INRIA Roquencourt. Her current research interests are on the interplay of relational and graph-shaped data paradigms, particularly on schema mapping and data exchange, query processing, and learning for these data models. She was Vice Chair of ICDE 2018 for the information extraction, data cleaning, and curation track and Vice Chair of ICDE 2011 for the semi-structured data track. She is Associate Editor of the VLDB Journal, ACM TODS, and Distributed and Parallel Databases. She is a member-at-large of the ICDT council and serving on the program committees of SIGMOD, PODS, PVLDB, ICDE, and EDBT.

George Fletcher is an associate professor of computer science at Technische Universiteit Eindhoven where he is chair of the Database Group. He defended a Ph.D. at Indiana University Bloomington in 2007. His research interests span query language design and engineering, foundations of databases, and data integration. His current focus is on management of massive graphs such as social networks and linked open data. He was a co-organizer of the EDBT Summer School on Graph Data Management (2015) and is currently a member of the LDBC Graph Query Language Standardization Task Force. His other recent activities include co-organizing an NII Shonan seminar on Graph Database Systems (2018) and serving on the program committees of SIGMOD, VLDB, ISWC, ICDE, EDBT, and IJCAI.

Hannes Voigt is a software engineer at Neo4j since June 2018, where he is part of the Query Languages, Standards, and Research team. Before that he was a post-doctoral researcher at the Dresden Database Systems Group, Technische Universitat Dresden and obtained his Ph.D. from the same university in 2014. As a researcher, he worked on various database topics such as declarative graph query languages, database evolution and versioning, management of schema-flexible data, and self-adapting indexes. He is member of the LDBC Graph Query Language Standardization Task Force. Other recent activities include co-editing the section on graph analytics in the Encyclopedia of Big Data Technologies, co-presenting a tutorial on graph query processing at EDBT 2017, and serving on the program committees of VLDB, ICDE, and CIKM.

Nikolay Yakovets is an assistant professor of computer science at Technische Universiteit Eindhoven. He obtained his Ph.D. from Lassonde School of Engineering at York University in 2017. He worked on various database topics at IBM CAS Canada and Empress Software Canada. His current focus is on design and implementation of core database technologies, management of massive graph data, and efficient processing of queries on graphs. His recent activities include co-presenting a tutorial on graph query processing at EDBT 2017, co-organizing the 2017 edition of the Dutch-Belgian Database Day, and serving on a program committee of ICDE.

Target Audience:

This book is useful for people interested in computer science and information technology. It gives a unified treatment of Graph Data Bases (GDBs), as needed to serve as a reference book for experts and a textbook for graduate students. GDB systems are used in application areas such as semantic web, social networking, fraud detections, recommendation systems, life science and knowledge bases.


Special prices are applicable to the authorised sales territory only.
Prices are subject to change without prior notice.