Cache-and-query for wide area sensor databases

ABSTRACT

Webcams, microphones, pressure gauges and other sensors provide exciting new opportunities for querying and monitoring the physical world. In this paper we focus on querying wide area sensor databases, containing (XML) data derived from sensors spread over tens to thousands of miles. We present the first scalable system for executing XPATH queries on such databases. The system maintains the logical view of the data as a single XML document, while physically the data is fragmented across any number of host nodes. For scalability, sensor data is stored close to the sensors, but can be cached elsewhere as dictated by the queries. Our design enables self starting distributed queries that jump directly to the lowest common ancestor of the query result, dramatically reducing query response times. We present a novel query-evaluate gather technique (using XSLT) for detecting (1) which data in a local database fragment is part of the query result, and (2) how to gather the missing parts. We define partitioning and cache invariants that ensure that even partial matches on cached data are exploited and that correct answers are returned, despite our dynamic query-driven caching. Experimental results demonstrate that our techniques dramatically increase query throughputs and decrease query response times in wide area sensor databases.

REFERENCES

• 1: Apache Xindice Database. http://www.dbxml.org.
• 2: Xalan-Java. http://xml.apache.org/xalan-j.
• 3: Serge Abiteboul , Jason McHugh , Michael Rys , Vasilis Vassalos , Janet L. Wiener, Incremental Maintenance for Materialized Views over Semistructured Data, Proceedings of the 24rd International Conference on Very Large Data Bases, p.38-49, August 24-27, 1998
• 4: D. Agrawal , S. Sengupta, Modular Synchronization in Distributed, Multiversion Databases: Version Control and Concurrency Control, IEEE Transactions on Knowledge and Data Engineering, v.5 n.1, p.126-137, February 1993 [doi>10.1109/69.204097]
• 5: Rafael Alonso , Daniel Barbara , Hector Garcia-Molina, Data caching issues in an information retrieval system, ACM Transactions on Database Systems (TODS), v.15 n.3, p.359-384, Sept. 1990 [doi>10.1145/88636.87848]
• 6: Robert D. Blumofe , Christopher F. Joerg , Bradley C. Kuszmaul , Charles E. Leiserson , Keith H. Randall , Yuli Zhou, Cilk: an efficient multithreaded runtime system, Proceedings of the fifth ACM SIGPLAN symposium on Principles and practice of parallel programming, p.207-216, July 19-21, 1995, Santa Barbara, California, United States
• 7: 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
• 8: M. J. Carey et al. XPERANTO: Publishing object-relational data as XML. In WebDB, 2000.
• 9: D. Carney et al. Monitoring streams - A new class of data management applications. In VLDB, 2002.
• 10: S. Chandrasekaran et al. TelegraphCQ: Continuous dataflow processing for an uncertain world. In CIDR, 2003.
• 11: 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
• 12: Armando Fox , Steven D. Gribble , Yatin Chawathe , Eric A. Brewer , Paul Gauthier, Cluster-based scalable network services, Proceedings of the sixteenth ACM symposium on Operating systems principles, p.78-91, October 05-08, 1997, Saint Malo, France
• 13: M. Franklin and M. Carey. Client-server caching revisited. In International Workshop on Distributed Object Management, 1992.
• 14: Goetz Graefe, Query evaluation techniques for large databases, ACM Computing Surveys (CSUR), v.25 n.2, p.73-169, June 1993 [doi>10.1145/152610.152611]
• 15: Jim Gray , Pat Helland , Patrick O'Neil , Dennis Shasha, The dangers of replication and a solution, Proceedings of the 1996 ACM SIGMOD international conference on Management of data, p.173-182, June 04-06, 1996, Montreal, Quebec, Canada
• 16: S. Gribble, A. Halevy, Z. Ives, M. Rodrig, and D. Suciu. What can databases do for peer-to-peer. In WebDB, 2001.
• 17: Matthew Harren , Joseph M. Hellerstein , Ryan Huebsch , Boon Thau Loo , Scott Shenker , Ion Stoica, Complex Queries in DHT-based Peer-to-Peer Networks, Revised Papers from the First International Workshop on Peer-to-Peer Systems, p.242-259, March 07-08, 2002
• 18: Panos Kalnis , Wee Siong Ng , Beng Chin Ooi , Dimitris Papadias , Kian-Lee Tan, An adaptive peer-to-peer network for distributed caching of OLAP results, Proceedings of the 2002 ACM SIGMOD international conference on Management of data, June 03-06, 2002, Madison, Wisconsin [doi>10.1145/564691.564695]
• 19: David Karger , Eric Lehman , Tom Leighton , Rina Panigrahy , Matthew Levine , Daniel Lewin, Consistent hashing and random trees: distributed caching protocols for relieving hot spots on the World Wide Web, Proceedings of the twenty-ninth annual ACM symposium on Theory of computing, p.654-663, May 04-06, 1997, El Paso, Texas, United States [doi>10.1145/258533.258660]
• 20: Meike Klettke , Holger Meyer, XML and Object-Relational Database Systems - Enhancing Structural Mappings Based on Statistics, Selected papers from the Third International Workshop WebDB 2000 on The World Wide Web and Databases, p.151-170, May 18-19, 2000
• 21: Narayanan Krishnakumar , Arthur J. Bernstein, Bounded ignorance in replicated systems, Proceedings of the tenth ACM SIGACT-SIGMOD-SIGART symposium on Principles of database systems, p.63-74, May 29-31, 1991, Denver, Colorado, United States [doi>10.1145/113413.113419]
• 22: S. Madden and M. J. Franklin. Fjording the stream: An architecture for queries over streaming sensor data. In ICDE, 2002.
• 23: 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]
• 24: P. Mockapetris , K. J. Dunlap, Development of the domain name system, Symposium proceedings on Communications architectures and protocols, p.123-133, August 16-18, 1988, Stanford, California, United States
• 25: R. Motwani et al. Query processing, approximation, and resource management in a data stream management system. In CIDR, 2003.
• 26: 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]
• 27: Calton Pu , Avraham Leff, Replica control in distributed systems: as asynchronous approach, Proceedings of the 1991 ACM SIGMOD international conference on Management of data, p.377-386, May 29-31, 1991, Denver, Colorado, United States
• 28: Takeyuki Shimura , Masatoshi Yoshikawa , Shunsuke Uemura, Storage and Retrieval of XML Documents Using Object-Relational Databases, Proceedings of the 10th International Conference on Database and Expert Systems Applications, p.206-217, August 30-September 03, 1999
• 29: Jeff Sidell , Paul M. Aoki , Adam Sah , Carl Staelin , Michael Stonebraker , Andrew Yu, Data Replication in Mariposa, Proceedings of the Twelfth International Conference on Data Engineering, p.485-494, February 26-March 01, 1996
• 30: 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]
• 31: B. Surjanto , N. Ritter , H. Loeser, XML Content Management Based on Object-Relational Database Technology, Proceedings of the First International Conference on Web Information Systems Engineering (WISE'00)-Volume 1, p.70, June 19-20, 2000
• 32: B. W. Wah. File placement on distributed computer systems. IEEE Computer, 17(1), 1984.
• 33: M. Wahl, T. Howes, and S. Kille. Lightweight Directory Access Protocol (v3). Tech report, IETF, RFC 2251, 1997.

INDEX TERMS

Primary Classification:
  H. Information Systems
  H.2 DATABASE MANAGEMENT
      H.2.4 Systems
          Subjects: Query processing

Additional Classification:
  B. Hardware
  B.3 MEMORY STRUCTURES
      B.3.2 Design Styles
          Subjects: Cache memories

  C. Computer Systems Organization
  C.2 COMPUTER-COMMUNICATION NETWORKS
      C.2.5 Local and Wide-Area Networks

  H. Information Systems
  H.2 DATABASE MANAGEMENT
      H.2.4 Systems
          Subjects: Distributed databases

General Terms:
Algorithms, Design, Experimentation, Performance