QUERY EVALUATION ON DISTRIBUTED SEMI-STRUCTURED DATA

The invention provides a system and method for evaluating a query on a distributed database across multiple sites. Database portion contained within each site is processed by a respective terminal. A client terminal is a terminal that distributes and collects information for evaluating the query. Each of the terminals receives the query and performs evaluation of the query on the respective distributed portion of the database. The terminals generate an accessibility graph based on the query evaluation of the respective distributive portion of the database and transmit the accessibility graphs to the client terminal. The client terminal receives all the accessibility graphs from each of the terminals and constructs an accessibility graph for the complete distributed database. The client terminal then traces through the accessibility graph for the distributed database and determines which parts of each of the distributed portions contribute to the query result. The client terminal transmits to each of the terminals information identifying the respective parts that contribute to the query result. The terminals returns the parts of the respective portions of the distributed database to the client terminal for construction of the query result.