Towards sequenced semantics for evolving graphs

Vera Zaychik Moffitt, Julia Stoyanovich

    Research output: Chapter in Book/Report/Conference proceedingConference contribution


    The research community has adopted a sequence of snapshots as the logical representation of evolving graphs — graphs that change over time and whose history of evolution we want to preserve for analysis. This paper argues that the snapshot sequence model of evolving graphs is insu cient for representation and analysis of a wide range of networks. Instead, we propose to use the interval model with sequenced semantics. In this model nodes and edges are associated with their validity intervals, and operations adhere to the properties of snapshot reducibility, extended snapshot reducibility, and change preservation. We show the advantages of adopting this model for evolving graphs and lay the groundwork for an evolving graph query language with sequenced semantics. We also discuss several challenges of e ciently supporting sequenced semantics in a distributed setting.

    Original languageEnglish (US)
    Title of host publicationAdvances in Database Technology - EDBT 2017
    Subtitle of host publication20th International Conference on Extending Database Technology, Proceedings
    EditorsBernhard Mitschang, Volker Markl, Sebastian Bress, Periklis Andritsos, Kai-Uwe Sattler, Salvatore Orlando
    Number of pages4
    ISBN (Electronic)9783893180738
    StatePublished - 2017
    Event20th International Conference on Extending Database Technology, EDBT 2017 - Venice, Italy
    Duration: Mar 21 2017Mar 24 2017

    Publication series

    NameAdvances in Database Technology - EDBT
    ISSN (Electronic)2367-2005


    Other20th International Conference on Extending Database Technology, EDBT 2017

    ASJC Scopus subject areas

    • Information Systems
    • Software
    • Computer Science Applications


    Dive into the research topics of 'Towards sequenced semantics for evolving graphs'. Together they form a unique fingerprint.

    Cite this