  In the last decade, substantial progress has been made towards standardizing
the syntax of graph query languages, and towards understanding their semantics
and complexity of evaluation. In this paper, we consider temporal property
graphs (TPGs) and propose temporal regular path queries (TRPQs) that
incorporate time into TPG navigation. Starting with design principles, we
propose a natural syntactic extension of the MATCH clause of popular graph
query languages. We then formally present the semantics of TRPQs, and study the
complexity of their evaluation. We show that TRPQs can be evaluated in
polynomial time if TPGs are time-stamped with time points, and identify
fragments of the TRPQ language that admit efficient evaluation over a more
succinct interval-annotated representation. Finally, we implement a fragment of
the language in a state-of-the-art dataflow framework, and experimentally
demonstrate that TRPQ can be evaluated efficiently.
