Supporting queries spanning across phases of evolving artifacts using Steiner forests

ABSTRACT

The problem of managing evolving data has attracted considerable research attention. Researchers have focused on the modeling and querying of schema/instance-level structural changes, such as, addition, deletion and modification of attributes. Databases with such a functionality are known as temporal databases. A limitation of the temporal databases is that they treat changes as independent events, while often the appearance (or elimination) of some structure in the database is the result of an evolution of some existing structure. We claim that maintaining the causal relationship between the two structures is of major importance since it allows additional reasoning to be performed and answers to be generated for queries that previously had no answers. We present here a novel framework for exploiting the evolution relationships between the structures in the database. In particular, our system combines different structures that are associated through evolution relationships into virtual structures to be used during query answering. The virtual structures define "possible" database instances, in a fashion similar to the possible worlds in the probabilistic databases. The framework includes a query answering mechanism that allows queries to be answered over these possible databases without materializing them. Evaluation of such queries raises many interesting technical challenges, since it requires the discovery of Steiner forests on the evolution graphs. On this problem we have designed and implemented a new dynamic programming algorithm with exponential complexity in the size of the input query and polynomial complexity in terms of both the attribute and the evolution data sizes.

References

1. J. Banerjee, W. Kim, H. Kim, and H. F. Korth. Semantics and implementation of schema evolution in object-oriented databases. In SIGMOD, pages 311--322, May 1987.
2. Gaurav Bhalotia, Arvind Hulgeri, Charuta Nakhe, Soumen Chakrabarti, and S. Sudarshan. Keyword searching and browsing in databases using banks. In ICDE, pages 431--440, 2002.
3. J. Blakeley, P. A. Larson, and F. W. Tompa. Efficiently Updating Materialized Views. In SIGMOD, pages 61--71, 1986.
4. P. Buneman, S. Khanna, K. Tajima, and W. Tan. Archiving scientific data. In SIGMOD, pages 1--12, 2002.
5. S. Chawathe, S. Abiteboul, and J. Widom. Representing and Querying Changes in Semistructured Data. In ICDE, pages 4--19, 1998.
6. S. Chien, V. J. Tsotras, and C. Zaniolo. Efficient Management of Multiversion Documents by Object Referencing. In VLDB, pages 291--300, 2001.
7. N. N. Dalvi, R. Kumar, B. Pang, R. Ramakrishnan, A. Tomkins, P. Bohannon, S. Keerthi, and S. Merugu. A web of concepts. In PODS, pages 1--12, 2009.
8. Nilesh Dalvi and Dan Suciu. Efficient query evaluation on probabilistic databases. volume 16, pages 523--544, Secaucus, NJ, USA, 2007. Springer-Verlag New York, Inc.
9. Bolin Ding, J Xu Yu, Shan Wang, Lu Qin, Xiao Zhang, and Xuemin Lin. Finding Top-k Min-Cost Connected Trees in Databases. ICDE, pages 836--845, 2007.
10. X. Dong and A. Y. Halevy. Indexing dataspaces. In SIGMOD, pages 43--54, 2007.
11. S E Dreyfus and R A Wagner. The Steiner problem in graphs. Networks, 1(3):195--207, 1972.
12. Elisabeth Gassner. The Steiner Forest Problem revisited. Journal of Discrete Algorithms, 8(2):154--163, June 2010.
13. A. Gupta, I. S. Mumick, and K. A. Ross. Adapting Materialized Views after Redefinitions. In SIGMOD, pages 211--222, 1995.
14. Hao He, Haixun Wang, Jun Yang 0001, and Philip S. Yu. Blinks: ranked keyword searches on graphs. In SIGMOD Conference, pages 305--316, 2007.
15. R. Hull and M. Yoshikawa. ILOG: Declarative Creation and Manipulation of Object Identifiers. In VLDB, pages 455--468, 1990.
16. E. Ioannou, W. Nejdl, C. Niederee, and Y. Velegrakis. OntheFly Entity-Aware Query Processing in the Presence of Linkage. PVLDB, 3(1):429--438, 2010.
17. Richard Johnsonbaugh and Martin Kalin. A graph generation software package. In SIGCSE, pages 151--154, 1991.
18. Varun Kacholia, Shashank Pandit, Soumen Chakrabarti, S. Sudarshan, Rushi Desai, and Hrishikesh Karambelkar. Bidirectional expansion for keyword search on graph databases. In VLDB, pages 505--516, 2005.
19. A. M. Keller. Algorithms for Translating View Updates to Database Updates for Views Involving Selections, Projections, and Joins. SIGMOD, March 1985.
20. B. Kimelfeld and Y. Sagiv. New algorithms for computing steiner trees for a fixed number of terminals. http://www.cs.huji.ac.il/ bennyk/papers/steiner06.pdf.
21. B. S. Lerner. A Model for Compound Type Changes Encountered in Schema Evolution. ACM TODS, 25(1):83--127, March 2000.
22. P. McBrien and A. Poulovassilis. Schema Evolution in Heterogeneous Database Architectures, A Schema Transformation Approach. In CAiSE, pages 484--499, 2002.
23. F. Rizzolo and A. A. Vaisman. Temporal XML: modeling, indexing, and query processing. VLDB Journal, 17(5):1179--1212, 2008.
24. F. Rizzolo, Y. Velegrakis, J. Mylopoulos, and S. Bykau. Modeling Concept Evolution: A Historical Perspective. In ER, pages 331--345, 2009.
25. N. Tahmasebi, T. Iofciu, T. Risse, C. Niederée, and W. Siberski. Terminology Evolution in Web Archiving: Open Issues. In IWAW, Sep 2008.
26. Y. Velegrakis, R. J. Miller, and J. Mylopoulos. Representing and Querying Data Transformations. In ICDE, pages 81--92, 2005.
27. C. Yu and L. Popa. Semantic Adaptation of Schema Mappings when Schemas Evolve. In VLDB, pages 1006--1017, 2005.

Index Terms

• Information systems