We propose an effective method to compute the sky pattern cubes thanks to a relaxation strategy in the pattern mining process. Our approach is based on the fact that each node of the cube can be approximated by the set of edge-sky patterns (a relaxed form of sky patterns) w.r.t. The whole set of measures M. Then we transform the problem into a skyline cube mining in M dimensions. The set of edge-sky patterns can be efficiently mined by using either a dynamic CSP method or an extended version of a static method based on the theoretical relationships between patterns and condensed representations of sky patterns. Experiments conducted on UCI datasets and on a real-life dataset (Mutagen city) show the relevance and performance of our approach.