MauveDB: supporting model-based user views in database systems

ABSTRACT

Real-world data --- especially when generated by distributed measurement infrastructures such as sensor networks --- tends to be incomplete, imprecise, and erroneous, making it impossible to present it to users or feed it directly into applications. The traditional approach to dealing with this problem is to first process the data using statistical or probabilistic models that can provide more robust interpretations of the data. Current database systems, however, do not provide adequate support for applying models to such data, especially when those models need to be frequently updated as new data arrives in the system. Hence, most scientists and engineers who depend on models for managing their data do not use database systems for archival or querying at all; at best, databases serve as a persistent raw data store.In this paper we define a new abstraction called model-based views and present the architecture of MauveDB, the system we are building to support such views. Just as traditional database views provide logical data independence, model-based views provide independence from the details of the underlying data generating mechanism and hide the irregularities of the data by using models to present a consistent view to the users. MauveDB supports a declarative language for defining model-based views, allows declarative querying over such views using SQL, and supports several different materialization strategies and techniques to efficiently maintain them in the face of frequent updates. We have implemented a prototype system that currently supports views based on regression and interpolation, using the Apache Derby open source DBMS, and we present results that show the utility and performance benefits that can be obtained by supporting several different types of model-based views in a database system.

REFERENCES

• 1: I. F. Akyildiz , W. Su , Y. Sankarasubramaniam , E. Cayirci, Wireless sensor networks: a survey, Computer Networks: The International Journal of Computer and Telecommunications Networking, v.38 n.4, p.393-422, 15 March 2002 [doi>10.1016/S1389-1286(01)00302-4]
• 2: Periklis Andritsos , Ariel Fuxman , Renee J. Miller, Clean Answers over Dirty Databases: A Probabilistic Approach, Proceedings of the 22nd International Conference on Data Engineering (ICDE'06), p.30, April 03-07, 2006 [doi>10.1109/ICDE.2006.35]
• 3: The Apache Derby Project. Web Site. http://db.apache.org/derby/.
• 4: D. Barbará , H. Garcia-Molina , D. Porter, The Management of Probabilistic Data, IEEE Transactions on Knowledge and Data Engineering, v.4 n.5, p.487-502, October 1992 [doi>10.1109/69.166990]
• 5: Tim Brooke , Jenna Burrell, From ethnography to design in a vineyard, Proceedings of the 2003 conference on Designing for user experiences, June 06-07, 2003, San Francisco, California [doi>10.1145/997078.997083]
• 6: Alberto Cerpa , Jeremy Elson , Michael Hamilton , Jerry Zhao , Deborah Estrin , Lewis Girod, Habitat monitoring: application driver for wireless communications technology, Workshop on Data communication in Latin America and the Caribbean, p.20-41, April 2001, San Jose, Costa Rica [doi>10.1145/371626.371720]
• 7: Efficient Evaluation of Queries with Mining Predicates, Proceedings of the 18th International Conference on Data Engineering, p.529, February 26-March 01, 2002
• 8: Reynold Cheng , Dmitri V. Kalashnikov , Sunil Prabhakar, Evaluating probabilistic queries over imprecise data, Proceedings of the 2003 ACM SIGMOD international conference on Management of data, June 09-12, 2003, San Diego, California [doi>10.1145/872757.872823]
• 9: M. Chu, H. Haussecker, and F. Zhao. Scalable information-driven sensor querying and routing for ad hoc heterogeneous sensor networks. In Intl Journal of High Performance Computing Applications, 2002.
• 10: Nilesh N. Dalvi and Dan Suciu. Efficient query evaluation on probabilistic databases. In VLDB, 2004.
• 11: Dorothy E. Denning , Selim G. Akl , Mark Heckman , Teresa F. Lunt , Matthew Morgenstern , Peter G. Neumann , Roger R. Schell, Views for multilevel database security, IEEE Transactions on Software Engineering, v.13 n.2, p.129-140, Feb. 1987 [doi>10.1109/TSE.1987.232889]
• 12: Amol Deshpande, Carlos Guestrin, Sam Madden, Joe Hellerstein, and Wei Hong. Model-driven data acquisition in sensor networks. In VLDB, 2004.
• 13: Norbert Fuhr , Thomas Rölleke, A probabilistic relational algebra for the integration of information retrieval and database systems, ACM Transactions on Information Systems (TOIS), v.15 n.1, p.32-66, Jan. 1997 [doi>10.1145/239041.239045]
• 14: G. Golub and C. Van Loan. Matrix Computations. Johns Hopkins, 1989.
• 15: G. Grahne, Horn tables-an efficient tool for handling incomplete information in databases, Proceedings of the eighth ACM SIGACT-SIGMOD-SIGART symposium on Principles of database systems, p.75-82, March 1989, Philadelphia, Pennsylvania, United States [doi>10.1145/73721.73728]
• 16: Stéphane Grumbach , Philippe Rigaux , Luc Segoufin, Manipulating Interpolated Data is Easier than You Thought, Proceedings of the 26th International Conference on Very Large Data Bases, p.156-165, September 10-14, 2000
• 17: Carlos Guestrin , Peter Bodi , Romain Thibau , Mark Paski , Samuel Madde, Distributed regression: an efficient framework for modeling sensor network data, Proceedings of the third international symposium on Information processing in sensor networks, April 26-27, 2004, Berkeley, California, USA [doi>10.1145/984622.984624]
• 18: Ashish Gupta , Iderpal Singh Mumick, Materialized views: techniques, implementations, and applications, MIT Press, Cambridge, MA, 1999
• 19: David J. Hand , Padhraic Smyth , Heikki Mannila, Principles of data mining, MIT Press, Cambridge, MA, 2001
• 20: DB2 Intelligent Miner. Web Site. http://www-306.ibm.com/software/data/iminer/.
• 21: Tomasz Imieliński , Witold Lipski, Jr., Incomplete Information in Relational Databases, Journal of the ACM (JACM), v.31 n.4, p.761-791, Oct. 1984 [doi>10.1145/1634.1886]
• 22: Chalermek Intanagonwiwat , Ramesh Govindan , Deborah Estrin, Directed diffusion: a scalable and robust communication paradigm for sensor networks, Proceedings of the 6th annual international conference on Mobile computing and networking, p.56-67, August 06-11, 2000, Boston, Massachusetts, United States [doi>10.1145/345910.345920]
• 23: Ankur Jain , Edward Y. Chang , Yuan-Fang Wang, Adaptive stream resource management using Kalman Filters, Proceedings of the 2004 ACM SIGMOD international conference on Management of data, June 13-18, 2004, Paris, France [doi>10.1145/1007568.1007573]
• 24: Laks V. S. Lakshmanan , Nicola Leone , Robert Ross , V. S. Subrahmanian, ProbView: a flexible probabilistic database system, ACM Transactions on Database Systems (TODS), v.22 n.3, p.419-469, Sept. 1997 [doi>10.1145/261124.261131]
• 25: Suk Kyoon Lee, An Extended Relational Database Model for Uncertain and Imprecise Information, Proceedings of the 18th International Conference on Very Large Data Bases, p.211-220, August 23-27, 1992
• 26: L. Liao, D. Fox, and H. Kautz. Location-based activity recognition using relational markov networks. In IJCAI, 2005.
• 27: Sam Madden. Intel lab data, 2004. http://berkeley.intel-research.net/labdata.
• 28: Samuel Madden, Wei Hong, Joseph M. Hellerstein, and Michael Franklin. TinyDB web page. http://telegraph.cs.berkeley.edu/tinydb.
• 29: Alan Mainwaring , David Culler , Joseph Polastre , Robert Szewczyk , John Anderson, Wireless sensor networks for habitat monitoring, Proceedings of the 1st ACM international workshop on Wireless sensor networks and applications, September 28-28, 2002, Atlanta, Georgia, USA [doi>10.1145/570738.570751]
• 30: Erin McKean, editor. The Oxford English Dictionary (2nd Edition). Oxford Univeristy Press, 2005.
• 31: Leonore Neugebauer, Optimization and evaluation of database queries including embedded interpolation procedures, Proceedings of the 1991 ACM SIGMOD international conference on Management of data, p.118-127, May 29-31, 1991, Denver, Colorado, United States
• 32: George M. Phillips. Interpolation and Approximation by Polynomials. Springer-Verlag, 2003.
• 33: PMML 3.0 Specification. Web Site. http://www.dmg.org/v3-0/GeneralStructure.html.
• 34: Sunita Sarawagi , Shiby Thomas , Rakesh Agrawal, Integrating association rule mining with relational database systems: alternatives and implications, Proceedings of the 1998 ACM SIGMOD international conference on Management of data, p.343-354, June 01-04, 1998, Seattle, Washington, United States
• 35: Business Analytics Software Solutions (SAS). Web Site. http://www.sas.com/technologies/analytics.
• 36: J. Widom. Trio: A system for integrated management of data, accuracy, and lineage. In CIDR, 2005.
• 37: Yuni Xia , Sunil Prabhakar , Shan Lei , Reynold Cheng , Rahul Shah, Indexing continuously changing data with mean-variance tree, Proceedings of the 2005 ACM symposium on Applied computing, March 13-17, 2005, Santa Fe, New Mexico [doi>10.1145/1066677.1066932]
• 38: Y. Yao and J. Gehrke. Query processing in sensor networks. In CIDR, 2003.

INDEX TERMS

Primary Classification:
  H. Information Systems
  H.2 DATABASE MANAGEMENT
      H.2.0 General

General Terms:
Design, Languages, Performance

Keywords:
query processing, regression, sensor networks, statistical models, uncertain data, views