2021/12/15 by Heng Zhang, Zhang, Heng
Computer Science · #Advanced Database Systems and Queries #Artificial Intelligence (cs.AI) #Databases (cs.DB) #FOS: Computer and information sciences #Logic in Computer Science (cs.LO) #Logic, Reasoning, and Knowledge #Semantic Web and Ontologies
paper · pdf · doi:10.48550/arxiv.2112.08136
openalex publication_date 2021/12/15 · openalex created_date 2022/10/07 · openalex updated_date 2026/07/28
Existential rule languages are a family of ontology languages that have been widely used in ontology-mediated query answering (OMQA). However, for most of them, the expressive power of representing domain knowledge for OMQA, known as the program expressive power, is not well-understood yet. In this paper, we establish a number of novel characterizations for the program expressive power of several important existential rule languages, including tuple-generating dependencies (TGDs), linear TGDs, as well as disjunctive TGDs. The characterizations employ natural model-theoretic properties, and automata-theoretic properties sometimes, which thus provide powerful tools for identifying the definability of domain knowledge for OMQA in these languages.