Service dependency is determined for services in a service oriented architecture (SOA) environment. The steps in determining service dependency include: recording a first triple describing a first service call where the first service calls the second service, and determining the first service is dependent upon the second service based, at least in part, upon the first triple. The recording action is performed dynamically, the recording occurring when the first service call is made. Other related steps include recording the first triple to a timestamp indicating when the first service call is made.