2 Search Results for "Console, Marco"

Document
Invited Talk
DOI: 10.4230/LIPIcs.MFCS.2025.4
On Graph Queries and Modal Constraints (Invited Talk)

Authors: Filip Murlak

Published in: LIPIcs, Volume 345, 50th International Symposium on Mathematical Foundations of Computer Science (MFCS 2025)

Abstract
Some fundamental problems in database theory and knowledge representation can be viewed as instances of the query entailment problem. While query evaluation asks whether a given query holds in a specific structure, query entailment consists in determining whether the query holds in every model of a given theory that extends that structure. The input structure represents the raw data stored in a database; the theory captures contextual information such as a set of database constraints or an ontology; and the query is used to extract specific information of interest. The recent proliferation of graph databases has brought the database and knowledge representation communities closer together, as many key problems in both fields involve the same structures - labelled graphs - and similar combinations of formalisms for theories and queries. A notable example is the combination of 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 kinds of constraints relevant in graph databases. Conjunctive regular path queries extend conjunctive queries (primitive positive first-order formulas) by allowing regular expressions over binary predicates to be used as atoms. They form the core of practical query languages employed in graph database systems and the Semantic Web. What distinguishes the two fields is the approach to infinity: knowledge representation embraces infinite models, whereas database theory focuses on finite models. Although many cases of the entailment problem have long been solved over unrestricted (finite or infinite) models, their finite-model counterparts have only recently seen progress, and many questions remain open.
Cite as

Filip Murlak. On Graph Queries and Modal Constraints (Invited Talk). In 50th International Symposium on Mathematical Foundations of Computer Science (MFCS 2025). Leibniz International Proceedings in Informatics (LIPIcs), Volume 345, p. 4:1, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2025)

Copy BibTex To Clipboard

@InProceedings{murlak:LIPIcs.MFCS.2025.4,
  author =	{Murlak, Filip},
  title =	{{On Graph Queries and Modal Constraints}},
  booktitle =	{50th International Symposium on Mathematical Foundations of Computer Science (MFCS 2025)},
  pages =	{4:1--4:1},
  series =	{Leibniz International Proceedings in Informatics (LIPIcs)},
  ISBN =	{978-3-95977-388-1},
  ISSN =	{1868-8969},
  year =	{2025},
  volume =	{345},
  editor =	{Gawrychowski, Pawe{\l} and Mazowiecki, Filip and Skrzypczak, Micha{\l}},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.MFCS.2025.4},
  URN =		{urn:nbn:de:0030-drops-241117},
  doi =		{10.4230/LIPIcs.MFCS.2025.4},
  annote =	{Keywords: conjunctive regular path queries, query entailment, query containment, graph databases, database schemas, integrity constraints, description logics, finite-model reasoning, ontology-mediated query answering, static analysis}
}
Document
DOI: 10.4230/LIPIcs.ICDT.2019.8
Fragments of Bag Relational Algebra: Expressiveness and Certain Answers

Authors: Marco Console, Paolo Guagliardo, and Leonid Libkin

Published in: LIPIcs, Volume 127, 22nd International Conference on Database Theory (ICDT 2019)

Abstract
While all relational database systems are based on the bag data model, much of theoretical research still views relations as sets. Recent attempts to provide theoretical foundations for modern data management problems under the bag semantics concentrated on applications that need to deal with incomplete relations, i.e., relations populated by constants and nulls. Our goal is to provide a complete characterization of the complexity of query answering over such relations in fragments of bag relational algebra. The main challenges that we face are twofold. First, bag relational algebra has more operations than its set analog (e.g., additive union, max-union, min-intersection, duplicate elimination) and the relationship between various fragments is not fully known. Thus we first fill this gap. Second, we look at query answering over incomplete data, which again is more complex than in the set case: rather than certainty and possibility of answers, we now have numerical information about occurrences of tuples. We then fully classify the complexity of finding this information in all the fragments of bag relational algebra.
Cite as

Marco Console, Paolo Guagliardo, and Leonid Libkin. Fragments of Bag Relational Algebra: Expressiveness and Certain Answers. In 22nd International Conference on Database Theory (ICDT 2019). Leibniz International Proceedings in Informatics (LIPIcs), Volume 127, pp. 8:1-8:16, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2019)

Copy BibTex To Clipboard

@InProceedings{console_et_al:LIPIcs.ICDT.2019.8,
  author =	{Console, Marco and Guagliardo, Paolo and Libkin, Leonid},
  title =	{{Fragments of Bag Relational Algebra: Expressiveness and Certain Answers}},
  booktitle =	{22nd International Conference on Database Theory (ICDT 2019)},
  pages =	{8:1--8:16},
  series =	{Leibniz International Proceedings in Informatics (LIPIcs)},
  ISBN =	{978-3-95977-101-6},
  ISSN =	{1868-8969},
  year =	{2019},
  volume =	{127},
  editor =	{Barcelo, Pablo and Calautti, Marco},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.ICDT.2019.8},
  URN =		{urn:nbn:de:0030-drops-103106},
  doi =		{10.4230/LIPIcs.ICDT.2019.8},
  annote =	{Keywords: bag semantics, relational algebra, expressivity, certain answers, complexity}
}
  • Refine by Type
  • 2 Document/PDF
  • 1 Document/HTML

  • Refine by Publication Year
  • 1 2025
  • 1 2019

  • Refine by Author
  • 1 Console, Marco
  • 1 Guagliardo, Paolo
  • 1 Libkin, Leonid
  • 1 Murlak, Filip

  • Refine by Series/Journal
  • 2 LIPIcs

  • Refine by Classification
  • 1 Information systems → Relational database query languages
  • 1 Information systems → Structured Query Language
  • 1 Theory of computation → Database query languages (principles)
  • 1 Theory of computation → Database theory
  • 1 Theory of computation → Description logics
  • Show More...

  • Refine by Keyword
  • 1 bag semantics
  • 1 certain answers
  • 1 complexity
  • 1 conjunctive regular path queries
  • 1 database schemas
  • Show More...

Any Issues?
X

Feedback on the Current Page

CAPTCHA

Thanks for your feedback!

Feedback submitted to Dagstuhl Publishing

Could not send message

Please try again later or send an E-mail
© 2023-2025 Schloss Dagstuhl – LZI GmbH About DROPS Imprint Privacy Contact