Range queries are a very powerful tool in a wide range of data management systems and are vital to a multitude of applications. The hierarchy of structured overlay systems can be utilized in order to provide efficient techniques for processing them, resulting in the support of applications and techniques based on range queries in large-scale distributed information systems. On the other hand, due to the rapid development of the Web, applications based on the P2P paradigm gain more and more interest, having such systems started to evolve towards adopting standard database functionalities in terms of complex query processing support. This goes far beyond simple key lookups, as provided by standard distributed hashtables (DHTs) systems, which makes estimating the completeness of query answers a crucial challenge. Unfortunately, due to the limited knowledge and the usually best-effort characteristics, deciding about the completeness of query results, e.g., getting an idea when a query is finished or what amount of results is still missing, is very challenging. There is not only an urgent need to provide this information to the user issuing queries, but also for implementing sophisticated and efficient processing techniques based on them. In this chapter, the authors propose a method for solving this task. They discuss the applicability and quality of the estimations, present an implementation and evaluation for the P-Grid system, and show how to adapt the technique to other overlays. The authors also discuss the semantics of completeness for complex queries in P2P database systems and propose methods based on the notion of routing graphs for estimating the number of expected query answers. Finally, they discuss probabilistic guarantees for the estimated values and evaluate the proposed methods through an implemented system.
TopIntroduction
Many new applications on the Web are based on the idea of collecting and combining large public data sets and services. In such public data management applications, the information, its structure and its semantics in many cases are the result of the collaborative effort of the participants. Examples of such applications are social networks, e.g., friend-of-a-friend networks, distributed recommender systems, distributed directory and index services, and sharing of sensor data. These applications typically require the indexing and management of data distributed over a large number of independent data stores, which is a typical scenario targeted by overlay networks.
P2P systems and particularly structured overlays based on distributed hashtables (DHTs) are recognized as a promising infrastructure for large-scale distributed data management. The main reasons are their effectiveness and scalability as well as the predictable behavior. After the first generation supporting only basic key lookups, recent research efforts address also the problem of efficiently querying range predicates (Bharambe, A., Agrawal, M., Seshan, S. (2004); Datta, A., Hauswirth, M., Schmidt, R., John, R., Aberer, K. (2005)). Typically, these approaches exploit the structure of the overlay (e.g., a tree structure) by implementing some kind of multicast protocol. In this context, a main challenge is to estimate the progress of query processing, i.e., to answer the question which fraction of the total query result is already received. The difficulties are due to the purely decentralized nature of the structured overlay, the lack of global knowledge (no peer knows how many peers are responsible for the queried key range), the dynamics of the network (peers may leave the network during processing a query), as well as the often used best-effort strategy for query routing and answering. Indeed,P2P data management is inherently open world: While processing a query, peers can fail, leave or join the network, or simply send no or a delayed answer (Gribble, S.D., Halevy, A.Y., Ives, Z.G., Rodrig, M., Suciu, D. (2001)). Though this can be mitigated by replication and delay-tolerant query techniques, there is no guarantee that all answers which potentially exist can be returned. On the other hand, DHTs, the most efficient family of overlay networks, so far have only been applicable to a certain degree in these scenarios, as support for managing and querying structured data in DHTs still is limited.
Estimating the completeness of a query result is not only a helpful information for the user issuing the query, but it is also needed for processing complex queries. For instance, query operators like aggregation or ranking-based queries (e.g., skyline queries (Börzsönyi, S., Kossmann, D., Stocker, K. (2001); Karnstedt, M.,Müller, J., Sattler, K. (2007))) require to know when all input data is arrived in order to calculate the aggregate value or to sort the input. Thus, we argue that estimating the completeness of query answers is a key aspect of reliable query processing in P2P databases.
In this chapter, we propose a solution to problems above. The general idea underlying our vision is that an approximated, but prompt estimation is often satisfying for the user. The objective of our work is to estimate the completeness of range queries as a fundamental operator for more complex query operators and to give guarantees on the quality of this estimation. The idea is to map the completeness on data level to a completeness on peer level, thus, estimating a number of replies expected for each query. This, of course, is still very challenging in the investigated systems. We achieve this by estimating the number of query answers without explicitly analyzing the actual content of each answer. Note that we are not trying to guarantee completeness, neither we want to improve the functionality of the underlying DHT. Instead we only get what is available at query time (“in situ querying'') but are able to assess the completeness of this result. Furthermore, we aim at an incremental and online refinement of the estimation.