Model-theoretic Characterizations of Rule-based Ontologies

Marco Console, Phokion G. Kolaitis, Andreas Pieris

Research output: Chapter in Book/Report/Conference proceedingConference contribution

Abstract / Description of output

An ontology specifies an abstract model of a domain of interest via a formal language that is typically based on logic. Although description logics are popular formalisms for modeling ontologies, it is generally agreed that tuple-generating dependencies (tgds), originally introduced as a unifying framework for database integrity constraints, and later on used in data exchange and integration, are well suited for modeling ontologies that are intended for data-intensive tasks. The reason is that, unlike description logics, tgds can easily handle higher-arity relations that naturally occur in relational databases. In recent years, there has been an extensive study of tgd-ontologies and of their applications to several different data-intensive tasks. However, the fundamental question of whether the expressive power of tgd-ontologies can be characterized in terms of model-theoretic properties remains largely unexplored. We establish several characterizations of tgd-ontologies, including characterizations of ontologies specified by such central classes of tgds as full, linear, guarded, and frontier-guarded tgds. Our characterizations use the well-known notions of critical instance and direct product, as well as a novel locality property for tgd-ontologies. We further use this locality property to decide whether an ontology expressed by frontier-guarded (respectively, guarded) tgds can be expressed by tgds in the weaker class of guarded (respectively, linear) tgds, and effectively construct such an equivalent ontology if one exists.
Original languageEnglish
Title of host publicationProceedings of the 40th ACM SIGMOD-SIGACT-SIGAI Symposium on Principles of Database Systems
PublisherACM Association for Computing Machinery
Number of pages13
ISBN (Electronic)9781450383813
Publication statusPublished - 20 Jun 2021
EventACM SIGMOD/PODS International Conference on Management Data - Virtual, Xi'an, China
Duration: 20 Jun 202125 Jun 2021


ConferenceACM SIGMOD/PODS International Conference on Management Data
Abbreviated titleSIGMOD/PODS 2021
Internet address


Dive into the research topics of 'Model-theoretic Characterizations of Rule-based Ontologies'. Together they form a unique fingerprint.

Cite this