Search Results

Documents authored by Koch, Christoph

Document
DOI: 10.4230/LIPIcs.ICDT.2022.16
Robustness Against Read Committed for Transaction Templates with Functional Constraints

Authors: Brecht Vandevoort, Bas Ketsman, Christoph Koch, and Frank Neven

Published in: LIPIcs, Volume 220, 25th International Conference on Database Theory (ICDT 2022)

Abstract
The popular isolation level Multiversion Read Committed (RC) trades some of the strong guarantees of serializability for increased transaction throughput. Sometimes, transaction workloads can be safely executed under RC obtaining serializability at the lower cost of RC. Such workloads are said to be robust against RC. Previous work has yielded a tractable procedure for deciding robustness against RC for workloads generated by transaction programs modeled as transaction templates. An important insight of that work is that, by more accurately modeling transaction programs, we are able to recognize larger sets of workloads as robust. In this work, we increase the modeling power of transaction templates by extending them with functional constraints, which are useful for capturing data dependencies like foreign keys. We show that the incorporation of functional constraints can identify more workloads as robust that otherwise would not be. Even though we establish that the robustness problem becomes undecidable in its most general form, we show that various restrictions on functional constraints lead to decidable and even tractable fragments that can be used to model and test for robustness against RC for realistic scenarios.
Cite as

Brecht Vandevoort, Bas Ketsman, Christoph Koch, and Frank Neven. Robustness Against Read Committed for Transaction Templates with Functional Constraints. In 25th International Conference on Database Theory (ICDT 2022). Leibniz International Proceedings in Informatics (LIPIcs), Volume 220, pp. 16:1-16:17, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2022)

Copy BibTex To Clipboard

@InProceedings{vandevoort_et_al:LIPIcs.ICDT.2022.16,
  author =	{Vandevoort, Brecht and Ketsman, Bas and Koch, Christoph and Neven, Frank},
  title =	{{Robustness Against Read Committed for Transaction Templates with Functional Constraints}},
  booktitle =	{25th International Conference on Database Theory (ICDT 2022)},
  pages =	{16:1--16:17},
  series =	{Leibniz International Proceedings in Informatics (LIPIcs)},
  ISBN =	{978-3-95977-223-5},
  ISSN =	{1868-8969},
  year =	{2022},
  volume =	{220},
  editor =	{Olteanu, Dan and Vortmeier, Nils},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.ICDT.2022.16},
  URN =		{urn:nbn:de:0030-drops-158905},
  doi =		{10.4230/LIPIcs.ICDT.2022.16},
  annote =	{Keywords: concurrency control, robustness, complexity}
}
Document
DOI: 10.4230/LIPIcs.ICDT.2020.19
Datalog with Negation and Monotonicity

Authors: Bas Ketsman and Christoph Koch

Published in: LIPIcs, Volume 155, 23rd International Conference on Database Theory (ICDT 2020)

Abstract
Positive Datalog has several nice properties that are lost when the language is extended with negation. One example is that fixpoints of positive Datalog programs are robust w.r.t. the order in which facts are inserted, which facilitates efficient evaluation of such programs in distributed environments. A natural question to ask, given a (stratified) Datalog program with negation, is whether an equivalent positive Datalog program exists. In this context, it is known that positive Datalog can express only a strict subset of the monotone queries, yet the exact relationship between the positive and monotone fragments of semi-positive and stratified Datalog was previously left open. In this paper, we complete the picture by showing that monotone queries expressible in semi-positive Datalog exist which are not expressible in positive Datalog. To provide additional insight into this gap, we also characterize a large class of semi-positive Datalog programs for which the dichotomy `monotone if and only if rewritable to positive Datalog' holds. Finally, we give best-effort techniques to reduce the amount of negation that is exhibited by a program, even if the program is not monotone.
Cite as

Bas Ketsman and Christoph Koch. Datalog with Negation and Monotonicity. In 23rd International Conference on Database Theory (ICDT 2020). Leibniz International Proceedings in Informatics (LIPIcs), Volume 155, pp. 19:1-19:18, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2020)

Copy BibTex To Clipboard

@InProceedings{ketsman_et_al:LIPIcs.ICDT.2020.19,
  author =	{Ketsman, Bas and Koch, Christoph},
  title =	{{Datalog with Negation and Monotonicity}},
  booktitle =	{23rd International Conference on Database Theory (ICDT 2020)},
  pages =	{19:1--19:18},
  series =	{Leibniz International Proceedings in Informatics (LIPIcs)},
  ISBN =	{978-3-95977-139-9},
  ISSN =	{1868-8969},
  year =	{2020},
  volume =	{155},
  editor =	{Lutz, Carsten and Jung, Jean Christoph},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.ICDT.2020.19},
  URN =		{urn:nbn:de:0030-drops-119432},
  doi =		{10.4230/LIPIcs.ICDT.2020.19},
  annote =	{Keywords: Datalog, Monotonicity}
}
Document
DOI: 10.4230/LIPIcs.ICALP.2016.147
Bootstrap Percolation on Geometric Inhomogeneous Random Graphs

Authors: Christoph Koch and Johannes Lengler

Published in: LIPIcs, Volume 55, 43rd International Colloquium on Automata, Languages, and Programming (ICALP 2016)

Abstract
Geometric inhomogeneous random graphs (GIRGs) are a model for scale-free networks with underlying geometry. We study bootstrap percolation on these graphs, which is a process modelling the spread of an infection of vertices starting within a (small) local region. We show that the process exhibits a phase transition in terms of the initial infection rate in this region. We determine the speed of the process in the supercritical case, up to lower order terms, and show that its evolution is fundamentally influenced by the underlying geometry. For vertices with given position and expected degree, we determine the infection time up to lower order terms. Finally, we show how this knowledge can be used to contain the infection locally by removing relatively few edges from the graph. This is the first time that the role of geometry on bootstrap percolation is analysed mathematically for geometric scale-free networks.
Cite as

Christoph Koch and Johannes Lengler. Bootstrap Percolation on Geometric Inhomogeneous Random Graphs. In 43rd International Colloquium on Automata, Languages, and Programming (ICALP 2016). Leibniz International Proceedings in Informatics (LIPIcs), Volume 55, pp. 147:1-147:15, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2016)

Copy BibTex To Clipboard

@InProceedings{koch_et_al:LIPIcs.ICALP.2016.147,
  author =	{Koch, Christoph and Lengler, Johannes},
  title =	{{Bootstrap Percolation on Geometric Inhomogeneous Random Graphs}},
  booktitle =	{43rd International Colloquium on Automata, Languages, and Programming (ICALP 2016)},
  pages =	{147:1--147:15},
  series =	{Leibniz International Proceedings in Informatics (LIPIcs)},
  ISBN =	{978-3-95977-013-2},
  ISSN =	{1868-8969},
  year =	{2016},
  volume =	{55},
  editor =	{Chatzigiannakis, Ioannis and Mitzenmacher, Michael and Rabani, Yuval and Sangiorgi, Davide},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.ICALP.2016.147},
  URN =		{urn:nbn:de:0030-drops-62918},
  doi =		{10.4230/LIPIcs.ICALP.2016.147},
  annote =	{Keywords: Geometric inhomogeneous random graphs, scale-free network, bootstrap percolation, localised infection process, metastability threshold}
}
Document
DOI: 10.4230/LIPIcs.SNAPL.2015.238
Go Meta! A Case for Generative Programming and DSLs in Performance Critical Systems

Authors: Tiark Rompf, Kevin J. Brown, HyoukJoong Lee, Arvind K. Sujeeth, Manohar Jonnalagedda, Nada Amin, Georg Ofenbeck, Alen Stojanov, Yannis Klonatos, Mohammad Dashti, Christoph Koch, Markus Püschel, and Kunle Olukotun

Published in: LIPIcs, Volume 32, 1st Summit on Advances in Programming Languages (SNAPL 2015)

Abstract
Most performance critical software is developed using very low-level techniques. We argue that this needs to change, and that generative programming is an effective avenue to enable the use of high-level languages and programming techniques in many such circumstances.
Cite as

Tiark Rompf, Kevin J. Brown, HyoukJoong Lee, Arvind K. Sujeeth, Manohar Jonnalagedda, Nada Amin, Georg Ofenbeck, Alen Stojanov, Yannis Klonatos, Mohammad Dashti, Christoph Koch, Markus Püschel, and Kunle Olukotun. Go Meta! A Case for Generative Programming and DSLs in Performance Critical Systems. In 1st Summit on Advances in Programming Languages (SNAPL 2015). Leibniz International Proceedings in Informatics (LIPIcs), Volume 32, pp. 238-261, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2015)

Copy BibTex To Clipboard

@InProceedings{rompf_et_al:LIPIcs.SNAPL.2015.238,
  author =	{Rompf, Tiark and Brown, Kevin J. and Lee, HyoukJoong and Sujeeth, Arvind K. and Jonnalagedda, Manohar and Amin, Nada and Ofenbeck, Georg and Stojanov, Alen and Klonatos, Yannis and Dashti, Mohammad and Koch, Christoph and P\"{u}schel, Markus and Olukotun, Kunle},
  title =	{{Go Meta! A Case for Generative Programming and DSLs in Performance Critical Systems}},
  booktitle =	{1st Summit on Advances in Programming Languages (SNAPL 2015)},
  pages =	{238--261},
  series =	{Leibniz International Proceedings in Informatics (LIPIcs)},
  ISBN =	{978-3-939897-80-4},
  ISSN =	{1868-8969},
  year =	{2015},
  volume =	{32},
  editor =	{Ball, Thomas and Bodík, Rastislav and Krishnamurthi, Shriram and Lerner, Benjamin S. and Morriset, Greg},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.SNAPL.2015.238},
  URN =		{urn:nbn:de:0030-drops-50295},
  doi =		{10.4230/LIPIcs.SNAPL.2015.238},
  annote =	{Keywords: Performance, Generative Programming, Staging, DSLs}
}
Document
DOI: 10.4230/DagSemProc.08421.1
08421 Abstracts Collection – Uncertainty Management in Information Systems

Authors: Christoph Koch, Birgitta König-Ries, Volker Markl, and Maurice van Keulen

Published in: Dagstuhl Seminar Proceedings, Volume 8421, Uncertainty Management in Information Systems (2009)

Abstract
From October 12 to 17, 2008 the Dagstuhl Seminar 08421 '`Uncertainty Management in Information Systems '' was held in Schloss Dagstuhl~--~Leibniz Center for Informatics. The abstracts of the plenary and session talks given during the seminar as well as those of the shown demos are put together in this paper.
Cite as

Christoph Koch, Birgitta König-Ries, Volker Markl, and Maurice van Keulen. 08421 Abstracts Collection – Uncertainty Management in Information Systems. In Uncertainty Management in Information Systems. Dagstuhl Seminar Proceedings, Volume 8421, pp. 1-25, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2009)

Copy BibTex To Clipboard

@InProceedings{koch_et_al:DagSemProc.08421.1,
  author =	{Koch, Christoph and K\"{o}nig-Ries, Birgitta and Markl, Volker and van Keulen, Maurice},
  title =	{{08421 Abstracts Collection – Uncertainty Management in Information Systems }},
  booktitle =	{Uncertainty Management in Information Systems},
  pages =	{1--25},
  series =	{Dagstuhl Seminar Proceedings (DagSemProc)},
  ISSN =	{1862-4405},
  year =	{2009},
  volume =	{8421},
  editor =	{Christoph Koch and Birgitta K\"{o}nig-Ries and Volker Markl and Maurice van Keulen},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops.dagstuhl.de/entities/document/10.4230/DagSemProc.08421.1},
  URN =		{urn:nbn:de:0030-drops-19428},
  doi =		{10.4230/DagSemProc.08421.1},
  annote =	{Keywords: Uncertainty management}
}
Document
DOI: 10.4230/DagSemProc.08421.2
08421 Executive Summary – Uncertainty Management in Information Systems

Authors: Christoph Koch, Birgitta König-Ries, Volker Markl, and Maurice van Keulen

Published in: Dagstuhl Seminar Proceedings, Volume 8421, Uncertainty Management in Information Systems (2009)

Abstract
This executive summary provides a brief overview of the topic, the organization, and the outcome of the Dagstuhl Seminar on Uncertainty Management in Information Systems.
Cite as

Christoph Koch, Birgitta König-Ries, Volker Markl, and Maurice van Keulen. 08421 Executive Summary – Uncertainty Management in Information Systems. In Uncertainty Management in Information Systems. Dagstuhl Seminar Proceedings, Volume 8421, pp. 1-9, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2009)

Copy BibTex To Clipboard

@InProceedings{koch_et_al:DagSemProc.08421.2,
  author =	{Koch, Christoph and K\"{o}nig-Ries, Birgitta and Markl, Volker and van Keulen, Maurice},
  title =	{{08421 Executive Summary – Uncertainty Management in Information Systems }},
  booktitle =	{Uncertainty Management in Information Systems},
  pages =	{1--9},
  series =	{Dagstuhl Seminar Proceedings (DagSemProc)},
  ISSN =	{1862-4405},
  year =	{2009},
  volume =	{8421},
  editor =	{Christoph Koch and Birgitta K\"{o}nig-Ries and Volker Markl and Maurice van Keulen},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops.dagstuhl.de/entities/document/10.4230/DagSemProc.08421.2},
  URN =		{urn:nbn:de:0030-drops-19405},
  doi =		{10.4230/DagSemProc.08421.2},
  annote =	{Keywords: }
}
Document
DOI: 10.4230/DagSemProc.08421.3
08421 Working Group: Classification, Representation and Modeling

Authors: Anish Das Sarma, Ander de Keijzer, Amol Deshpande, Peter J. Haas, Ihab F. Ilyas, Christoph Koch, Thomas Neumann, Dan Olteanu, Martin Theobald, and Vasilis Vassalos

Published in: Dagstuhl Seminar Proceedings, Volume 8421, Uncertainty Management in Information Systems (2009)

Abstract
This report briefly summarizes the discussions carried out in the working group on classification, representation and modeling of uncertain data. The discussion was divided into two subgroups: the first subgroup studied how different representation and modeling alternatives currently proposed can fit in a bigger picture of theory and technology interaction, while the second subgroup focused on contrasting current system implementations and the reasons behind such diverse class of available prototypes. We summarize the findings of these two groups and the future steps suggested by group members.
Cite as

Anish Das Sarma, Ander de Keijzer, Amol Deshpande, Peter J. Haas, Ihab F. Ilyas, Christoph Koch, Thomas Neumann, Dan Olteanu, Martin Theobald, and Vasilis Vassalos. 08421 Working Group: Classification, Representation and Modeling. In Uncertainty Management in Information Systems. Dagstuhl Seminar Proceedings, Volume 8421, pp. 1-4, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2009)

Copy BibTex To Clipboard

@InProceedings{dassarma_et_al:DagSemProc.08421.3,
  author =	{Das Sarma, Anish and de Keijzer, Ander and Deshpande, Amol and Haas, Peter J. and Ilyas, Ihab F. and Koch, Christoph and Neumann, Thomas and Olteanu, Dan and Theobald, Martin and Vassalos, Vasilis},
  title =	{{08421 Working Group: Classification, Representation and Modeling}},
  booktitle =	{Uncertainty Management in Information Systems},
  pages =	{1--4},
  series =	{Dagstuhl Seminar Proceedings (DagSemProc)},
  ISSN =	{1862-4405},
  year =	{2009},
  volume =	{8421},
  editor =	{Christoph Koch and Birgitta K\"{o}nig-Ries and Volker Markl and Maurice van Keulen},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops.dagstuhl.de/entities/document/10.4230/DagSemProc.08421.3},
  URN =		{urn:nbn:de:0030-drops-19410},
  doi =		{10.4230/DagSemProc.08421.3},
  annote =	{Keywords: }
}
Document
DOI: 10.4230/DagSemProc.08421.7
08421 Working Group: Report of the Probabilistic Databases Benchmarking

Authors: Christoph Koch, Peter J. Haas, H.-J. Lenz, Dan Olteanu, Christopher Re, Maurice van Keulen, and Jeff Z. Pan

Published in: Dagstuhl Seminar Proceedings, Volume 8421, Uncertainty Management in Information Systems (2009)

Abstract
The results of the probabilistic database benchmark working group.
Cite as

Christoph Koch, Peter J. Haas, H.-J. Lenz, Dan Olteanu, Christopher Re, Maurice van Keulen, and Jeff Z. Pan. 08421 Working Group: Report of the Probabilistic Databases Benchmarking. In Uncertainty Management in Information Systems. Dagstuhl Seminar Proceedings, Volume 8421, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2009)

Copy BibTex To Clipboard

@InProceedings{koch_et_al:DagSemProc.08421.7,
  author =	{Koch, Christoph and Haas, Peter J. and Lenz, H.-J. and Olteanu, Dan and Re, Christopher and van Keulen, Maurice and Pan, Jeff Z.},
  title =	{{08421 Working Group: Report of the Probabilistic Databases Benchmarking}},
  booktitle =	{Uncertainty Management in Information Systems},
  series =	{Dagstuhl Seminar Proceedings (DagSemProc)},
  ISSN =	{1862-4405},
  year =	{2009},
  volume =	{8421},
  editor =	{Christoph Koch and Birgitta K\"{o}nig-Ries and Volker Markl and Maurice van Keulen},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops.dagstuhl.de/entities/document/10.4230/DagSemProc.08421.7},
  URN =		{urn:nbn:de:0030-drops-19367},
  doi =		{10.4230/DagSemProc.08421.7},
  annote =	{Keywords: Probabilistic databases, benchmark}
}
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