2017/10/12 by Jakub Michaliszyn, Michaliszyn, Jakub, Jan Otop +3
Computer Science · #Advanced Database Systems and Queries #Data Management and Algorithms #Databases (cs.DB) #FOS: Computer and information sciences #Graph Theory and Algorithms #H.2.3 #H.2.4
paper · pdf · doi:10.48550/arxiv.1710.04419
openalex publication_date 2017/10/12 · openalex created_date 2025/10/10 · openalex updated_date 2026/07/28
Querying graph databases has recently received much attention. We propose a new approach to this problem, which balances competing goals of expressive power, language clarity and computational complexity. A distinctive feature of our approach is the ability to express properties of minimal (e.g. shortest) and maximal (e.g. most valuable) paths satisfying given criteria. To express complex properties in a modular way, we introduce labelling-generating ontologies. The resulting formalism is computationally attractive -- queries can be answered in non-deterministic logarithmic space in the size of the database.