A possible solution of the problem of time in quantum gravitational systems is presented based on a relational description between the parameterized Dirac observables of the system under consideration and the clocks. The use of physical clocks required by a quantum gravitational description of time is shown to induce a loss of unitarity. The evolution is described by a Lindblad-type master equation unless it is possible to construct a perfect clock. I show that fundamental uncertainties in time measurements could arise due to quantum and gravitational effects, leading to the conclusion that there is always a loss of unitarity induced by the use of physical clocks. The extension of the analysis to physical reference frames in totally constrained systems is sketched.