skip to main content
article

TinyDB: an acquisitional query processing system for sensor networks

Published: 01 March 2005 Publication History

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]
Alonso, R. and Korth, H. F. 1993. Database system issues in nomadic computing. In Proceedings of the ACM SIGMOD (Washington, DC).]]
[3]
Avnur, R. and Hellerstein, J. M. 2000. Eddies: Continuously adaptive query processing. In Proceedings of ACM SIGMOD (Dallas, TX). 261--272.]]
[4]
Bancilhon, F., Briggs, T., Khoshafian, S., and Valduriez, P. 1987. FAD, a powerful and simple database language. In Proceedings of VLDB.]]
[5]
Bonnet, P., Gehrke, J., and Seshadri, P. 2001. Towards sensor database systems. In Proceedings of the Conference on Mobile Data Management.]]
[6]
Brooke, T. and Burrell, J. 2003. From ethnography to design in a vineyard. In Proceedings of the Design User Experiences (DUX) Conference. Case study.]]
[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]
Cerpa, A., Elson, J., D. Estrin, Girod, L., Hamilton, M., and Zhao, J. 2001. Habitat monitoring: Application driver for wireless communications technology. In Proceedings of ACM SIGCOMM Workshop on Data Communications in Latin America and the Caribbean.]]
[9]
Chakrabarti, K., Garofalakis, M., Rastogi, R., and Shim, K. 2001. Approximate query processing using wavelets. VLDB J. 10, 2-3 (Sep.), 199--223.]]
[10]
Chakravarthy, S., Krishnaprasad, V., Anwar, E., and Kim, S. K. 1994. Composite events for active databases: Semantics, contexts and detection. In Proceedings of VLDB.]]
[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]
Chen, J., DeWitt, D., Tian, F., and Wang, Y. 2000. NiagaraCQ: A scalable continuous query system for internet databases. In Proceedings of ACM SIGMOD.]]
[13]
Chen, Z., Gehrke, J., and Korn, F. 2001. Query optimization in compressed database systems. In Proceedings of ACM SIGMOD.]]
[14]
Crespo, A. and Garcia-Molina, H. 2002. Routing indices for peer-to-peer systems. In Proceedings of ICDCS.]]
[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]
Dewitt, D. J., Ghandeharizadeh, S., Schneider, D. A., Bricker, A., Hsiao, H. I., and Rasmussen, R. 1990. The gamma database machine project. IEEE Trans. Knowl. Data Eng. 2, 1, 44--62.]]
[17]
Ganeriwal, S., Kumar, R., Adlakha, S., and Srivastava, M. 2003. Timing-sync protocol for sensor networks. In Proceedings of ACM SenSys.]]
[18]
Garofalakis, M. and Gibbons, P. 2001. Approximate query processing: Taming the terabytes! (tutorial). In Proceedings of VLDB.]]
[19]
Gay, D., Levis, P., von Behren, R., Welsh, M., Brewer, E., and Culler, D. 2003. The nesC language: A holistic approach to network embedded systems. In Proceedings of the ACM SIGPLAN 2003 Conference on Programming Language Design and Implementation (PLDI).]]
[20]
Gehrke, J., Korn, F., and Srivastava, D. 2001. On computing correlated aggregates over continual data streams. In Proceedings of ACM SIGMOD Conference on Management of Data (Santa Barbara, CA).]]
[21]
Hanson, E. N. 1996. The design and implementation of the ariel active database rule system. IEEE Trans. Knowl. Data Eng. 8, 1 (Feb.), 157--172.]]
[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]
Hellerstein, J. M. 1998. Optimization techniques for queries with expensive methods. ACM Trans. Database Syst. 23, 2, 113--157.]]
[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]
Hill, J., Szewczyk, R., Woo, A., Hollar, S., and Pister, D. C. K. 2000. System architecture directions for networked sensors. In Proceedings of ASPLOS.]]
[26]
Ibaraki, T. and Kameda, T. 1984. On the optimal nesting order for computing n-relational joins. ACM Trans. Database Syst. 9, 3, 482--502.]]
[27]
Imielinski, T. and Badrinath, B. 1992. Querying in highly mobile distributed environments. In Proceedings of VLDB (Vancouver, B.C., Canada).]]
[28]
Intanagonwiwat, C., Govindan, R., and Estrin, D. 2000. Directed diffusion: A scalable and robust communication paradigm for sensor networks. In Proceedings of MobiCOM (Boston, MA).]]
[29]
Intersema. 2002. MS5534A barometer module. Tech. rep. (Oct.). Go online to http://www.intersema.com/pro/module/file/da5534.pdf.]]
[30]
Ives, Z. G., Florescu, D., Friedman, M., Levy, A., and Weld, D. S. 1999. An adaptive query execution system for data integration. In Proceedings of ACM SIGMOD.]]
[31]
Kossman, D. 2000. The state of the art in distributed query processing. ACM Comput. Surv. 32, 4 (Dec.), 422--46.]]
[32]
Krishnamurthy, R., Boral, H., and Zaniolo, C. 1986. Optimization of nonrecursive queries. In Proceedings of VLDB. 128--137.]]
[33]
Leopold, M., Dydensborg, M., and Bonnet, P. 2003. Bluetooth and sensor networks: A reality check. In Proceedings of ACM Conference on Sensor Networks (SenSys).]]
[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]
Liu, L., Pu, C., and Tang, W. 1999. Continual queries for internet-scale event-driven information delivery. IEEE Trans. Knowl. Data Eng. (special Issue on Web technology) 11, 4 (July), 610--628.]]
[36]
Madden, S. 2003. The design and evaluation of a query processing architecture for sensor networks. Ph.D. dissertation. University of California, Berkeley, Berkeley, CA.]]
[37]
Madden, S. and Franklin, M. J. 2002. Fjording the stream: An architechture for queries over streaming sensor data. In Proceedings of ICDE.]]
[38]
Madden, S., Franklin, M. J., Hellerstein, J. M., and Hong, W. 2002a. TAG: A Tiny AGgregation service for ad-hoc sensor networks. In Proceedings of OSDI.]]
[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]
Madden, S., Shah, M. A., Hellerstein, J. M., and Raman, V. 2002b. Continously adaptive continuous queries over data streams. In Proceedings of ACM SIGMOD (Madison, WI).]]
[41]
Mainwaring, A., Polastre, J., Szewczyk, R., and Culler, D. 2002. Wireless sensor networks for habitat monitoring. In Proceedings of ACM Workshop on Sensor Networks and Applications.]]
[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]
Olston, C. and Widom, J. 2002. In best effort cache sychronization with source cooperation. In Proceedings of SIGMOD.]]
[46]
Pirahesh, H., Hellerstein, J. M., and Hasan, W. 1992. Extensible/rule based query rewrite optimization in starburst. In Proceedings of ACM SIGMOD. 39--48.]]
[47]
Pottie, G. and Kaiser, W. 2000. Wireless integrated network sensors. Commun. ACM 43, 5 (May), 51--58.]]
[48]
Priyantha, N. B., Chakraborty, A., and Balakrishnan, H. 2000. The cricket location-support system. In Proceedings of MOBICOM.]]
[49]
Raman, V., Raman, B., and Hellerstein, J. M. 2002. Online dynamic reordering. VLDB J. 9, 3.]]
[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]
Shatdal, A. and Naughton, J. 1995. Adaptive parallel aggregation algorithms. In Proceedings of ACM SIGMOD.]]
[52]
Stonebraker, M. and Kemnitz, G. 1991. The POSTGRES next-generation database management system. Commun. ACM 34, 10, 78--92.]]
[53]
Sudarshan, S. and Ramakrishnan, R. 1991. Aggregation and relevance in deductive databases. In Proceedings of VLDB. 501--511.]]
[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]
Urhan, T., Franklin, M. J., and Amsaleg, L. 1998. Cost-based query scrambling for initial delays. In Proceedings of ACM SIGMOD.]]
[57]
Wolfson, O., Sistla, A. P., Xu, B., Zhou, J., and Chamberlain, S. 1999. DOMINO: Databases fOr MovINg Objects tracking. In Proceedings of ACM SIGMOD (Philadelphia, PA).]]
[58]
Woo, A. and Culler, D. 2001. A transmission control scheme for media access in sensor networks. In Proceedings of ACM Mobicom.]]
[59]
Yao, Y. and Gehrke, J. 2002. The cougar approach to in-network query processing in sensor networks. In SIGMOD Rec. 13, 3 (Sept.), 9--18.]]

Cited By

View all
  • (2025)Parameters security strategy formulated by hyperchaos in federal learningApplied Intelligence10.1007/s10489-024-06209-z55:4Online publication date: 2-Jan-2025
  • (2024)The impact of distributed systems on the architecture and design of computer systems: advantages and challengesData and Metadata10.56294/dm2024.2253Online publication date: 26-Dec-2024
  • (2024)Efficient Placement of Decomposable Aggregation Functions for Stream Processing over Large Geo-Distributed TopologiesProceedings of the VLDB Endowment10.14778/3648160.364818617:6(1501-1514)Online publication date: 1-Feb-2024
  • Show More Cited By

Recommendations

Reviews

Lia-Maria Pasculescu

The acquisitional query processing system for sensor networks described in this paper is a new development in the field of acquisitional query languages. Running on the Berkeley "mote" platform, on top of an operating system called TinyOS, TinyDB is a query processor designed for sensor networks that has control over "where, when and how often data is physically acquired." The discussion starts with a presentation of the sensor devices and their power consumption, the operating system running on these sensor devices (TinyOS), and the communication inside sensor networks. On these sensor devices, on top of TinyOS, there is an acquisitional query language running, called TinyDB, that collects data in the form of sensor tuples. TinyDB uses basic structured query language (SQL) with extensions that deal with the particularities of the sensor devices, mainly the sample period (the time between the moment when the nodes initiate the data collection and transmission in a real-time fashion, and when they stop the transmission). Other extensions to the classic SQL used inside TinyDB concern the aggregation queries, and also event-based queries (where the events are those mechanisms that initiate data collection). The lifetime-based queries will be useful in environmental monitoring scenarios, where scientists are concerned with the duration of the network. The model of TinyDB uses a cost-based optimizer to choose a query plan that will require the lowest degree of power consumption. This is accomplished by the use of a catalog of metadata describing the node's local attributes, events, and user-defined functions. Next, the paper describes the dissemination of the query into the network. The query begins with a broadcast from the root of the network. Each node listens to the query, and must decide if it applies locally, or needs to be further broadcast to its children. This decision is based on a new data structure proposed by the authors: a semantic routing tree. This routing tree allows each node to efficiently determine if its children need to participate in a given query. Finally, the authors present details on query execution, prioritizing data, and adapting sampling and delivery rates. Using techniques like snooping, TinyDB can still transmit the most relevant results when the power or bandwidth is limited. Although the paper is very interesting, and describes the newest techniques in data acquisition and processing, its audience is quite limited; it is mainly intended for those scientists and researchers who implement and supervise battery-powered sensing devices. Online Computing Reviews Service

Access critical reviews of Computing literature here

Become a reviewer for Computing Reviews.

Comments

Information & Contributors

Information

Published In

cover image ACM Transactions on Database Systems
ACM Transactions on Database Systems  Volume 30, Issue 1
Special Issue: SIGMOD/PODS 2003
March 2005
332 pages
ISSN:0362-5915
EISSN:1557-4644
DOI:10.1145/1061318
Issue’s Table of Contents

Publisher

Association for Computing Machinery

New York, NY, United States

Publication History

Published: 01 March 2005
Published in TODS Volume 30, Issue 1

Permissions

Request permissions for this article.

Check for updates

Author Tags

  1. Query processing
  2. data acquisition
  3. sensor networks

Qualifiers

  • Article

Contributors

Other Metrics

Bibliometrics & Citations

Bibliometrics

Article Metrics

  • Downloads (Last 12 months)120
  • Downloads (Last 6 weeks)10
Reflects downloads up to 27 Jan 2025

Other Metrics

Citations

Cited By

View all
  • (2025)Parameters security strategy formulated by hyperchaos in federal learningApplied Intelligence10.1007/s10489-024-06209-z55:4Online publication date: 2-Jan-2025
  • (2024)The impact of distributed systems on the architecture and design of computer systems: advantages and challengesData and Metadata10.56294/dm2024.2253Online publication date: 26-Dec-2024
  • (2024)Efficient Placement of Decomposable Aggregation Functions for Stream Processing over Large Geo-Distributed TopologiesProceedings of the VLDB Endowment10.14778/3648160.364818617:6(1501-1514)Online publication date: 1-Feb-2024
  • (2024)Databases in Edge and Fog Environments: A SurveyACM Computing Surveys10.1145/366600156:11(1-40)Online publication date: 8-Jul-2024
  • (2024)Fault Tolerance Placement in the Internet of ThingsProceedings of the ACM on Management of Data10.1145/36549412:3(1-29)Online publication date: 30-May-2024
  • (2024)Managing Metaverse Data Tsunami: Actionable InsightsIEEE Transactions on Knowledge and Data Engineering10.1109/TKDE.2024.335496036:12(7423-7441)Online publication date: 1-Dec-2024
  • (2024)A Heterogeneous Streaming Vehicle Data Access Model for Diverse IoT Sensor Monitoring Network ManagementIEEE Internet of Things Journal10.1109/JIOT.2024.338449311:16(26929-26943)Online publication date: 15-Aug-2024
  • (2024)Geo-Distributed Analytical Streaming Architecture for IoT Platforms2024 IEEE International Conference on Cluster Computing (CLUSTER)10.1109/CLUSTER59578.2024.00030(263-274)Online publication date: 24-Sep-2024
  • (2023)In-Network Processing of Skyline Join Queries in Wireless Sensor Networks Using Synopses of Skyline Attribute Value RangesSensors10.3390/s2306302223:6(3022)Online publication date: 10-Mar-2023
  • (2023)Towards Optimal Moment Estimation in Streaming and Distributed ModelsACM Transactions on Algorithms10.1145/359649419:3(1-35)Online publication date: 24-Jun-2023
  • Show More Cited By

View Options

Login options

Full Access

View options

PDF

View or Download as a PDF file.

PDF

eReader

View online with eReader.

eReader

Figures

Tables

Media

Share

Share

Share this Publication link

Share on social media