Search Results

Documents authored by Roy, Sudeepa

Document
DOI: 10.4230/DagRep.14.1.49
Representation, Provenance, and Explanations in Database Theory and Logic (Dagstuhl Seminar 24032)

Authors: Pablo Barcelo, Pierre Bourhis, Stefan Mengel, and Sudeepa Roy

Published in: Dagstuhl Reports, Volume 14, Issue 1 (2024)

Abstract
This report documents the program and the outcomes of Dagstuhl Seminar "Representation, Provenance, and Explanations in Database Theory and Logic" (24032), which was broadly in the area of database theory. Database theory formalizes the theoretical underpinnings of databases and analyzes them with mathematical tools. We focused on questions related to the fundamental problem of efficient query evaluation: compute the answers of a query on a database. This seminar focused on three key aspects of query evaluations. (1) Representation studies the tradeoff between expressivity, compactness, and efficient computation of outputs from the inputs, including circuits and knowledge compilation forms, enumeration, and direct access. (2) Provenance captures the computation process of outputs from the inputs using a compact formula, and has applications to probabilistic databases. (3) Explanations give meaningful insights to responsibilities of different inputs toward an output beyond provenance, e.g., by using Shapley Values from co-operative game theory that has been recently popular in both DB and ML.
Cite as

Pablo Barcelo, Pierre Bourhis, Stefan Mengel, and Sudeepa Roy. Representation, Provenance, and Explanations in Database Theory and Logic (Dagstuhl Seminar 24032). In Dagstuhl Reports, Volume 14, Issue 1, pp. 49-71, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2024)

Copy BibTex To Clipboard

@Article{barcelo_et_al:DagRep.14.1.49,
  author =	{Barcelo, Pablo and Bourhis, Pierre and Mengel, Stefan and Roy, Sudeepa},
  title =	{{Representation, Provenance, and Explanations in Database Theory and Logic (Dagstuhl Seminar 24032)}},
  pages =	{49--71},
  journal =	{Dagstuhl Reports},
  ISSN =	{2192-5283},
  year =	{2024},
  volume =	{14},
  number =	{1},
  editor =	{Barcelo, Pablo and Bourhis, Pierre and Mengel, Stefan and Roy, Sudeepa},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops.dagstuhl.de/entities/document/10.4230/DagRep.14.1.49},
  URN =		{urn:nbn:de:0030-drops-204904},
  doi =		{10.4230/DagRep.14.1.49},
  annote =	{Keywords: Circuits, database theory, factorized databases, provenance, shapley values}
}
Document
Invited Talk
DOI: 10.4230/LIPIcs.ICDT.2024.2
How Database Theory Helps Teach Relational Queries in Database Education (Invited Talk)

Authors: Sudeepa Roy, Amir Gilad, Yihao Hu, Hanze Meng, Zhengjie Miao, Kristin Stephens-Martinez, and Jun Yang

Published in: LIPIcs, Volume 290, 27th International Conference on Database Theory (ICDT 2024)

Abstract
Data analytics skills have become an indispensable part of any education that seeks to prepare its students for the modern workforce. Essential in this skill set is the ability to work with structured relational data. Relational queries are based on logic and may be declarative in nature, posing new challenges to novices and students. Manual teaching resources being limited and enrollment growing rapidly, automated tools that help students debug queries and explain errors are potential game-changers in database education. We present a suite of tools built on the foundations of database theory that has been used by over 1600 students in database classes at Duke University, showcasing a high-impact application of database theory in database education.
Cite as

Sudeepa Roy, Amir Gilad, Yihao Hu, Hanze Meng, Zhengjie Miao, Kristin Stephens-Martinez, and Jun Yang. How Database Theory Helps Teach Relational Queries in Database Education (Invited Talk). In 27th International Conference on Database Theory (ICDT 2024). Leibniz International Proceedings in Informatics (LIPIcs), Volume 290, pp. 2:1-2:9, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2024)

Copy BibTex To Clipboard

@InProceedings{roy_et_al:LIPIcs.ICDT.2024.2,
  author =	{Roy, Sudeepa and Gilad, Amir and Hu, Yihao and Meng, Hanze and Miao, Zhengjie and Stephens-Martinez, Kristin and Yang, Jun},
  title =	{{How Database Theory Helps Teach Relational Queries in Database Education}},
  booktitle =	{27th International Conference on Database Theory (ICDT 2024)},
  pages =	{2:1--2:9},
  series =	{Leibniz International Proceedings in Informatics (LIPIcs)},
  ISBN =	{978-3-95977-312-6},
  ISSN =	{1868-8969},
  year =	{2024},
  volume =	{290},
  editor =	{Cormode, Graham and Shekelyan, Michael},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.ICDT.2024.2},
  URN =		{urn:nbn:de:0030-drops-197841},
  doi =		{10.4230/LIPIcs.ICDT.2024.2},
  annote =	{Keywords: Query Debugging, SQL, Relational Algebra, Relational Calculus, Database Education, Boolean Provenance}
}
Document
DOI: 10.4230/LIPIcs.ICDT.2015.76
Answering Conjunctive Queries with Inequalities

Authors: Paraschos Koutris, Tova Milo, Sudeepa Roy, and Dan Suciu

Published in: LIPIcs, Volume 31, 18th International Conference on Database Theory (ICDT 2015)

Abstract
In this parer, we study the complexity of answering conjunctive queries (CQ) with inequalities. In particular, we compare the complexity of the query with and without inequalities. The main contribution of our work is a novel combinatorial technique that enables the use of any Select-Project-Join query plan for a given CQ without inequalities in answering the CQ with inequalities, with an additional factor in running time that only depends on the query. To achieve this, we define a new projection operator that keeps a small representation (independent of the size of the database) of the set of input tuples that map to each tuple in the output of the projection; this representation is used to evaluate all the inequalities in the query. Second, we generalize a result by Papadimitriou-Yannakakis [PODS'97] and give an alternative algorithm based on the color-coding technique [Alon, Yuster and Zwick, PODS'02] to evaluate a CQ with inequalities by using an algorithm for the CQ without inequalities. Third, we investigate the structure of the query graph, inequality graph, and the augmented query graph with inequalities, and show that even if the query and the inequality graphs have bounded treewidth, the augmented graph not only can have an unbounded treewidth but can also be NP-hard to evaluate. Further, we illustrate classes of queries and inequalities where the augmented graphs have unbounded treewidth, but the CQ with inequalities can be evaluated in poly-time. Finally, we give necessary properties and sufficient properties that allow a class of CQs to have poly-time combined complexity with respect to any inequality pattern.
Cite as

Paraschos Koutris, Tova Milo, Sudeepa Roy, and Dan Suciu. Answering Conjunctive Queries with Inequalities. In 18th International Conference on Database Theory (ICDT 2015). Leibniz International Proceedings in Informatics (LIPIcs), Volume 31, pp. 76-93, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2015)

Copy BibTex To Clipboard

@InProceedings{koutris_et_al:LIPIcs.ICDT.2015.76,
  author =	{Koutris, Paraschos and Milo, Tova and Roy, Sudeepa and Suciu, Dan},
  title =	{{Answering Conjunctive Queries with Inequalities}},
  booktitle =	{18th International Conference on Database Theory (ICDT 2015)},
  pages =	{76--93},
  series =	{Leibniz International Proceedings in Informatics (LIPIcs)},
  ISBN =	{978-3-939897-79-8},
  ISSN =	{1868-8969},
  year =	{2015},
  volume =	{31},
  editor =	{Arenas, Marcelo and Ugarte, Mart{\'\i}n},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.ICDT.2015.76},
  URN =		{urn:nbn:de:0030-drops-49781},
  doi =		{10.4230/LIPIcs.ICDT.2015.76},
  annote =	{Keywords: query evaluation, conjunctive query, inequality, treewidth}
}
Document
DOI: 10.4230/LIPIcs.FSTTCS.2008.1758
STCON in Directed Unique-Path Graphs

Authors: Sampath Kannan, Sanjeev Khanna, and Sudeepa Roy

Published in: LIPIcs, Volume 2, IARCS Annual Conference on Foundations of Software Technology and Theoretical Computer Science (2008)

Abstract
We study the problem of space-efficient polynomial-time algorithms for {\em directed st-connectivity} (STCON). Given a directed graph $G$, and a pair of vertices $s, t$, the STCON problem is to decide if there exists a path from $s$ to $t$ in $G$. For general graphs, the best polynomial-time algorithm for STCON uses space that is only slightly sublinear. However, for special classes of directed graphs, polynomial-time poly-logarithmic-space algorithms are known for STCON. In this paper, we continue this thread of research and study a class of graphs called \emph{unique-path graphs with respect to source $s$}, where there is at most one simple path from $s$ to any vertex in the graph. For these graphs, we give a polynomial-time algorithm that uses $\tilde O(n^{\varepsilon})$ space for any constant $\varepsilon \in (0,1]$. We also give a polynomial-time, $\tilde O(n^\varepsilon)$-space algorithm to \emph{recognize} unique-path graphs. Unique-path graphs are related to configuration graphs of unambiguous log-space computations, but they can have some directed cycles. Our results may be viewed along the continuum of sublinear-space polynomial-time algorithms for STCON in different classes of directed graphs - from slightly sublinear-space algorithms for general graphs to $O(\log n)$ space algorithms for trees.
Cite as

Sampath Kannan, Sanjeev Khanna, and Sudeepa Roy. STCON in Directed Unique-Path Graphs. In IARCS Annual Conference on Foundations of Software Technology and Theoretical Computer Science. Leibniz International Proceedings in Informatics (LIPIcs), Volume 2, pp. 256-267, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2008)

Copy BibTex To Clipboard

@InProceedings{kannan_et_al:LIPIcs.FSTTCS.2008.1758,
  author =	{Kannan, Sampath and Khanna, Sanjeev and Roy, Sudeepa},
  title =	{{STCON in Directed Unique-Path Graphs}},
  booktitle =	{IARCS Annual Conference on Foundations of Software Technology and Theoretical Computer Science},
  pages =	{256--267},
  series =	{Leibniz International Proceedings in Informatics (LIPIcs)},
  ISBN =	{978-3-939897-08-8},
  ISSN =	{1868-8969},
  year =	{2008},
  volume =	{2},
  editor =	{Hariharan, Ramesh and Mukund, Madhavan and Vinay, V},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.FSTTCS.2008.1758},
  URN =		{urn:nbn:de:0030-drops-17589},
  doi =		{10.4230/LIPIcs.FSTTCS.2008.1758},
  annote =	{Keywords: Algorithm, complexity, st-connectivity}
}
Questions / Remarks / Feedback
X

Feedback for Dagstuhl Publishing


Thanks for your feedback!

Feedback submitted

Could not send message

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