A machine learning service implements programmatic interfaces for a variety of operations on several entity types, such as data sources, statistics, feature processing recipes, models, and aliases. A first request to perform an operation on an instance of a particular entity type is received, and a first job corresponding to the requested operation is inserted in a job queue. Prior to the completion of the first job, a second request to perform another operation is received, where the second operation depends on a result of the operation represented by the first job. A second job, indicating a dependency on the first job, is stored in the job queue. The second job is initiated when the first job completes.