Pablo Barcelo (Universidad de Chile)
Title: A Theoretical View on Reverse Engineering Problems for Database Query Languages
Abstract: A typical reverse engineering problem for a query language L is as follows: Given a database D and two sets P and N of tuples over D labeled as “positive” and “negative” examples, respectively, is there a query q in L that “explains” P and N, i.e., the evaluation of q on D contains all positive examples in P and none of the negative examples in N? Applications of reverse engineering problems include database explanations, data exploration, data security, relational classifier engineering, and the study of the expressiveness of query languages. In this talk I will present a family of tests that solve the reverse engineering problem described above for several query languages of interest, e.g., FO, CQ, UCQs, RPQs, CRPQs, etc. We will see that in many cases such tests directly provide optimal bounds for the problem, as well as for the size of the smallest query that explains the given labeled examples. I will also present restrictions that alleviate the complexity of the problem when it is too high. Finally, I will develop the relationship between reverse engineering and a separability problem recently introduced in the database theory literature to assist the task of relational classifier engineering with data management tools.
Bio: Pablo Barceló is Full Professor in the Department of Computer Science at the University of Chile and Deputy Director of the Millennium Institute for Foundational Research on Data. He received his PhD from the University of Toronto in 2006. His main research interest are in the areas of databases and logic in computer science, where he has contributed with over 50 technical papers in major conferences and journals. He has also been an invited tutorial speaker at ACM PODS 2013. He is a member of the editorial board of Logical Methods in Computer Science and a former editor of the Database Principles Column of the SIGMOD Record. During 2019 he is chairing the International Conference on Database Theory (ICDT).
Meghyn Bienvenu (University of Bordeaux)
Title: Inconsistency Handling in Ontology-Mediated Query Answering: A Progress Report
Abstract: It is widely acknowledged that real-world data is plagued with numerous data quality issues, among them the presence of erroneous facts. While already a serious issue for “plain” databases, the problem of handling imperfect data is even more critical in the setting of ontology-mediated query answering (OMQA), where even a single erroneous fact can provoke an inconsistency, thereby rendering classical OMQA semantics useless. This has motivated DL and KR researchers to study a variety of approaches for handling inconsistent data in OMQA, both building upon and extending techniques initially proposed for databases. Now that there has been about a decade of research on inconsistency handling in OMQA, the time is ripe to take a step back and evaluate the progress that has been made and what remains to be done. The first half of the talk will provide a brief overview of the state-of-the-art, presenting the main results and lessons learnt, with the remainder of the talk being devoted to discussing the limitations of current approaches and some ideas for moving forward.
Bio: Meghyn Bienvenu is a tenured researcher at the CNRS (French National Center for Scientific Research), currently based at the LaBRI laboratory in Bordeaux, following earlier postings in Montpellier and Paris. Prior to joining the CNRS, she was a postdoctoral researcher at the University of Bremen (Germany). She obtained her undergraduate degree from the University of Toronto (Canada) and her Master’s and PhD degrees (the latter in 2009) from the University of Toulouse (France). Her research interests span a range of topics in knowledge representation and reasoning and database theory, with a focus on description logic ontologies and their use in querying data.
Gerhard Lakemeyer (RWTH Aachen)
Title: Decidable Verification of Golog Programs: Situation Calculus Meets Description Logic
Abstract: In the area of reasoning about action and change, one of the best understood formalisms is the situation calculus, which was originally proposed by John McCarthy in the late fifties. In its modern form, due to Ray Reiter, the situation calculus provides a solution to the frame problem and is also the basis for the action programming language Golog, which is used, among other things, to control the high-level behavior of robots. When considering the verification of temporal properties of Golog programs, one quickly runs into undecidability because of the expressiveness of the situation calculus. To tackle this problem we have teamed up with Franz Baader and his group, and we have been able to show that decidable verification can be obtained when the base logic is restricted to a Description Logic (DL). In this talk, I will begin by introducing a modal variant of the situation calculus and Golog. I will then define the verification problem and show how decidability can be achieved with the help of DL.
Bio: Gerhard Lakemeyer received his Ph.D. from the University of Toronto in 1990. After six years at the University of Bonn he joined the faculty of the Department of Computer Science at RWTH Aachen University, where he is Full Professor and heads the Knowledge-Based Systems Group. He is also a Full Professor (status-only) at the University of Toronto, Canada, and a Professorial Fellow at the University of New South Wales, Australia. His research interests include knowledge representation and cognitive robotics. He has published more than 150 scientific papers and has served on numerous program committees, including IJCAI, AAAI, ECAI, and KR. He is a Fellow of the European Association for Artificial Intelligence (EurAI), past President of EurAI, Associate Editor of Artificial Intelligence, and Area Editor of Computational Intelligence. He is also a member of the Editorial Board of the Journal of Applied Logic, and was a member of the Editorial and Advisory Board of the Journal of Artificial Intelligence Research.