Abstract
Entities and the concepts they instantiate evolve over time. For example, a corporate entity may have resulted from a series of mergers and splits, or a concept such as that of Whale may have evolved along with our understanding of the physical world. We propose a model for capturing and querying concept evolution. Our proposal extends an RDF-like model with temporal features and evolution operators. In addition, we provide a query language that exploits these extensions and supports historical queries. Moreover, we study how evolution information can be exploited to answer queries that are agnostic to evolution details (hence, evolution-unaware). For these, we propose dynamic programming algorithms and evaluate their efficiency and scalability by experimenting with both real and synthetic datasets.
Article PDF
Similar content being viewed by others
Explore related subjects
Discover the latest articles, news and stories from top researchers in related subjects.Avoid common mistakes on your manuscript.
References
Bhalotia G, Hulgeri A, Nakhe C, Chakrabarti S, Sudarshan S (2002) Keyword searching and browsing in databases using banks. In: ICDE, pp 431–440
Blakeley J, Larson PA, Tompa FW (1986) Efficiently updating materialized views. In: SIGMOD, pp 61–71
Buneman P, Khanna S, Tajima K, Tan W (2002) Archiving scientific data. In: SIGMOD, pp 1–12
Bykau, Siarhei, Mylopoulos J, Rizzolo F, Velegrakis Y (2011) Supporting queries spanning across phases of evolving artifacts using steiner forests. In: CIKM, pp 1649–1658
Chawathe S, Abiteboul S, Widom J (1999) Managing historical semistructured data. In: Theory and Practice of Object Systems, pp 143–162
Chien S, Tsotras V, Zaniolo C (2001) Efficient management of multiversion documents by object referencing. In: VLDB, pp 291–300
Dalvi NN, Kumar R, Pang B, Ramakrishnan R, Tomkins A, Bohannon P, Keerthi S, Merugu S (2009) A web of concepts. In: PODS, pp 1–12
Dalvi N, Suciu D (2007) Efficient query evaluation on probabilistic databases. VLDB J 16:523–544
Ding B, Yu JX, Wang S, Qin L, Zhang X, Lin X (2007) Finding Top-k Min-Cost connected trees in databases. In: ICDE, pp 836–845
Dong X, Halevy AY, Madhavan J (2005) Reference reconciliation in complex information spaces. In: SIGMOD, pp 85–96
Dong, X, Halevy AY, Yu C (2007) Data integration with uncertainty. VLDB, VLDB Endowment, pp 687–698
Dreyfus SE, Wagner RA (1972) The Steiner problem in graphs. Networks 1: 195–207
Dyreson CE, Evans WS, Lin H, Snodgrass RT (2000) Efficiently supported temporal granularities. IEEE Trans Knowl Data Eng 12: 568–587
Flouris G, Manakanatas D, Kondylakis H, Plexousakis D, Antoniou G (2008) Ontology change: classification and survey. Knowl Eng Rev 23: 117–152
Gassner E (2010) The Steiner Forest Problem revisited. J Discrete Algorithms 8: 154–163
Gregersen H, Jensen CS (1999) Temporal entity-relationship models—a survey. IEEE Trans Knowl Data Eng 11: 464–497
Gutiérrez C, Hurtado CA, Vaisman AA (2005) Temporal RDF. In: ESWC, pp 93–107
He H, Wang H, Yang J 0001, Yu PS (2007) Blinks: ranked keyword searches on graphs. In: SIGMOD Conference, pp 305–316
Hull R, Yoshikawa M (1990) ILOG: declarative creation and manipulation of object identifiers. In: VLDB, pp 455–468
Ioannou E, Nejdl W, Niederee C, Velegrakis Y (2010) OntheFly entity-aware query processing in the presence of linkage. PVLDB 3: 429–438
Johnsonbaugh R, Kalin M (1991) A graph generation software package. In: SIGCSE, pp 151–154
Kacholia V, Pandit S, Chakrabarti S, Sudarshan S, Desai R, Karambelkar H (2005), Bidirectional expansion for keyword search on graph databases. In: VLDB, pp 505–516
Katsuno H, Mendelzon AO (1991) On the difference between updating a knowledge base and revising it. In: KR, pp 387–394
Kauppinen T, Hyvönen E (2007) Modeling and reasoning about changes in ontology time series. In: Ontologies: a handbook of principles, concepts and applications in information systems, pp 319–338
Keet CM, Artale A (2008) Representing and reasoning over a taxonomy of part-whole relations. Appl Ontol 3: 91–110
Kimelfeld B, Sagiv Y (2006) New algorithms for computing steiner trees for a fixed number of terminals. http://www.cs.huji.ac.il/bennyk/papers/steiner06.pdf
Klein MCA, Fensel D (2001) Ontology versioning on the semantic web. In: SWWS, pp 75–91
Kondylakis H, Plexousakis D (2010) Enabling ontology evolution in data integration. In: EDBT. ACM, New York, pp 38:1–38:7
Konstantinidis G, Flouris G, Antoniou G, Christophides V (2007) On RDF/S ontology evolution. In: SWDB-ODBIS, pp 21–42
Lenzerini M (2002) Data integration: a theoretical perspective. In: PODS, pp 233–246
Lerner BS (2000) A model for compound type changes encountered in schema evolution. TODS 25: 83–127
Mölle D, Richter S, Rossmanith P, Anvertraut MG (2005) A faster algorithm for the steiner tree problem. In: STACS. Springer, Berlin, pp 561–570
Palpanas T, Chaudhry J, Andritsos P, Velegrakis Y (2008) Entity data management in OKKAM. In: SWAP, pp 729–733
Papavassiliou V, Flouris G, Fundulaki I, Kotzinos D, Christophides V (2009) On detecting high-level changes in rdf/s kbs. In: ISWC, pp 473–488
Pérez J, Arenas M, Gutierrez C (2008) nSPARQL: a navigational language for RDF. In: ISWC, pp 66–81
Rizzolo F, Vaisman AA (2008) Temporal XML: modeling, indexing, and query processing. VLDBJ 17: 1179–1212
Rizzolo F, Velegrakis Y, Mylopoulos J, Bykau S (2009) Modeling concept evolution: a historical perspective. In: ER, pp 331–345
Soo MD (1991) Bibliography on temporal databases. SIGMODREC 20: 14–23
Tahmasebi N, Iofciu T, Risse T, Niederee C, Siberski W (2008) Terminology evolution in web archiving: Open issues. In: International Web Archiving Workshop
Velegrakis Y, Miller RJ, Popa L (2004) Preserving mapping consistency under schema changes. VLDB J 13: 274–293
W3C (2004) RDF vocabulary description language 1.0: RDF Schema. http://www.w3.org/TR/rdf-schema/
Author information
Authors and Affiliations
Corresponding author
Rights and permissions
About this article
Cite this article
Bykau, S., Mylopoulos, J., Rizzolo, F. et al. On Modeling and Querying Concept Evolution. J Data Semant 1, 31–55 (2012). https://doi.org/10.1007/s13740-012-0001-1
Received:
Revised:
Accepted:
Published:
Issue Date:
DOI: https://doi.org/10.1007/s13740-012-0001-1