TinyDB: an acquisitional query processing system for sensor networks

ABSTRACT

We discuss the design of an acquisitional query processor for data collection in sensor networks. Acquisitional issues are those that pertain to where, when, and how often data is physically acquired (sampled) and delivered to query processing operators. By focusing on the locations and costs of acquiring data, we are able to significantly reduce power consumption over traditional passive systems that assume the a priori existence of data. We discuss simple extensions to SQL for controlling data acquisition, and show how acquisitional issues influence query optimization, dissemination, and execution. We evaluate these issues in the context of TinyDB, a distributed query processor for smart sensor devices, and show how acquisitional techniques can provide significant reductions in power consumption on our sensor devices.

REFERENCES

• 1: Alonso, R. and Ganguly, S. 1993. Query optimization in mobile environments. In Proceedings of the Workshop on Foundations of Models and Languages for Data and Objects. 1--17.
• 2: Rafael Alonso , Henry F. Korth, Database system issues in nomadic computing, Proceedings of the 1993 ACM SIGMOD international conference on Management of data, p.388-392, May 25-28, 1993, Washington, D.C., United States
• 3: Ron Avnur , Joseph M. Hellerstein, Eddies: continuously adaptive query processing, Proceedings of the 2000 ACM SIGMOD international conference on Management of data, p.261-272, May 15-18, 2000, Dallas, Texas, United States
• 4: François Bancilhon , Ted Briggs , Setrag Khoshafian , Patrick Valduriez, FAD, a Powerful and Simple Database Language, Proceedings of the 13th International Conference on Very Large Data Bases, p.97-105, September 01-04, 1987
• 5: Philippe Bonnet , Johannes Gehrke , Praveen Seshadri, Towards Sensor Database Systems, Proceedings of the Second International Conference on Mobile Data Management, p.3-14, January 08-10, 2001
• 6: 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]
• 7: Carney, D., Centiemel, U., Cherniak, M., Convey, C., Lee, S., Seidman, G., Stonebraker, M., Tatbul, N., and Zdonik, S. 2002. Monitoring streams---a new class of data management applications. In Proceedings of VLDB.
• 8: 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]
• 9: Kaushik Chakrabarti , Minos Garofalakis , Rajeev Rastogi , Kyuseok Shim, Approximate query processing using wavelets, The VLDB Journal — The International Journal on Very Large Data Bases, v.10 n.2-3, p.199-223, September 2001
• 10: Sharma Chakravarthy , V. Krishnaprasad , Eman Anwar , S.-K. Kim, Composite Events for Active Databases: Semantics, Contexts and Detection, Proceedings of the 20th International Conference on Very Large Data Bases, p.606-617, September 12-15, 1994
• 11: Chandrasekaran, S., Cooper, O., Deshpande, A., Franklin, M. J., Hellerstein, J. M., Hong, W., Krishnamurthy, S., Madden, S. R., Raman, V., Reiss, F., and Shah, M. A. 2003. TelegraphCQ: Continuous dataflow processing for an uncertain world. In Proceedings of the First Annual Conference on Innovative Database Research (CIDR).
• 12: Jianjun Chen , David J. DeWitt , Feng Tian , Yuan Wang, NiagaraCQ: a scalable continuous query system for Internet databases, Proceedings of the 2000 ACM SIGMOD international conference on Management of data, p.379-390, May 15-18, 2000, Dallas, Texas, United States
• 13: Zhiyuan Chen , Johannes Gehrke , Flip Korn, Query optimization in compressed database systems, Proceedings of the 2001 ACM SIGMOD international conference on Management of data, p.271-282, May 21-24, 2001, Santa Barbara, California, United States
• 14: Arturo Crespo , Hector Garcia-Molina, Routing Indices For Peer-to-Peer Systems, Proceedings of the 22 nd International Conference on Distributed Computing Systems (ICDCS'02), p.23, July 02-05, 2002
• 15: Delin, K. A. and Jackson, S. P. 2000. Sensor web for in situ exploration of gaseous biosignatures. In Proceedings of the IEEE Aerospace Conference.
• 16: D. J. Dewitt , S. Ghandeharizadeh , D. A. Schneider , A. Bricker , H. -I. Hsiao , R. Rasmussen, The Gamma Database Machine Project, IEEE Transactions on Knowledge and Data Engineering, v.2 n.1, p.44-62, March 1990 [doi>10.1109/69.50905]
• 17: Saurabh Ganeriwal , Ram Kumar , Mani B. Srivastava, Timing-sync protocol for sensor networks, Proceedings of the 1st international conference on Embedded networked sensor systems, November 05-07, 2003, Los Angeles, California, USA [doi>10.1145/958491.958508]
• 18: Minos N. Garofalakis , Phillip B. Gibbon, Approximate Query Processing: Taming the TeraBytes, Proceedings of the 27th International Conference on Very Large Data Bases, p.725, September 11-14, 2001
• 19: David Gay , Philip Levis , Robert von Behren , Matt Welsh , Eric Brewer , David Culler, The nesC language: A holistic approach to networked embedded systems, Proceedings of the ACM SIGPLAN 2003 conference on Programming language design and implementation, June 09-11, 2003, San Diego, California, USA
• 20: Johannes Gehrke , Flip Korn , Divesh Srivastava, On computing correlated aggregates over continual data streams, Proceedings of the 2001 ACM SIGMOD international conference on Management of data, p.13-24, May 21-24, 2001, Santa Barbara, California, United States
• 21: Eric N. Hanson, The Design and Implementation of the Ariel Active Database Rule System, IEEE Transactions on Knowledge and Data Engineering, v.8 n.1, p.157-172, February 1996 [doi>10.1109/69.485644]
• 22: Hellerstein, J., Hong, W., Madden, S., and Stanek, K. 2003. Beyond average: Towards sophisticated sensing with queries. In Proceedings of the First Workshop on Information Processing in Sensor Networks (IPSN).
• 23: Joseph M. Hellerstein, Optimization techniques for queries with expensive methods, ACM Transactions on Database Systems (TODS), v.23 n.2, p.113-157, June 1998 [doi>10.1145/292481.277627]
• 24: Hellerstein, J. M., Franklin, M. J., Chandrasekaran, S., Deshpande, A., Hildrum, K., Madden, S., Raman, V., and Shah, M. 2000. Adaptive query processing: Technology in evolution. IEEE Data Eng. Bull. 23, 2, 7--18.
• 25: Jason Hill , Robert Szewczyk , Alec Woo , Seth Hollar , David Culler , Kristofer Pister, System architecture directions for networked sensors, Proceedings of the ninth international conference on Architectural support for programming languages and operating systems, p.93-104, November 2000, Cambridge, Massachusetts, United States
• 26: Toshihide Ibaraki , Tiko Kameda, On the optimal nesting order for computing N-relational joins, ACM Transactions on Database Systems (TODS), v.9 n.3, p.482-502, Sept. 1984 [doi>10.1145/1270.1498]
• 27: Tomasz Imielinski , B. R. Badrinath, Querying in Highly Mobile Distributed Environments, Proceedings of the 18th International Conference on Very Large Data Bases, p.41-52, August 23-27, 1992
• 28: 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]
• 29: Intersema. 2002. MS5534A barometer module. Tech. rep. (Oct.). Go online to http://www.intersema.com/pro/module/file/da5534.pdf.
• 30: Zachary G. Ives , Daniela Florescu , Marc Friedman , Alon Levy , Daniel S. Weld, An adaptive query execution system for data integration, Proceedings of the 1999 ACM SIGMOD international conference on Management of data, p.299-310, May 31-June 03, 1999, Philadelphia, Pennsylvania, United States
• 31: Donald Kossmann, The state of the art in distributed query processing, ACM Computing Surveys (CSUR), v.32 n.4, p.422-469, Dec. 2000 [doi>10.1145/371578.371598]
• 32: Ravi Krishnamurthy , Haran Boral , Carlo Zaniolo, Optimization of Nonrecursive Queries, Proceedings of the 12th International Conference on Very Large Data Bases, p.128-137, August 25-28, 1986
• 33: Martin Leopold , Mads Bondo Dydensborg , Philippe Bonnet, Bluetooth and sensor networks: a reality check, Proceedings of the 1st international conference on Embedded networked sensor systems, November 05-07, 2003, Los Angeles, California, USA [doi>10.1145/958491.958504]
• 34: Lin, C., Federspiel, C., and Auslander, D. 2002. Multi-sensor single actuator control of HVAC systems. In Proceedings of the International Conference for Enhanced Building Operations (Austin, TX, Oct. 14--18).
• 35: Ling Liu , Calton Pu , Wei Tang, Continual Queries for Internet Scale Event-Driven Information Delivery, IEEE Transactions on Knowledge and Data Engineering, v.11 n.4, p.610-628, July 1999 [doi>10.1109/69.790816]
• 36: Samuel Ross Madden , Michael J. Franklin, The design and evaluation of a query processing architecture for sensor networks, University of California at Berkeley, Berkeley, CA, 2003
• 37: Fjording the Stream: An Architecture for Queries Over Streaming Sensor Data, Proceedings of the 18th International Conference on Data Engineering, p.555, February 26-March 01, 2002
• 38: Samuel Madden , Michael J. Franklin , Joseph M. Hellerstein , Wei Hong, TAG: a Tiny AGgregation service for Ad-Hoc sensor networks, Proceedings of the 5th symposium on Operating systems design and implementation

  Due to copyright restrictions we are not able to make the PDFs for this conference available for downloading

  , December 09-11, 2002, Boston, Massachusetts [doi>10.1145/1060289.1060303]
• 39: Madden, S., Hong, W., Franklin, M., and Hellerstein, J. M. 2003. TinyDB Web page. Go online to http://telegraph.cs.berkeley.edu/tinydb.
• 40: Samuel Madden , Mehul Shah , Joseph M. Hellerstein , Vijayshankar Raman, Continuously adaptive continuous queries over streams, Proceedings of the 2002 ACM SIGMOD international conference on Management of data, June 03-06, 2002, Madison, Wisconsin [doi>10.1145/564691.564698]
• 41: 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]
• 42: Melexis, Inc. 2002. MLX90601 infrared thermopile module. Tech. rep. (Aug.). Go online to http://www.melexis.com/prodfiles/mlx90601.pdf.
• 43: Monma, C. L. and Sidney, J. 1979. Sequencing with series parallel precedence constraints. Math. Operat. Rese. 4, 215--224.
• 44: Motwani, R., Widom, J., Arasu, A., Babcock, B., S.Babu, Data, M., Olston, C., Rosenstein, J., and Varma, R. 2003. Query processing, approximation and resource management in a data stream management system. In Proceedings of the First Annual Conference on Innovative Database Research (CIDR).
• 45: Chris Olston , Jennifer Widom, Best-effort cache synchronization with source cooperation, Proceedings of the 2002 ACM SIGMOD international conference on Management of data, June 03-06, 2002, Madison, Wisconsin [doi>10.1145/564691.564701]
• 46: Hamid Pirahesh , Joseph M. Hellerstein , Waqar Hasan, Extensible/rule based query rewrite optimization in Starburst, Proceedings of the 1992 ACM SIGMOD international conference on Management of data, p.39-48, June 02-05, 1992, San Diego, California, United States
• 47: G. J. Pottie , W. J. Kaiser, Wireless integrated network sensors, Communications of the ACM, v.43 n.5, p.51-58, May 2000 [doi>10.1145/332833.332838]
• 48: Nissanka B. Priyantha , Anit Chakraborty , Hari Balakrishnan, The Cricket location-support system, Proceedings of the 6th annual international conference on Mobile computing and networking, p.32-43, August 06-11, 2000, Boston, Massachusetts, United States [doi>10.1145/345910.345917]
• 49: Vijayshankar Raman , Bhaskaran Raman , Joseph M. Hellerstein, Online dynamic reordering, The VLDB Journal — The International Journal on Very Large Data Bases, v.9 n.3, p.247-260, December 2000 [doi>10.1007/s007780000032]
• 50: Sensirion. 2002. SHT11/15 relative humidity sensor. Tech. rep. (June). Go online to http://www.sensirion.com/en/pdf/Datasheet_SHT1x_SHT7x_0206.pdf.
• 51: Ambuj Shatdal , Jeffrey F. Naughton, Adaptive parallel aggregation algorithms, Proceedings of the 1995 ACM SIGMOD international conference on Management of data, p.104-114, May 22-25, 1995, San Jose, California, United States
• 52: Michael Stonebraker , Greg Kemnitz, The POSTGRES next generation database management system, Communications of the ACM, v.34 n.10, p.78-92, Oct. 1991 [doi>10.1145/125223.125262]
• 53: S. Sudarshan , Raghu Ramakrishnan, Aggregation and Relevance in Deductive Databases, Proceedings of the 17th International Conference on Very Large Data Bases, p.501-511, September 03-06, 1991
• 54: TAOS, Inc. 2002. TSL2550 ambient light sensor. Tech. rep. (Sep.). Go online to http://www.taosinc.com/images/product/document/tsl2550.pdf.
• 55: UC Berkeley. 2001. Smart buildings admit their faults. Web page. Lab notes: Research from the College of Engineering, UC Berkeley. Go online to http://coe.berkeley.edu/labnotes/1101.smartbuildings.html.
• 56: Tolga Urhan , Michael J. Franklin , Laurent Amsaleg, Cost-based query scrambling for initial delays, Proceedings of the 1998 ACM SIGMOD international conference on Management of data, p.130-141, June 01-04, 1998, Seattle, Washington, United States
• 57: Ouri Wolfson , Prasad Sistla , Bo Xu , Jutai Zhou , Sam Chamberlain, DOMINO: databases fOr MovINg Objects tracking, Proceedings of the 1999 ACM SIGMOD international conference on Management of data, p.547-549, May 31-June 03, 1999, Philadelphia, Pennsylvania, United States
• 58: Alec Woo , David E. Culler, A transmission control scheme for media access in sensor networks, Proceedings of the 7th annual international conference on Mobile computing and networking, p.221-235, July 2001, Rome, Italy [doi>10.1145/381677.381699]
• 59: Yong Yao , Johannes Gehrke, The cougar approach to in-network query processing in sensor networks, ACM SIGMOD Record, v.31 n.3, September 2002 [doi>10.1145/601858.601861]

INDEX TERMS

Primary Classification:
  H. Information Systems
  H.2 DATABASE MANAGEMENT
      H.2.3 Languages
          Subjects: Query languages

Additional Classification:
  H. Information Systems
  H.2 DATABASE MANAGEMENT
      H.2.4 Systems
          Subjects: Query processing; Distributed databases

  I. Computing Methodologies
  I.2 ARTIFICIAL INTELLIGENCE
      I.2.9 Robotics
          Subjects: Sensors

Keywords:
Query processing, data acquisition, sensor networks