A first-order stochastic action language, Datalog Stochastic Action Language (Datalog-SAL), is introduced for describing stochastic dynamic changing worlds. We define syntax and semantics of Datalog-SAL in order to show that a model of Datalog-SAL is given as a set of Hidden Markov Models (HMMs). Probability distributions over actions, state transitions, and initial states could be learned by HMM's parameter learning algorithms such as Baum-Welch algorithm. We investigate the learning complexity of Datalog-SAL with Baum-Welch algorithm. We show two simple examples from a nuclear power station domain and the metabolic pathway reaction domain. Datalog-SAL provides a simple and smooth conversion of Datalog and probability in the action and change framework.