ExpresST - Expressive Querying for Semantic Technologies
Final Report Abstract
In ExpresST, we have developed next-generation query languages for OWL knowledge bases. The need for such query languages is apparent from the demands of application scenarios. Accordingly, in ExpresST we were concerned with conjunctive queries (which constitute the formal basis of standard database query languages like SQL) on the one hand, and on the other hand with the development of query languages with expressive capabilities which surpass the classical ones, in particular with regard to the usage of the local closed world assumption and knowledge base introspection. In ExpresST, we first investigated, by means of complexity and decidability analyses, which kinds of query languages are realisable in principle. We found that conjunctive querying is decidable for a large fragment of OWL 1 and OWL 2 but (as supported by later hardness results) it is very unlikely that efficient algorithms can for this task can be found. On the other hand, we were able to show, that for the Horn fragments of OWL 1 and OWL 2, query answering exhibits the same complexity as standard reasoning which makes future efficient implementations more likely. With respect to tractable fragments, we were investigating new approaches to reasoning which are based on the novel paradigm of consequence-driven reasoning. By graph-theoretic analyses we were able to establish more fine-grained metrics for the difficulty of such reasoning problems. We also investigated if uniform interpolation might constitute a beneficial pre-processing step, obtaining a negative answer due to a possible extreme blowup of the resulting knowledge base. In our investigations of the combination of rule-based with description-logic-basd KR formalisms, we focused on a hybrid approach also known as existential rules, which gained a lot of community interest recently. We contributed to comprehensive complexity analyses of known and newly defined fragments of existential rules and designed a generic algorithm that behaves worst-case optimal for many of the considered fragments. In the area of closed-world queries, we focused on epistemic queries, which allow for knowledge base introspection and are not only useful for direct querying but also suitable for defining integrity constraints and checking their violation. Our approach for executing these queries over OWL ontologies works via a reduction to many subsequent standard entailment checks. Thus our implementation, EQuIKa, could be built on top of existing highly optimized reasoning tools. Finally, we investigated query answering in the case where the classical notion of static knowledge bases is replaced by a dynamic one, information being provided to the system as a stream of data. We developed a formal querying framework and query language for this scenario and implemented a Prolog-based prototype, ETALIS, which was thoroughly evaluated and found to be competitive with existing event processing engines. In general, our work was done in a very active and dynamic research field with many internationally renowned groups working in the area of logic-based semantic technologies. In addition the standardization activities under the auspices of the W3C led to the establishment of reference formalisms that constitute foci for subsequent research work. On one hand, this situation required to slightly modify our project goals in order to follow current developments in the scientific community. On the other hand, it allowed us to engage in close and fruitful collaboration with other research teams, leading to a vivid exchange and providing the basis for future cooperation.
Publications
- Nominals, Inverses, Counting, and Conjunctive Queries or: Why Infinity is your Friend! Journal of Artificial Intelligence Research, 39, 429-481, 2010
S. Rudolph, B. Glimm
- EP-SPARQL: A Unified Language for Event Processing and Stream Reasoning. In S. Srinivasan et al. (eds.), Proceedings of the 20th International Conference on World Wide Web (WWW 2011), 635–644. ACM, 2011
D. Anicic, P. Fodor, S. Rudolph, N. Stojanovic
- Extending Decidable Existential Rules by Joining Acyclicity and Guardedness. In T. Walsh (ed.), Proceedings of the 22nd International Joint Conference on Artificial Intelligence (IJCAI 2011), 963–968. IJCAI/AAAI 2011
M. Krötzsch, S. Rudolph
- Query Answering in the Horn Fragments of the Description Logics SHOIQ and SROIQ. In T. Walsh (ed.), Proceedings of the 22nd International Joint Conference on Artificial Intelligence (IJCAI 2011), 1039–1044. IJCAI/AAAI 2011
M. Ortiz, S. Rudolph, M. Šimkus
- Revisiting Semantics for Epistemic Extensions of Description Logics. In W. Burgard, D. Roth (eds.), Proceedings of the 25th AAAI Conference on Artificial Intelligence (AAAI 2011), AAAI Press, 2011
A. Mehdi, S. Rudolph
- A Generic Querying Algorithm for Greedy Sets of Existential Rules. In T. Eiter, S. McIlraith, G. Brewka (eds.), Proceedings of the 13th International Conference on Principles of Knowledge Representation and Reasoning (KR 2012), 96–106, AAAI Press, 2012
M. Thomazo, J.-F. Baget, M.-L. Mugnier, S. Rudolph
- ExpExpExplosion: Uniform Interpolation in General EL Terminologies. In L. De Raedt et al. (eds.), Proceedings of the 20th European Conference on Artificial Intelligence (ECAI 2012), volume 242 of Frontiers in Artificial Intelligence and Applications (FAIA),618–623 IOS Press, 2012 [Shortlisted for best student paper]
N. Nikitina, S. Rudolph
- Type-Elimination-Based Reasoning for the Description Logic SHIQbs Using Decision Diagrams and Disjunctive Datalog. Logical Methods in Computer Science, 8(1:12), 1–38, 2012
S. Rudolph, M. Krötzsch, P. Hitzler
(See online at https://doi.org/10.2168/LMCS-8(1:12)2012) - Complexities of Horn Description Logics. ACM Transactions on Computational Logic, 14(1), 2, 2013
M. Krötzsch, S. Rudolph, P. Hitzler
