EUVIMEDEUVIMED entdecken
Crossref

Dependencies for Graphs

Wenfei Fan, Ping Lu

ACM Transactions on Database Systems · 30.06.2019 · 44 (2) · 1-40

DOI: 10.1145/3287285 ↗

Kurz gefasst

Fachartikel in der Zeitschrift ACM Transactions on Database Systems, online erschienen am 13.02.2019. Verfasst von Wenfei Fan und 1 weiteren Autor:innen. Die Arbeit wurde bisher 50-mal zitiert (Crossref) und nennt 55 Literaturangaben. Gefördert von: 973 Program, Beijing Advanced Innovation Center for Big Data and Brain Computing, Foundation for Innovative Research Groups of NSFC.

AbstractBibliografische AngabenZitierenVerwandte Studien

Abstract (Originalsprache)

This article proposes a class of dependencies for graphs, referred to as graph entity dependencies (GEDs). A GED is defined as a combination of a graph pattern and an attribute dependency. In a uniform format, GEDs can express graph functional dependencies with constant literals to catch inconsistencies, and keys carrying id literals to identify entities (vertices) in a graph. We revise the chase for GEDs and prove its Church-Rosser property. We characterize GED satisfiability and implication, and establish the complexity of these problems and the validation problem for GEDs, in the presence and absence of constant literals and id literals. We also develop a sound, complete and independent axiom system for finite implication of GEDs. In addition, we extend GEDs with built-in predicates or disjunctions, to strike a balance between the expressive power and complexity. We settle the complexity of the satisfiability, implication, and validation problems for these extensions.

Förderung

  • 973 Program
  • Beijing Advanced Innovation Center for Big Data and Brain Computing
  • Foundation for Innovative Research Groups of NSFC
  • Joint Lab between Edinburgh and Huawei
  • NSFC
  • EPSRC
  • ERC

Zitieren

APA

Fan, W., & Lu, P. (2019). Dependencies for Graphs. ACM Transactions on Database Systems, 44(2), 1-40. https://doi.org/10.1145/3287285

Vancouver

Fan W, Lu P. Dependencies for Graphs. ACM Transactions on Database Systems. 2019;44(2):1-40. doi:10.1145/3287285

BibTeX
@article{Fan2019,
  author = {Fan, Wenfei and Lu, Ping},
  title = {Dependencies for Graphs},
  journal = {ACM Transactions on Database Systems},
  year = {2019},
  volume = {44},
  number = {2},
  pages = {1--40},
  doi = {10.1145/3287285}
}
Kostenlos starten →