On the Expressive Power of Ontology-Mediated Queries: Capturing coNP.
Sanja LukumbuzyaMagdalena OrtizMantas SimkusPublished in: Description Logics (2023)
Keyphrases
- expressive power
- query language
- data complexity
- relational calculus
- pattern queries
- conjunctive queries
- query evaluation
- recursive queries
- aggregate functions
- database query languages
- transitive closure
- data model
- relational algebra
- first order logic
- database
- relational query languages
- conceptual model
- monadic second order logic
- constraint databases
- computational properties
- semantic web
- knowledge base
- knowledge representation
- efficient processing
- query processing
- datalog queries
- domain ontology
- range queries
- exptime complete
- regular expressions
- user defined aggregates
- complex objects
- query containment
- relational database systems
- np hard
- database systems
- relation algebra