In order to effectively and efficiently disclose the ever-growing amount of widely distributed RDF data to demanding users in real-time environments, RDF query engines need to optimize the join order of partial query results. For this, a two-phase optimization (2PO) algorithm and a genetic algorithm (GA) have already been proposed. We propose an alternative approach - an ant colony system (ACS). On a large RDF data source, our approach significantly outperforms both 2PO and the GA in terms of execution time and solution quality for RDF chain queries consisting of up to about ten joins. For larger queries, our novel ACS delivers solutions of better quality than 2PO does, while realizing a solution quality that is comparable to the solution quality of the GA method. However, the GA approach offers the best trade-off between execution time and solution quality for such larger queries.

Additional Metadata
Keywords Alternative approach, Ant colony systems, Execution time, Query optimization, Query results, RDF chain query optimization, Real-time environment, Solution quality, Two-phase optimizations, ant colony system
Persistent URL dx.doi.org/10.1109/WI-IAT.2012.63, hdl.handle.net/1765/40598
Conference 2012 IEEE/WIC/ACM International Conference on Web Intelligence, WI 2012
Citation
Hogenboom, A.C, Niewenhuijse, E, & Frasincar, F. (2012). RCQ-ACS: RDF chain query optimization using an ant colony system. Presented at the 2012 IEEE/WIC/ACM International Conference on Web Intelligence, WI 2012. doi:10.1109/WI-IAT.2012.63