Sovereign debt ratings provided by rating agencies measure the solvency of a country, as gauged by a lender or an investor. It is an indication of the risk involved in investment, and should be determined correctly and in a well timed manner. The present study reconstructs sovereign debt ratings through logical analysis of data, which is based on the theory of Boolean functions. It organizes groups of countries according to twenty World Bank defined variables for the period 2012 till 2015. The Fitch Rating Agency, one of the three big global rating agencies, is used as a case study. An approximate algorithm was crucial in exploring the rating method, in correcting the agencys errors, and in determining the estimated rating of otherwise non rated countries. The outcome was a decision tree for each year. Each country was assigned a rating. On average, the algorithm reached almost ninety eight percentage matched ratings in the training set, and was verified by eighty four percentage in the test set. This was a considerable achievement.