That’s a very modern and Western definition of magic. The medieval European concept of magic, for example, held that magic was based on unknown physical laws. If you could suss out the knowledge, you could perform magic. (Chaucer’s The Franklin’s Tale is a nice example of this belief.) The only supernatural object was God. (The medieval Latin supernaturalis, which is first found in Aquinas, is applied to the divine.) Even Satan and demons had to obey the laws of nature that God had set forth.
There is a great process theologian whose name escapes me (edit: Stephen Neill, Bishop of South India, I think) who said that the word “supernatural” should be understood as a kind of “super charged” natural. Natural but charged with the possibility of the transcendent without violating natural law. I cite this thought with appreciation.