  Validation of compliance rules against process data is a fundamental
functionality for business process management. Over the years, the problem has
been addressed for different types of process data, i.e., process models,
process event data at runtime, and event logs representing historical
execution. Several approaches have been proposed to tackle compliance checking
over process logs. These approaches have been based on different data models
and storage technologies including relational databases, graph databases, and
proprietary formats. Graph-based encoding of event logs is a promising
direction that turns several process analytics tasks into queries on the
underlying graph. Compliance checking is one class of such analysis tasks. In
this paper, we argue that encoding log data as graphs alone is not enough to
guarantee efficient processing of queries on this data. Efficiency is important
due to the interactive nature of compliance checking. Thus, compliance checking
would benefit from sub-linear scanning of the data. Moreover, as more data are
added, e.g., new batches of logs arrive, the data size should grow sub-linearly
to optimize both the space of storage and time for querying. We propose two
encoding methods using graph representation, realized in Neo4J, and show the
benefits of these encoding on a special class of queries, namely timed order
compliance rules. Compared to a baseline encoding, our experiments show up to
5x speed up in the querying time as well as a 3x reduction in the graph size.
