Discovering Graph Differential Dependencies

Yidi Zhang, Selasi Kwashie, Michael Bewong, Junwei Hu, Arash Mahboubi, Xi Guo, Zaiwen Feng

Research output: Book chapter/Published conference paperConference paperpeer-review

56 Downloads (Pure)


Graph differential dependencies (GDDs) are a novel class of integrity constraints in property graphs for capturing and expressing the semantics of difference in graph data. They are more expressive, and subsume other graph dependencies; and thus, are more useful for addressing many real-world graph data quality/management problems. In this paper, we study the general discovery problem for GDDs – the task of finding a non-redundant and succinct set of GDDs that hold in a given property graph. Indeed, we present characterisations of GDDs based on their semantics, extend existing data structures, and device pruning strategies to enable our proposed level-wise discovery algorithm, GDDMiner, returns a minimal cover of valid GDDs efficiently. Further, we perform experiments over three real-world graphs to demonstrate the feasibility, scalability, and effectiveness of our solution.
Original languageEnglish
Title of host publicationDatabase Theory and Applications
Subtitle of host publication34th Australasian Database Conference, ADC 2023, Proceedings
EditorsZhifeng Bao, Renata Borovica-Gajic, Ruihong Qiu, Farhana Choudhury, Zhengyi Yang
Place of PublicationCham, Switzerland
Number of pages14
ISBN (Electronic)9783031478437
ISBN (Print)9783031478420
Publication statusPublished - 2024
Event2023 Australasian Database Conference: ADC 2023 - Melbourne Connect, Melbourne, Australia
Duration: 01 Nov 202303 Nov 2023 (Program)

Publication series

NameLecture Notes in Computer Science
PublisherSpringer Cham
ISSN (Print)0302-9743
ISSN (Electronic)1611-3349


Conference2023 Australasian Database Conference
OtherThe Australasian Database Conference (ADC) series is an annual forum for sharing the latest research progresses and novel applications of database systems, data management, data mining and data analytics for researchers and practitioners in these areas from Australia, New Zealand and in the world. The 34th edition of the Australasian Database Conference, ADC 2023, will be held in Melbourne, Australia. We welcome contributions related to all aspects of database theory and foundation, techniques, and applications.
Internet address


Dive into the research topics of 'Discovering Graph Differential Dependencies'. Together they form a unique fingerprint.

Cite this