Reducing the carbon footprint in cement production is a pressing challenge faced by the construction industry. In the past few years, the world annual cement consumption is approximately at 4 billion tons, where each ton leads to 1-ton CO2 emissions. To curb the massive environmental impact, it is pertinent to improve material performance and reduce carbon embodiment of cement. This requires an in-depth understanding of how cement strength is controlled by its chemical composition. Although this problem has been investigated for more than one hundred years, our current knowledge is still deficient for a clear decomposition of this complex composition-strength relationship. Here, we take advantage of Gaussian process regression (GPR) to decipher the fundamental compositional attributes (the cement "genome") to cement strength performance. Among all machine learning methods applied to the same dataset, our GPR model achieves the highest accuracy of predicting cement strength based on the chemical compounds. Based on the optimized GPR model, we are able to decompose the influence of each oxide on cement strength to an unprecedented level.