Selected Publications (2002 -)

• My publications in Google Scholar.
• My publications in DBLP.

2008

• Conditioning Probabilistic Databases
  Christoph Koch and Dan Olteanu.
  To appear in Proc. VLDB 2008. CoRR Technical Report arXiv:0803.2212.

• Approximating Predicates and Expressive Queries on Probabilistic Databases
  Christoph Koch.
  Proc. PODS 2008 (PDF file).

• XML Prefiltering as a String Matching Problem
  Christoph Koch, Stefanie Scherzinger, and Michael Schmidt.
  Proc. ICDE 2008. (PDF file).

• Fast and Simple Relational Processing of Uncertain Data.
  Lyublena Antova, Thomas Jansen, Christoph Koch, Dan Olteanu.
  Proc. ICDE 2008. (PDF file).
  

• Query Evaluation on Compressed Trees.
  Markus Frick, Martin Grohe, and Christoph Koch.
  To appear in Journal of Computer and System Sciences.
  (Journal version of LICS 2003 paper)

• XPath Leashed.
  Michael Benedikt and Christoph Koch.
  To appear in ACM Computing Surveys (PDF file).

• World-Set Decompositions: Expressiveness and Efficient Algorithms.
  Lyublena Antova, Christoph Koch, and Dan Olteanu.
  To appear in TCS (PDF file). Long version of ICDT 2007 paper.

2007

• Database Research Opportunities in Computer Games
  Walker White, Christoph Koch, Nitin Gupta, Johannes Gehrke, and Alan Demers.
  SIGMOD Record, September 2007. (PDF file).

• Efficient Algorithms for the Tree Homeomorphism Problem.
  Michaela Götz, Christoph Koch, and Wim Martens.
  Proc. DBPL 2007. (PDF file).

• The GCX System: Dynamic Buffer Minimization in Streaming XQuery Evaluation.
  Christoph Koch, Stefanie Scherzinger, and Michael Schmidt.
  Proc. VLDB 2007. Demo paper (PDF file).

• Query language support for incomplete information in the MayBMS system.
  Lyublena Antova, Christoph Koch, and Dan Olteanu.
  Proc. VLDB 2007. Demo paper (PDF file).

• Scaling Games to Epic Proportions.
  Alan Demers, Johannes Gehrke, Christoph Koch, Rajmohan Rajagopalan, and Walker White.
  Proc. SIGMOD 2007 (PDF file).

• Massively Multi-Query Join Processing in Publish/Subscribe Systems.
  Alan Demers, Johannes Gehrke, Mingsheng Hong, Christoph Koch, Mirek Riedewald, and Walker White.
  Proc. SIGMOD 2007 (PDF file).

• From Complete to Incomplete Information and Back.
  Lyublena Antova, Christoph Koch, and Dan Olteanu.
  Proc. SIGMOD 2007 (PDF file).

• Combined Static and Dynamic Analysis for Effective Buffer Minimization in Streaming XQuery Evaluation.
  Michael Schmidt, Stefanie Scherzinger, and Christoph Koch.
  Proc. ICDE 2007 (PDF file).

• 10^(10^6) Worlds and Beyond: Efficient Representation and Processing of Incomplete Information.
  Lyublena Antova, Christoph Koch, and Dan Olteanu.
  Proc. ICDE 2007 (extended version in CoRR).

• MayBMS: Managing Incomplete Information with Probabilistic World-Set Decompositions.
  Lyublena Antova, Christoph Koch, and Dan Olteanu.
  Proc. ICDE 2007. Demo Paper (PDF file).

• Attribute Grammars for Scalable Query Processing on XML Streams.
  Christoph Koch and Stefanie Scherzinger.
  VLDB Journal 16(3), July 2007.
  (Journal version of DBPL 2003 paper; online version)

• Tight Lower Bounds for Query Processing on Streaming and External Memory Data.
  Martin Grohe, Christoph Koch, and Nicole Schweikardt.
  Theoretical Computer Science 380(1-2):199-217, June 2007 (PDF file).

• World-Set Decompositions: Expressiveness and Efficient Algorithms.
  Lyublena Antova, Christoph Koch, and Dan Olteanu.
  Proc. ICDT 2007 (PDF file -- extended version to appear in TCS).

2006

• Building a Native XML-DBMS as a Term Project in a Database Systems Course.
  Christoph Koch, Dan Olteanu, and Stefanie Scherzinger.
  Proc. XIME-P 2006 (124kB PDF file).

• Interpreting Tree-to-tree Queries.
  Michael Benedikt and Christoph Koch.
  Proc. ICALP 2006.
  Long version "From XQuery to Relational Logics and Back" (561kB .ps)

• Processing Queries on Tree-Structured Data Efficiently.
  Christoph Koch.
  Proc. PODS 2006, pp.213-224 (invited paper, 245 kB PDF file; slides).

• On the Complexity of Nonrecursive XQuery and Functional Query Languages on Complex Values.
  Christoph Koch.
  TODS 31(4), Dec. 2006.
  (Journal version of PODS 2005 paper; 496 kB PDF file -- preliminary version).

• Conjunctive Queries over Trees.
  Georg Gottlob, Christoph Koch, and Klaus U. Schulz.
  Journal of the ACM 53(2), March 2006.
  (Journal version of PODS 2004 paper; 388 kB PDF file).

• A Visual Query Language for Complex-Value Databases.
  Christoph Koch.
  http://arxiv.org/abs/cs.DB/0602006

2005

• On the role of composition in XQuery.
  Christoph Koch.
  Proc. WebDB 2005. (103 kB PDF file)

• Tight Lower Bounds for Query Processing on Streaming and External Memory Data.
  Martin Grohe, Christoph Koch, and Nicole Schweikardt.
  Proc. ICALP 2005 (Best Paper Award - ICALP Track B / Logic, Semantics and Theory of Programming; 182 kB PDF file)

• On the Complexity of Nonrecursive XQuery and Functional Query Languages on Complex Values.
  Christoph Koch.
  Proc. PODS 2005. (229 kB PDF file; long version: 496 kB PDF file)

• Efficient Algorithms for Processing XPath Queries.
  Georg Gottlob, Christoph Koch, and Reinhard Pichler.
  TODS 30(2), June 2005.
  (Journal version of VLDB 2002 and ICDE 2003 papers. 443 kB PDF file)

• The Complexity of XPath Query Evaluation and XML Typing.
  Georg Gottlob, Christoph Koch, Reinhard Pichler, and Luc Segoufin.
  Journal of the ACM 52(2), March 2005.
  (Journal version of two PODS2003 papers. 423 kB PDF file)

• The Complexity of Querying External Memory and Streaming Data.
  Martin Grohe, Christoph Koch, and Nicole Schweikardt.
  Proc. FCT, 2005.

2004

• Schema-based Scheduling of Event Processors and Buffer Minimization for Queries on Structured Data Streams.
  Christoph Koch, Stefanie Scherzinger, Nicole Schweikardt, and Bernhard Stegmaier.
  Proc. VLDB 2004. (220kB PDF file, extended version in CoRR, errata).

• FluXQuery: An Optimizing XQuery Processor for Streaming XML Data.
  Christoph Koch, Stefanie Scherzinger, Nicole Schweikardt, and Bernhard Stegmaier.
  Proc. VLDB 2004. Demo paper. (101kB PDF file).

• Logic-based Web Information Extraction.
  Georg Gottlob and Christoph Koch.
  SIGMOD Record, 33(2), June 2004. (158kB PDF file).

• The Lixto Data Extraction Project - Back and Forth between Theory and Practice.
  Georg Gottlob, Christoph Koch, Robert Baumgartner, Marcus Herzog, and Sergio Flesca.
  Proc. PODS 2004. Invited paper. (398kB PDF file).

• Conjunctive Queries over Trees.
  Georg Gottlob, Christoph Koch, and Klaus U. Schulz.
  Proc. PODS 2004. (232kB PDF file; long version in JACM: 388 kB PDF file).

• Monadic Datalog and the Expressive Power of Languages for Web Information Extraction.
  Georg Gottlob and Christoph Koch.
  Journal of the ACM, 51(1):74-113, January 2004.
  (Journal version of PODS 2002 paper. CoRR Report arXiv:cs.DB/0211020: 449kB PDF file).

• Query Rewriting with Symmetric Constraints.
  Christoph Koch.
  AI Communications, 17(2), 2004.
  (Journal version of FoIKS 2002 paper: 221kB PDF file).

2003

• Enhancing Disjunctive Logic Programming Systems by SAT Checkers.
  Christoph Koch, Nicola Leone, and Gerald Pfeifer.
  Artificial Intelligence, 151(1-2):177-212, December 2003.
  (Journal version of IJCAI 1999 paper; 479kB PDF file - Elsevier site)

• Attribute Grammars for Scalable Query Processing on XML Streams.
  Christoph Koch and Stefanie Scherzinger.
  Proc. DBPL 2003. (209kB PDF file).

• Efficient Processing of Expressive Node-Selecting Queries on XML Data in Secondary Storage: A Tree Automata-based Approach.
  Christoph Koch.
  Proc. VLDB 2003. (242kB PDF file).

• Path Queries on Compressed XML.
  Peter Buneman, Martin Grohe, and Christoph Koch.
  Proc. VLDB 2003. (227kB PDF file).

• XPath Processing in a Nutshell.
  Georg Gottlob, Christoph Koch, and Reinhard Pichler.
  SIGMOD Record, 32(2), June 2003. (193kB PDF file).

• Query Evaluation on Compressed Trees.
  Markus Frick, Martin Grohe, and Christoph Koch.
  Proc. LICS 2003. (183kB PDF file; Extended version: 271kB PDF file).

• The Complexity of XPath Query Evaluation.
  Georg Gottlob, Christoph Koch, and Reinhard Pichler.
  Proc. PODS 2003. (214kB PDF file).

• XPath Query Evaluation: Improving Time and Space Efficiency.
  Georg Gottlob, Christoph Koch, and Reinhard Pichler.
  Proc. ICDE 2003. (185kB PDF file).

2002

• Monadic Queries over Tree-Structured Data.
  Georg Gottlob and Christoph Koch.
  Proc. LICS 2002. (168kB PDF file)

• Efficient Algorithms for Processing XPath Queries.
  Georg Gottlob, Christoph Koch, and Reinhard Pichler.
  Proc. VLDB 2002. (254kB PDF file; Extended version: 256kB PDF file)

• Monadic Datalog and the Expressive Power of Languages for Web Information Extraction.
  Georg Gottlob and Christoph Koch.
  Proc. PODS 2002, Best Paper Award (227kB PDF file).

• Query Rewriting with Symmetric Constraints.
  Christoph Koch.
  Proc. FoIKS 2002. (246kB PDF file)