3 Search Results for "Console, Marco"

Document
Invited Paper
DOI: 10.4230/OASIcs.RW.2024/2025.5
Inconsistency-Tolerant Semantics Based on (Preferred) Repairs (Invited Paper)

Authors: Camille Bourgaux

Published in: OASIcs, Volume 138, Joint Proceedings of the 20th and 21st Reasoning Web Summer Schools (RW 2024 & RW 2025)

Abstract
Real-world datasets are plagued by data quality issues which may render the data inconsistent w.r.t. a set of constraints, be they given by database integrity constraints or ontologies. A prominent way to handle such inconsistent data is to use inconsistency-tolerant semantics to obtain meaningful answers to queries. Most of these semantics are based on some notion of repairs, which represent ways of restoring the data consistency. The most basic kind of repairs is that of subset repairs, which are maximal consistent subsets of the dataset. However, in many scenarios, one can define preferred repairs based on some preference information. These lecture notes present inconsistency-tolerant semantics, focusing on the repair-based ones, then review different kinds of preferred repairs that have been considered in the literature. We present in particular the relationships between different kinds of preferred repairs and other notions related to inconsistency handling, the computational complexity of reasoning with (preferred) repairs, and some implementations.
Cite as

Camille Bourgaux. Inconsistency-Tolerant Semantics Based on (Preferred) Repairs (Invited Paper). In Joint Proceedings of the 20th and 21st Reasoning Web Summer Schools (RW 2024 & RW 2025). Open Access Series in Informatics (OASIcs), Volume 138, pp. 5:1-5:67, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2025)

Copy BibTex To Clipboard

@InProceedings{bourgaux:OASIcs.RW.2024/2025.5,
  author =	{Bourgaux, Camille},
  title =	{{Inconsistency-Tolerant Semantics Based on (Preferred) Repairs}},
  booktitle =	{Joint Proceedings of the 20th and 21st Reasoning Web Summer Schools (RW 2024 \& RW 2025)},
  pages =	{5:1--5:67},
  series =	{Open Access Series in Informatics (OASIcs)},
  ISBN =	{978-3-95977-405-5},
  ISSN =	{2190-6807},
  year =	{2025},
  volume =	{138},
  editor =	{Artale, Alessandro and Bienvenu, Meghyn and Garc{\'\i}a, Yazm{\'\i}n Ib\'{a}\~{n}ez and Murlak, Filip},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops.dagstuhl.de/entities/document/10.4230/OASIcs.RW.2024/2025.5},
  URN =		{urn:nbn:de:0030-drops-250504},
  doi =		{10.4230/OASIcs.RW.2024/2025.5},
  annote =	{Keywords: Knowledge bases, databases, inconsistency handling, repairs, preferences}
}
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
  • 3 Document/PDF
  • 2 Document/HTML

  • Refine by Publication Year
  • 2 2025
  • 1 2019

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

  • Refine by Series/Journal
  • 2 LIPIcs
  • 1 OASIcs

  • Refine by Classification
  • 1 Computing methodologies → Description logics
  • 1 Computing methodologies → Nonmonotonic, default reasoning and belief revision
  • 1 Computing methodologies → Reasoning about belief and knowledge
  • 1 Information systems → Data cleaning
  • 1 Information systems → Relational database query languages
  • Show More...

  • Refine by Keyword
  • 1 Knowledge bases
  • 1 bag semantics
  • 1 certain answers
  • 1 complexity
  • 1 conjunctive regular path queries
  • 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