Tractable Compliance Checking with Negation

PL is a low-complexity fragment of OWL2, expressly designed to automatically check the compliance of privacy policies with respect to the consent of data subjects and the regulations on personal data processing, such as the GDPR. Privacy policies, consent and regulations can all be expressed uniformly with PL classes, and compliance checking is reduced to subsumption checking. The latter is tractable and highly scalable to meet the performance requirements of some applications. Several use cases need negation in the queries; however, subsumption checking becomes coNP-hard, even if negation is restricted to atomic concepts. In this paper we show that an alternative encoding based on histories of positive and negative policies (where negation is applied to compound concepts) can be processed in polynomial time by a correct and complete algorithm.