Graph Queries and Description Logics
Filip Murlak University of Warsaw
Course Summary |
About the lecturer |
Location and schedule |
Some of the fundamental problems in databases and knowledge representation can be seen as instances of the query entailment problem. While query evaluation asks whether a given query holds in a given structure, in the task of query entailment one needs to determine if the query holds in every model of a given theory that extends the given structure. The input structure represents the raw data, as stored in a database; the theory captures the context of the problem, such as a set of integrity constraints or an ontology; and the query extracts specific information.
The recent proliferation of graph databases has brought the database community and the knowledge representation community closer together, as some of the key problems studied in these communities involve the same structures—labelled graphs—and the same or very similar combinations of formalisms for theories and queries. One such combination is description logics and conjunctive regular path queries. Description logics are a family of formalisms based on fragments of first order logic, akin to modal logics; they are among the most prominent ontology languages and they are capable of expressing most constraints relevant in graph databases. Conjunctive regular path queries are an extension of conjunctive queries (primitive positive first-order formulas) in which regular expressions over binary predicates can be used as atoms; they are the core of practical query languages used in the Semantic Web and in modern graph databases.
What distinguishes the two communities is the approach to infinity: knowledge representation embraces infinite models, whereas database theory focuses on finite models. While many problems have been solved over unrestricted models long ago, their finite-model counterparts have seen progress only recently and many questions remain open. This course presents key techniques behind this progress and discusses current challenges.
About the lecturer:Filip Murlak obtained his PhD at the University of Warsaw in 2008, specializing in automata theory. During a postdoctoral internship at the University of Edinburgh he got interested in database theory, and later also in knowledge representation. Currently, he holds a position at the University of Warsaw and works mainly on graph data management, schema and query languages, ontology-based data access, and streaming semi-structured data. Beyond academia, he has participated in collaborative projects with industry and standards committees. He received the Witold Lipski Prize for Young Researchers in Computer Science (2009), the Best Paper Award at ICALP 2006 and SIGMOD 2023 (Industry Track), as well as the SIGMOD Research Highlight Award (2023). He has co-authored two books on data exchange and an automata theory problem book.
Location and schedule:
|
|
|
||||||||||||||||