The discovery of substrate materials has been dominated by trial and error, opening the opportunity for a systematic search. We generate bonding networks for materials from the Materials Project and systematically break up to three bonds in the networks for three-dimensional crystals. Successful cleavage reduces the bonding network to two periodic dimensions. We identify 4693 symmetrically unique cleavage surfaces across 2133 bulk crystals, 4626 of which have a maximum Miller index of one. We characterize the likelihood of cleavage by creating monolayers of these surfaces and calculating their thermodynamic stability using density functional theory to discover 3991 potential substrates. Following, we identify distinct trends in the work of cleavage and relate them to bonding in the three-dimensional precursor. We illustrate the potential impact of the substrate database by identifying several improved epitaxial substrates for the transparent conductor BaSnO3. The open-source databases of predicted and commercial substrates are available at MaterialsWeb.org. © 2021, The Author(s).