Fast Compositional Queries in a Relational Grid Information Service

A Grid Information service (GIS) stores information about the resources of a distributed computing environment and answers questions about it. We have developed RGIS, a GIS system that, unlike previous efforts, is based on the relational data model. RGIS users can write SQL queries that search for complex compositions of resources that meet collective requirements. Executing these queries can be very expensive, however. In response, we have introduced three query techniques, nondeterminism, scoping, and approximation, that allow the user (and RGIS) to trade off between the query’s running time and the number of results. Herein we describe RGIS, our query techniques, and their implementation. Our evaluation shows that a meaningful tradeoff between query time and results returned is achievable, and that the tradeoff can be used to keep query time largely independent of query complexity. RGIS uses our techniques to bound query execution time. This strongly supports our general case for GIS systems based on the relational data model and RDBMSes. Effort sponsored by the National Science Foundation under Grants ANI-0093221, ACI-0112891, ANI-0301108, EIA-0130869, and EIA-0224449. Any opinions, findings and conclusions or recommendations expressed in this material are those of the author and do not necessarily reflect the views of the National Science Foundation (NSF).