Minimizing the Make Span of Diagnostic Multi-Query Graphs Using Graph Pruning and Query Merging
Nadra Tabassam, Roman Obermaisser · 2018
Active diagnosis can significantly increase the reliability of a real-time system in case of fault occurrences. Root causes are identified for observed failures and the root causes are associated with suitable recovery actions such as the migration of services to spare resources or application-specific reconfiguration. Real-time databases and diagnostic multi-query graphs (DMG) are a promising technique for root-cause analysis. However, in order to ensure safety the completion of the diagnostic queries must be performed within strict timing bounds dictated by the environment. This paper presents optimization techniques for diagnostic multi-query graphs in order to minimize the make span of a root cause analysis. The optimization is split into two steps. The first step comprises the pruning of the graph nodes without affecting the semantics of diagnostic queries. Each graph node that satisfies a certain set of constraints is deleted and its query is merged with its neighborhood nodes. The constraints for pruning and merging are based on the matching of SQL operations (select or join) and the data tables between the queries. The new graph generated after pruning is a subset of the original graph based on the merged queries from the deleted nodes. The second step is based on the optimization of the diagnostic queries in each node of the DMG, by selecting the best query execution plan. After the DMG is pruned and queries are optimized the new DMG is given as an input to a scheduler to determine the ensuing make span.