Discovering Graph Differential Dependencies

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

doi:10.1007/978-3-031-47843-7_18

Discovering Graph Differential Dependencies

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

Huazhong Agricultural University

Research output: Book chapter/Published conference paper › Conference paper › peer-review

182 Downloads (Pure)

Abstract

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 language	English
Title of host publication	Database Theory and Applications
Subtitle of host publication	34th Australasian Database Conference, ADC 2023, Proceedings
Editors	Zhifeng Bao, Renata Borovica-Gajic, Ruihong Qiu, Farhana Choudhury, Zhengyi Yang
Place of Publication	Cham, Switzerland
Publisher	Springer
Pages	259-272
Number of pages	14
Volume	14386
ISBN (Electronic)	9783031478437
ISBN (Print)	9783031478420
DOIs	https://doi.org/10.1007/978-3-031-47843-7_18
Publication status	Published - 2024
Event	2023 Australasian Database Conference: ADC 2023 - Melbourne Connect, Melbourne, Australia Duration: 01 Nov 2023 → 03 Nov 2023 https://adc2023.github.io/ https://adc2023.github.io/ADC_2023_Program_Structure.pdf (Program)

Publication series

Name	Lecture Notes in Computer Science
Publisher	Springer Cham
Number	1
Volume	14386
ISSN (Print)	0302-9743
ISSN (Electronic)	1611-3349

Conference

Conference	2023 Australasian Database Conference
Country/Territory	Australia
City	Melbourne
Period	01/11/23 → 03/11/23
Other	The 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	https://adc2023.github.io/ https://adc2023.github.io/ADC_2023_Program_Structure.pdf (Program)

Access to Document

10.1007/978-3-031-47843-7_18

407126930_Accepted manuscriptAccepted author manuscript, 795 KB

Cite this

Zhang, Y., Kwashie, S., Bewong, M., Hu, J., Mahboubi, A., Guo, X., & Feng, Z. (2024). Discovering Graph Differential Dependencies. In Z. Bao, R. Borovica-Gajic, R. Qiu, F. Choudhury, & Z. Yang (Eds.), Database Theory and Applications: 34th Australasian Database Conference, ADC 2023, Proceedings (Vol. 14386, pp. 259-272). (Lecture Notes in Computer Science; Vol. 14386, No. 1). Springer. https://doi.org/10.1007/978-3-031-47843-7_18

Zhang, Yidi ; Kwashie, Selasi ; Bewong, Michael et al. / Discovering Graph Differential Dependencies. Database Theory and Applications: 34th Australasian Database Conference, ADC 2023, Proceedings. editor / Zhifeng Bao ; Renata Borovica-Gajic ; Ruihong Qiu ; Farhana Choudhury ; Zhengyi Yang. Vol. 14386 Cham, Switzerland : Springer, 2024. pp. 259-272 (Lecture Notes in Computer Science; 1).

@inproceedings{1519419600e346e28ba38c768e3d5316,

title = "Discovering Graph Differential Dependencies",

abstract = "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.",

keywords = "Graph differential dependency, Graph dependencies, Data dependencies, Dependency discovery",

author = "Yidi Zhang and Selasi Kwashie and Michael Bewong and Junwei Hu and Arash Mahboubi and Xi Guo and Zaiwen Feng",

year = "2024",

doi = "10.1007/978-3-031-47843-7_18",

language = "English",

isbn = "9783031478420",

volume = "14386",

series = "Lecture Notes in Computer Science",

publisher = "Springer",

number = "1",

pages = "259--272",

editor = "Zhifeng Bao and Borovica-Gajic, { Renata } and Qiu, {Ruihong } and Choudhury, {Farhana } and Yang, {Zhengyi }",

booktitle = "Database Theory and Applications",

address = "United States",

note = "2023 Australasian Database Conference : ADC 2023 ; Conference date: 01-11-2023 Through 03-11-2023",

url = "https://adc2023.github.io/, https://adc2023.github.io/ADC_2023_Program_Structure.pdf",

}

Zhang, Y, Kwashie, S , Bewong, M, Hu, J, Mahboubi, A, Guo, X & Feng, Z 2024, Discovering Graph Differential Dependencies. in Z Bao, R Borovica-Gajic, R Qiu, F Choudhury & Z Yang (eds), Database Theory and Applications: 34th Australasian Database Conference, ADC 2023, Proceedings. vol. 14386, Lecture Notes in Computer Science, no. 1, vol. 14386, Springer, Cham, Switzerland, pp. 259-272, 2023 Australasian Database Conference, Melbourne, Victoria, Australia, 01/11/23. https://doi.org/10.1007/978-3-031-47843-7_18

Discovering Graph Differential Dependencies. / Zhang, Yidi; Kwashie, Selasi ; Bewong, Michael et al.
Database Theory and Applications: 34th Australasian Database Conference, ADC 2023, Proceedings. ed. / Zhifeng Bao; Renata Borovica-Gajic; Ruihong Qiu; Farhana Choudhury; Zhengyi Yang. Vol. 14386 Cham, Switzerland: Springer, 2024. p. 259-272 (Lecture Notes in Computer Science; Vol. 14386, No. 1).

Research output: Book chapter/Published conference paper › Conference paper › peer-review

TY - GEN

T1 - Discovering Graph Differential Dependencies

AU - Zhang, Yidi

AU - Kwashie, Selasi

AU - Bewong, Michael

AU - Hu, Junwei

AU - Mahboubi, Arash

AU - Guo, Xi

AU - Feng, Zaiwen

PY - 2024

Y1 - 2024

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

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

KW - Graph differential dependency

KW - Graph dependencies

KW - Data dependencies

KW - Dependency discovery

UR - https://www.webofscience.com/api/gateway?GWVersion=2&SrcApp=woscharlessturt_pure&SrcAuth=WosAPI&KeyUT=WOS:001150179700018&DestLinkType=FullRecord&DestApp=WOS_CPL

U2 - 10.1007/978-3-031-47843-7_18

DO - 10.1007/978-3-031-47843-7_18

M3 - Conference paper

SN - 9783031478420

VL - 14386

T3 - Lecture Notes in Computer Science

SP - 259

EP - 272

BT - Database Theory and Applications

A2 - Bao, Zhifeng

A2 - Borovica-Gajic, Renata

A2 - Qiu, Ruihong

A2 - Choudhury, Farhana

A2 - Yang, Zhengyi

PB - Springer

CY - Cham, Switzerland

T2 - 2023 Australasian Database Conference

Y2 - 1 November 2023 through 3 November 2023

ER -

Zhang Y, Kwashie S , Bewong M, Hu J, Mahboubi A, Guo X et al. Discovering Graph Differential Dependencies. In Bao Z, Borovica-Gajic R, Qiu R, Choudhury F, Yang Z, editors, Database Theory and Applications: 34th Australasian Database Conference, ADC 2023, Proceedings. Vol. 14386. Cham, Switzerland: Springer. 2024. p. 259-272. (Lecture Notes in Computer Science; 1). Epub 2023 Nov 7. doi: 10.1007/978-3-031-47843-7_18

Discovering Graph Differential Dependencies

Abstract

Publication series

Conference

Access to Document

Other files and links

Fingerprint

Cite this