Variable environmental conditions and runtime phenomena require developers of complex business information systems to expose configuration parameters to system administrators. This allows system administrators to intervene by tuning the bottleneck configuration parameters in response to current changes or in anticipation of future changes in order to maintain the system’s performance at an optimum level. However, these manual performance tuning interventions are prone to error and lack of standards due to fatigue, varying levels of expertise and over-reliance on inaccurate predictions of future states of a business information system. As a result, the purpose of this research is to investigate on how the capacity of probabilistic reasoning to handle uncertainty can be combined with the capacity of Markov chains to map stochastic environmental phenomena to ideal self-optimization actions. This was done using a comparative experimental research design that involved quantitative data collection through simulations of different algorithm variants. This provided compelling results that indicate that applying the algorithm in a distributed database system improves performance of tuning decisions under uncertainty. The improvement was quantitatively measured by a response-time latency that was 27% lower than average and a transaction throughput that was 17% higher than average.