Accelerating Recursive Queries in Federated Database Systems: Small-World Networks Based Approach

Federated Database System (FDBS) is a general name for storage systems consisting of distributed data sources. The data sources can be databases or any software system with query interface. Recursive Queries are queries on which the result relation is defined in terms of itself, and involves an infinite, recursively defined sequence of similar expressions. This work addresses the issue by providing a heuristic which tries to improve the execution of the recursive queries on FDBS based on the database structure. In the development process we have used the knowledge aquired in the area of real world networks since most databases on which a recursive query can be executed represent a type of real world network. We used the fact that on some networks there are nodes with a large degree (sometimes called Hubs) in order to reduce the sizes of sub queries. This size reduction is achieved by limiting the search of the reachability set of a node in the graph to the edges coming out of hubs connected to that node, and the hubs they are connected to and so forth.