5 Search Results for "Padmanabha, Anantha"

Document
DOI: 10.4230/LIPIcs.ICDT.2026.4
Computing Consistent Least Upper Bounds in Aggregate Logic

Authors: Aziz Amezian El Khalfioui and Jef Wijsen

Published in: LIPIcs, Volume 365, 29th International Conference on Database Theory (ICDT 2026)

Abstract
We consider the problem of answering conjunctive queries with aggregation on database instances that may violate primary key constraints. In SQL, these queries follow the SELECT-FROM-WHERE-GROUP BY format, where the WHERE clause involves a conjunction of equalities, and the SELECT clause can incorporate aggregate operators like MAX, MIN, SUM, AVG, or COUNT. Repairs of a database instance are defined as inclusion-maximal subsets that satisfy all primary keys. The range-consistent answer to a numerical query over an inconsistent database is a pair [glb, lub], where glb and lub are, respectively, the smallest and the greatest results returned by the query over all possible repairs. While previous work has focused on the computation of the glb, the current paper studies the computation of the lub for a numerical domain of non-negative rational numbers. We introduce the notion of κ-acyclicity for self-join-free conjunctive queries. We show that if the body of a SUM-query is κ-acyclic, then the lub can be computed through a rewriting in first-order aggregate logic. Moreover, we show that this result extends to all aggregate operators that are monotone and associative. Importantly, we also prove the inverse: if the body of a SUM-query is not κ-acyclic, then the lub cannot be computed in first-order aggregate logic.
Cite as

Aziz Amezian El Khalfioui and Jef Wijsen. Computing Consistent Least Upper Bounds in Aggregate Logic. In 29th International Conference on Database Theory (ICDT 2026). Leibniz International Proceedings in Informatics (LIPIcs), Volume 365, pp. 4:1-4:21, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2026)

Copy BibTex To Clipboard

@InProceedings{amezianelkhalfioui_et_al:LIPIcs.ICDT.2026.4,
  author =	{Amezian El Khalfioui, Aziz and Wijsen, Jef},
  title =	{{Computing Consistent Least Upper Bounds in Aggregate Logic}},
  booktitle =	{29th International Conference on Database Theory (ICDT 2026)},
  pages =	{4:1--4:21},
  series =	{Leibniz International Proceedings in Informatics (LIPIcs)},
  ISBN =	{978-3-95977-413-0},
  ISSN =	{1868-8969},
  year =	{2026},
  volume =	{365},
  editor =	{ten Cate, Balder and Funk, Maurice},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.ICDT.2026.4},
  URN =		{urn:nbn:de:0030-drops-256180},
  doi =		{10.4230/LIPIcs.ICDT.2026.4},
  annote =	{Keywords: Consistent query answering, primary key, conjunctive query, aggregate logic}
}
Document
DOI: 10.4230/LIPIcs.ICDT.2023.24
A Simple Algorithm for Consistent Query Answering Under Primary Keys

Authors: Diego Figueira, Anantha Padmanabha, Luc Segoufin, and Cristina Sirangelo

Published in: LIPIcs, Volume 255, 26th International Conference on Database Theory (ICDT 2023)

Abstract
We consider the dichotomy conjecture for consistent query answering under primary key constraints. It states that, for every fixed Boolean conjunctive query q, testing whether q is certain (i.e. whether it evaluates to true over all repairs of a given inconsistent database) is either polynomial time or coNP-complete. This conjecture has been verified for self-join-free and path queries. We propose a simple inflationary fixpoint algorithm for consistent query answering which, for a given database, naively computes a set Δ of subsets of database repairs with at most k facts, where k is the size of the query q. The algorithm runs in polynomial time and can be formally defined as: 1) Initialize Δ with all sets S of at most k facts such that S⊧ q. 2) Add any set S of at most k facts to Δ if there exists a block B (i.e., a maximal set of facts sharing the same key) such that for every fact a ∈ B there is a set S' ∈ Δ contained in S ∪ {a}. The algorithm answers "q is certain" iff Δ eventually contains the empty set. The algorithm correctly computes certainty when the query q falls in the polynomial time cases of the known dichotomies for self-join-free queries and path queries. For arbitrary Boolean conjunctive queries, the algorithm is an under-approximation: the query is guaranteed to be certain if the algorithm claims so. However, there are polynomial time certain queries (with self-joins) which are not identified as such by the algorithm.
Cite as

Diego Figueira, Anantha Padmanabha, Luc Segoufin, and Cristina Sirangelo. A Simple Algorithm for Consistent Query Answering Under Primary Keys. In 26th International Conference on Database Theory (ICDT 2023). Leibniz International Proceedings in Informatics (LIPIcs), Volume 255, pp. 24:1-24:18, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2023)

Copy BibTex To Clipboard

@InProceedings{figueira_et_al:LIPIcs.ICDT.2023.24,
  author =	{Figueira, Diego and Padmanabha, Anantha and Segoufin, Luc and Sirangelo, Cristina},
  title =	{{A Simple Algorithm for Consistent Query Answering Under Primary Keys}},
  booktitle =	{26th International Conference on Database Theory (ICDT 2023)},
  pages =	{24:1--24:18},
  series =	{Leibniz International Proceedings in Informatics (LIPIcs)},
  ISBN =	{978-3-95977-270-9},
  ISSN =	{1868-8969},
  year =	{2023},
  volume =	{255},
  editor =	{Geerts, Floris and Vandevoort, Brecht},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.ICDT.2023.24},
  URN =		{urn:nbn:de:0030-drops-177663},
  doi =		{10.4230/LIPIcs.ICDT.2023.24},
  annote =	{Keywords: consistent query answering, primary keys, conjunctive queries}
}
Document
DOI: 10.4230/LIPIcs.MFCS.2022.70
Generalized Bundled Fragments for First-Order Modal Logic

Authors: Mo Liu, Anantha Padmanabha, R. Ramanujam, and Yanjing Wang

Published in: LIPIcs, Volume 241, 47th International Symposium on Mathematical Foundations of Computer Science (MFCS 2022)

Abstract
When we bundle quantifiers and modalities together (as in ∃x□, ◇∀x etc.) in first-order modal logic (FOML), we get new logical operators whose combinations produce interesting bundled fragments of FOML. It is well-known that finding decidable fragments of FOML is hard, but existing work shows that certain bundled fragments are decidable [Anantha Padmanabha et al., 2018], without any restriction on the arity of predicates, the number of variables, or the modal scope. In this paper, we explore generalized bundles such as ∀x∀y□, ∀x∃y◇ etc., and map the terrain with regard to decidability, presenting both decidability and undecidability results. In particular, we propose the loosely bundled fragment, which is decidable over increasing domains and encompasses all known decidable bundled fragments.
Cite as

Mo Liu, Anantha Padmanabha, R. Ramanujam, and Yanjing Wang. Generalized Bundled Fragments for First-Order Modal Logic. In 47th International Symposium on Mathematical Foundations of Computer Science (MFCS 2022). Leibniz International Proceedings in Informatics (LIPIcs), Volume 241, pp. 70:1-70:14, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2022)

Copy BibTex To Clipboard

@InProceedings{liu_et_al:LIPIcs.MFCS.2022.70,
  author =	{Liu, Mo and Padmanabha, Anantha and Ramanujam, R. and Wang, Yanjing},
  title =	{{Generalized Bundled Fragments for First-Order Modal Logic}},
  booktitle =	{47th International Symposium on Mathematical Foundations of Computer Science (MFCS 2022)},
  pages =	{70:1--70:14},
  series =	{Leibniz International Proceedings in Informatics (LIPIcs)},
  ISBN =	{978-3-95977-256-3},
  ISSN =	{1868-8969},
  year =	{2022},
  volume =	{241},
  editor =	{Szeider, Stefan and Ganian, Robert and Silva, Alexandra},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.MFCS.2022.70},
  URN =		{urn:nbn:de:0030-drops-168684},
  doi =		{10.4230/LIPIcs.MFCS.2022.70},
  annote =	{Keywords: bundled fragments, first-order modal logic, decidability, tableaux}
}
Document
DOI: 10.4230/LIPIcs.MFCS.2019.30
Two variable fragment of Term Modal Logic

Authors: Anantha Padmanabha and R. Ramanujam

Published in: LIPIcs, Volume 138, 44th International Symposium on Mathematical Foundations of Computer Science (MFCS 2019)

Abstract
Term modal logics (TML) are modal logics with unboundedly many modalities, with quantification over modal indices, so that we can have formulas of the form Exists y Forall x (Box_x P(x,y) implies Diamond_y P(y,x)). Like First order modal logic, TML is also "notoriously" undecidable, in the sense that even very simple fragments are undecidable. In this paper, we show the decidability of one interesting fragment, that of two variable TML. This is in contrast to two-variable First order modal logic, which is undecidable.
Cite as

Anantha Padmanabha and R. Ramanujam. Two variable fragment of Term Modal Logic. In 44th International Symposium on Mathematical Foundations of Computer Science (MFCS 2019). Leibniz International Proceedings in Informatics (LIPIcs), Volume 138, pp. 30:1-30:14, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2019)

Copy BibTex To Clipboard

@InProceedings{padmanabha_et_al:LIPIcs.MFCS.2019.30,
  author =	{Padmanabha, Anantha and Ramanujam, R.},
  title =	{{Two variable fragment of Term Modal Logic}},
  booktitle =	{44th International Symposium on Mathematical Foundations of Computer Science (MFCS 2019)},
  pages =	{30:1--30:14},
  series =	{Leibniz International Proceedings in Informatics (LIPIcs)},
  ISBN =	{978-3-95977-117-7},
  ISSN =	{1868-8969},
  year =	{2019},
  volume =	{138},
  editor =	{Rossmanith, Peter and Heggernes, Pinar and Katoen, Joost-Pieter},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.MFCS.2019.30},
  URN =		{urn:nbn:de:0030-drops-109741},
  doi =		{10.4230/LIPIcs.MFCS.2019.30},
  annote =	{Keywords: Term modal logic, satisfiability problem, two variable fragment, decidability}
}
Document
DOI: 10.4230/LIPIcs.FSTTCS.2018.43
Bundled Fragments of First-Order Modal Logic: (Un)Decidability

Authors: Anantha Padmanabha, R Ramanujam, and Yanjing Wang

Published in: LIPIcs, Volume 122, 38th IARCS Annual Conference on Foundations of Software Technology and Theoretical Computer Science (FSTTCS 2018)

Abstract
Quantified modal logic is notorious for being undecidable, with very few known decidable fragments such as the monodic ones. For instance, even the two-variable fragment over unary predicates is undecidable. In this paper, we study a particular fragment, namely the bundled fragment, where a first-order quantifier is always followed by a modality when occurring in the formula, inspired by the proposal of [Yanjing Wang, 2017] in the context of non-standard epistemic logics of know-what, know-how, know-why, and so on. As always with quantified modal logics, it makes a significant difference whether the domain stays the same across possible worlds. In particular, we show that the predicate logic with the bundle "forall Box" alone is undecidable over constant domain interpretations, even with only monadic predicates, whereas having the "exists Box" bundle instead gives us a decidable logic. On the other hand, over increasing domain interpretations, we get decidability with both "forall Box" and "exists Box" bundles with unrestricted predicates, where we obtain tableau based procedures that run in PSPACE. We further show that the "exists Box" bundle cannot distinguish between constant domain and variable domain interpretations.
Cite as

Anantha Padmanabha, R Ramanujam, and Yanjing Wang. Bundled Fragments of First-Order Modal Logic: (Un)Decidability. In 38th IARCS Annual Conference on Foundations of Software Technology and Theoretical Computer Science (FSTTCS 2018). Leibniz International Proceedings in Informatics (LIPIcs), Volume 122, pp. 43:1-43:20, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2018)

Copy BibTex To Clipboard

@InProceedings{padmanabha_et_al:LIPIcs.FSTTCS.2018.43,
  author =	{Padmanabha, Anantha and Ramanujam, R and Wang, Yanjing},
  title =	{{Bundled Fragments of First-Order Modal Logic: (Un)Decidability}},
  booktitle =	{38th IARCS Annual Conference on Foundations of Software Technology and Theoretical Computer Science (FSTTCS 2018)},
  pages =	{43:1--43:20},
  series =	{Leibniz International Proceedings in Informatics (LIPIcs)},
  ISBN =	{978-3-95977-093-4},
  ISSN =	{1868-8969},
  year =	{2018},
  volume =	{122},
  editor =	{Ganguly, Sumit and Pandya, Paritosh},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.FSTTCS.2018.43},
  URN =		{urn:nbn:de:0030-drops-99424},
  doi =		{10.4230/LIPIcs.FSTTCS.2018.43},
  annote =	{Keywords: First-order modal logic, decidability, bundled fragments}
}
  • Refine by Type
  • 5 Document/PDF
  • 1 Document/HTML

  • Refine by Publication Year
  • 1 2026
  • 1 2023
  • 1 2022
  • 1 2019
  • 1 2018

  • Refine by Author
  • 4 Padmanabha, Anantha
  • 2 Ramanujam, R.
  • 2 Wang, Yanjing
  • 1 Amezian El Khalfioui, Aziz
  • 1 Figueira, Diego
  • Show More...

  • Refine by Series/Journal
  • 5 LIPIcs

  • Refine by Classification
  • 3 Theory of computation → Modal and temporal logics
  • 1 Information systems → Relational database query languages
  • 1 Theory of computation → Database query languages (principles)
  • 1 Theory of computation → Incomplete, inconsistent, and uncertain databases
  • 1 Theory of computation → Logic and databases
  • Show More...

  • Refine by Keyword
  • 3 decidability
  • 2 bundled fragments
  • 1 Consistent query answering
  • 1 First-order modal logic
  • 1 Term modal logic
  • 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-2026 Schloss Dagstuhl – LZI GmbH Schloss Dagstuhl – LZI GmbH About DROPS Imprint Privacy Contact