Optimization techniques and software architectures for improving scalability of description logic reasoners

用于提高描述逻辑推理器可扩展性的优化技术和软件架构

• 批准号: RGPIN-2019-05526
• 负责人: Haarslev, Volker
• 金额: $ 2.48万
• 依托单位: Concordia University
• 依托单位国家: 加拿大
• 项目类别: Discovery Grants Program - Individual
• 财政年份: 2022
• 资助国家: 加拿大
• 起止时间: 2022-01-01 至 2023-12-31
• 项目状态: 已结题
• 来源: https://www.nserc-crsng.gc.ca/ase-oro/Details-Detailles_eng.asp?id=750109
• 关键词: Optimization; techniques; software; architectures; improving

The proposed research program is mainly concerned with the design and empirical evaluation of optimization techniques and software architectures for description logic (DL) reasoners. Over the last 15 years DL reasoning has gained attention from the semantic web community because the Web Ontology Language (OWL) is based on DL. OWL is a syntactic variant of a very expressive DL. Roughly speaking DL knowledge is described using concepts, roles, and individuals that can be combined with various constructors. Concepts describe sets of individuals with common properties and roles specify binary relationships between individuals. From a DL point of view an OWL knowledge base (or ontology) can be divided into terminological and assertional knowledge. The terminological knowledge (Tbox) consists of a finite set of concept and role axioms and assertional knowledge (Abox) of a finite set of assertions about individuals. The concept satisfiability problem for OWL is known to be N2ExpTime-complete. A multitude of optimization techniques are required to speed up inference services for concepts (e.g., satisfiability, subsumption), Tboxes (e.g., axiom transformation, classification), individuals (e.g., instance checking), and Aboxes (e.g., consistency, realization, conjunctive query answering). The first objective is to improve reasoning scalability by adapting parallelization or distribution techniques. These techniques are well suited in cases where reasoning remains expensive. The proposed architectures employ (i) thread-level parallelism for DL reasoning algorithms that can be executed in parallel but usually share common data structures or (ii) distributed approaches applying a divide-and-conquer scheme where reasoning tasks can be partitioned into independent subproblems. Over the last four years we developed a very promising approach for parallelizing OWL ontology classification with a scalability that is linear to the number of available processing units. It is planned to further extend this approach and develop other approaches based on distributed processing. The second objective is to develop novel calculi and optimization techniques for DL language elements such as number restrictions, nominals, and inverse roles. These three elements can impose implicit cardinality constraints on sets of individuals and in this context most known DL reasoning algorithms do not scale. Over the past decade my research group has coined the algebraic DL reasoning approach, which combines traditional reasoning algorithms that are tableau or consequence-based with integer linear programming. Such algebraic reasoning approaches have shown to be superior because implicit cardinality constraints on sets can be encodes as integer linear inequalities and solved efficiently. The scalability of algebraic reasoning has been improved by integrating column generation and branch-and-price techniques. The goal is to extend these techniques further and improve their scalability.

所提出的研究计划主要涉及描述逻辑(DL)推理器的优化技术和软件体系结构的设计和实证评估。在过去的15年里，由于Web Ontology Language(OWL)是基于DL的，因此DL推理得到了语义网社区的关注。OWL是一种表达能力很强的DL的句法变体。粗略地说，DL知识是使用概念、角色和个人来描述的，这些概念、角色和个人可以与各种构造器相结合。概念描述具有共同属性的个体集合，角色指定个体之间的二元关系。从描述语言的角度来看，OWL知识库(或本体)可以分为术语知识和断言知识。术语知识(Tbox)由概念和角色公理的有限集合以及关于个体的有限断言集合的断言知识(Abox)组成。OWL的概念可满足性问题是已知的N2ExpTime-Complete。需要多种优化技术来加速针对概念(例如，可满足性、包含)、T盒(例如，公理转换、分类)、个体(例如，实例检查)和Abox(例如，一致性、实现、合取查询应答)的推理服务。第一个目标是通过采用并行化或分布式技术来提高推理的可扩展性。这些技术非常适合推理仍然昂贵的情况。该体系结构采用(I)可并行执行但通常共享公共数据结构的DL推理算法的线程级并行，或(Ii)采用分而治之的分布式方法，其中推理任务可被划分为独立子问题。在过去的四年里，我们开发了一种非常有希望的方法来并行OWL本体分类，其可扩展性与可用处理单元的数量呈线性关系。计划进一步扩展这一方法，并开发其他基于分布式处理的方法。第二个目标是开发新的演算和优化技术，用于数字限制、名词性和反转角色等数字减词语言元素。这三个元素可以对个体集合施加隐式基数约束，在这种情况下，大多数已知的DL推理算法不能扩展。在过去的十年里，我的研究小组创造了代数DL推理方法，它将传统的基于表或结果的推理算法与整数线性规划相结合。这种代数推理方法被证明是优越的，因为集合上的隐基数约束可以被编码为整数线性不等式并有效地求解。通过将列生成和分支与价格技术相结合，提高了代数推理的可扩展性。目标是进一步扩展这些技术并提高其可伸缩性。