2 Search Results for "Cucumides, Tamara"

Document
DOI: 10.4230/LIPIcs.ICDT.2024.5
Communication Cost of Joins over Federated Data

Authors: Tamara Cucumides and Juan Reutter

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

Abstract
We study the problem of querying different data sources, which we assume out of our control and that are made available by standard web communication protocols. In this scenario, the time spent communicating data often dominates the time spent processing local queries in each server. Thus, our focus is on algorithms that minimize the communication between the query processing server and the federated servers containing data. However, any federated query can always be answered with linear communication, simply by requesting all the data to the federated sources. Further, one can show that certain queries do require this amount of communication. But sending all the data is definitely not a relevant algorithm from a practical point of view. This worst-case analysis is, therefore, not useful for our needs. There is a growing body of work in terms of designing strategies that minimize communication in query federation, but these strategies are commonly based in heuristics, and we currently miss a formal analysis providing guidelines for the design of such strategies. We focus on the communication complexity of federated joins when the problem is parameterized by a measure commonly referred to as the certificate of the instance: a framework that has been used before in the context of set intersection and local query processing. We show how to process any conjunctive query in time given by the certificate of instances. Our algorithm is an adaptation of Minesweeper, one of the algorithms devised for local query processing, into our federating setting. When certificates are of the size of the instance, this amount to sending the entire database, but our strategy provides drastic reductions in the communication needed for queries and instances with small certificates. We also show matching communication lower bounds for cases where the certificate is smaller than the size of active domain of the instances.
Cite as

Tamara Cucumides and Juan Reutter. Communication Cost of Joins over Federated Data. In 27th International Conference on Database Theory (ICDT 2024). Leibniz International Proceedings in Informatics (LIPIcs), Volume 290, pp. 5:1-5:19, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2024)

Copy BibTex To Clipboard

@InProceedings{cucumides_et_al:LIPIcs.ICDT.2024.5,
  author =	{Cucumides, Tamara and Reutter, Juan},
  title =	{{Communication Cost of Joins over Federated Data}},
  booktitle =	{27th International Conference on Database Theory (ICDT 2024)},
  pages =	{5:1--5:19},
  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.5},
  URN =		{urn:nbn:de:0030-drops-197879},
  doi =		{10.4230/LIPIcs.ICDT.2024.5},
  annote =	{Keywords: databases, database queries, query federation, communication complexity, adaptive algorithms}
}
Document
DOI: 10.4230/LIPIcs.ICDT.2023.13
Size Bounds and Algorithms for Conjunctive Regular Path Queries

Authors: Tamara Cucumides, Juan Reutter, and Domagoj Vrgoč

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

Abstract
Conjunctive regular path queries (CRPQs) are one of the core classes of queries over graph databases. They are join intensive, inheriting their structure from the relational setting, but they also allow arbitrary length paths to connect points that are to be joined. However, despite their popularity, little is known about what are the best algorithms for processing CRPQs. We focus on worst-case optimal algorithms, which are algorithms that run in time bounded by the worst-case output size of queries, and have been recently deployed for simpler graph queries with very promising results. We show that the famous bound on the number of query results by Atserias, Grohe and Marx can be extended to CRPQs, but to obtain tight bounds one needs to work with slightly stronger cardinality profiles. We also discuss what algorithms follow from our analysis. If one pays the cost for fully materializing graph queries, then the techniques developed for conjunctive queries can be reused. If, on the other hand, one imposes constraint on the working memory of algorithms, then worst-case optimal algorithms must be adapted with care: the order of variables in which queries are processed can have striking implications on the running time of queries.
Cite as

Tamara Cucumides, Juan Reutter, and Domagoj Vrgoč. Size Bounds and Algorithms for Conjunctive Regular Path Queries. In 26th International Conference on Database Theory (ICDT 2023). Leibniz International Proceedings in Informatics (LIPIcs), Volume 255, pp. 13:1-13:17, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2023)

Copy BibTex To Clipboard

@InProceedings{cucumides_et_al:LIPIcs.ICDT.2023.13,
  author =	{Cucumides, Tamara and Reutter, Juan and Vrgo\v{c}, Domagoj},
  title =	{{Size Bounds and Algorithms for Conjunctive Regular Path Queries}},
  booktitle =	{26th International Conference on Database Theory (ICDT 2023)},
  pages =	{13:1--13:17},
  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-dev.dagstuhl.de/entities/document/10.4230/LIPIcs.ICDT.2023.13},
  URN =		{urn:nbn:de:0030-drops-177552},
  doi =		{10.4230/LIPIcs.ICDT.2023.13},
  annote =	{Keywords: graph databases, regular path queries, worst-case optimal algorithms}
}
  • Refine by Author
  • 2 Cucumides, Tamara
  • 2 Reutter, Juan
  • 1 Vrgoč, Domagoj

  • Refine by Classification
  • 1 Information systems → Query languages
  • 1 Information systems → Relational database query languages
  • 1 Theory of computation → Database query processing and optimization (theory)

  • Refine by Keyword
  • 1 adaptive algorithms
  • 1 communication complexity
  • 1 database queries
  • 1 databases
  • 1 graph databases
  • Show More...

  • Refine by Type
  • 2 document

  • Refine by Publication Year
  • 1 2023
  • 1 2024

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 Imprint Privacy Contact