We propose a new approach to querying graph databases. Our approach 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.
翻译:我们提出了一种新的查询图表数据库的方法。我们的方法平衡了表达力、语言清晰度和计算复杂性等相互竞争的目标。我们的方法的一个显著特点是能够表达满足特定标准的最小(例如最短)和最大(例如最有价值的)路径的特性。为了以模块方式表达复杂特性,我们引入了产生标签的理论。由此产生的形式主义在计算上具有吸引力 -- -- 在数据库的大小中,查询可以在非确定性的对数空间中解答。