University of Oxford Logo University of OxfordDepartment of Computer Science - Home

Michael Benedikt — Selected Publications

All papers are in ps or gunzipped ps. There are several papers not linked or not listed: for these send e-mail to michael.benedikt@cs.ox.ac.uk

Foundations of Databases

    Papers
  1. "Monadic Datalog Containment" (with Pierre Bourhis and Pierre Senellart) In ICALP 2012.
  2. "HOMES: a higher-order mapping system" (with Huy Vu) VLDB 2011 demo.
  3. "Positive Higher Order Queries" (with Gabriele Puppis and Huy Vu) In PODS 2010.
  4. "The Impact of Virtual Views on Containment" (with Georg Gottlob) In VLDB 2010.
  5. "Complexity of Higher Order Queries" (with Huy Vu) In ICDT 2011.
  6. "Determining relevance of accesses at runtime" (with Georg Gottlob and Pierre Senellart) In PODS 2011.
  7. "Querying Schemas with Access Restrictions" (with Pierre Bourhis and Clemens Ley) To appear in VLDB 2012. A draft version is here.
    Book Chapters
  1. "Databases" (with Pierre Senellart) In E.K. Blum and A.V. Aho, editors, Computer Sceince, The Harware, Software, and Heart of It pp. 169 --229, Spring-Verlag, 2012

Tree and String Queries

  1. "A Model-Theoretic Approach to Regular String Relations" (with Luc Segoufin, Leonid Libkin and Thomas Schwentick) In LICS 2001.
  2. "String Operations in Query Languages" (with Luc Segoufin, Leonid Libkin and Thomas Schwentick) In PODS 2001.
  3. "Tree Extension Algebras: logics,automata, and query langauges" (with Leonid Libkin) In LICS 2002.

XML

Papers
  1. "Higher Order Functions and Structured Datatypes" (with Huy Vu) In WebDB 2012.
  2. "Probabilistic XML via Markov Chains" (with Evgeny Kharlamov, Dan Olteanu, and Pierre Senellart) In VLDB 2010.

  3. "Destabilizers and XML Updates" (with James Cheney) In VLDB 2010.

  4. "Schema-based Independence Analysis of XML Updates" (with James Cheney) In VLDB 2009.

  5. "How big must complete XML query languages be?" (with Clemens Ley) In ICDT 2009.
  6. "Semantics, Types and Effects for XML Updates" (with James Cheney) In DBPL 2009.

  7. "Interpreting Tree-to-Tree Queries" (with Christoph Koch) In ICALP 2006.

    One half of the full version of this paper will appear as ``From XQuery to Relational Logics '' , in TODS.

  8. "XML Subtree Queries: Specification and Composition" (with Irini Fundulaki) In DPBL 2005.
  9. "Satisfiability of XPath in the presence of DTDs" (with Wenfei Fan and Floris Geerts) In PODS 2005.
  10. "Adding Updates to XQuery: Semantics, Optmization, and Static Analysis" (with Angela Bonifati, Sergio Flesca, and Avinash Vyas) In XIME-P 2005.
  11. "Automated Update Management for XML" (with Glenn Bruns, Julie Gibson, Robin Kuss, and Amy Ng) In Programming Languages for XML (PLAN-X 2002).
  12. "Structural Properties of XPath Fragments" (with Wenfei Fan and Gabi Kuper). In Theoretical Computer Science.
  13. "DTD-directed publishing with Attribute Translation Grammars" (with Chee Yong Chan, Wenfei Fan, Rajeev Rastogi,Shihui Zheng, and Aoying Zhou). In VLDB 2002.
  14. "Capturing types and constraints in Data Exchange" (with Chee Yong Chan, Wenfei Fan, Juliana Freire, and Rajeev Rastogi). In SIGMOD 2003.
Surveys
  1. "XPath Leashed!" (with Christoph Koch), draft version of a survey on the XPath query language. To Appear in ACM Computing Surveys, March 2009.
  2. "Managing XML Data: An Abridged Overview" (with Juliana Freire) In CISE.

Stream Processing

  1. "Efficient and Expressive Tree Filters" (with Alan Jeffrey). In FSTTCS 2007.
  2. "Stream Firewalling of XML Constraints" (with Alan Jeffrey and Ruy Ley-Wild). In SIGMOD 2008.

Querying Social Networks

  1. "Challenges in Searching Online Communities" (with Sihem Amer-Yahia and Philip Bohannon) In Data Engineering Bulletin 2008.
  2. "Efficient Network-Aware Search in Collaborative Tagging Sites" (with Sihem Amer-Yahia, Julia Stoyanovich, and Laks Lakshmanan). In VLDB 2008.

Spatial Databases and Constraint Query Languages

Papers
  1. "A characterization of first-order topological properties of planar spatial databases" (with C. Loeding, J. Van den Bussche, and T. Wilke). In PODS 2004, with a journal version (joint with Bart Kuijpers) in JACM
  2. "Definability over Linear Constraints" (with H.J. Keisler). In CSL 2000.
  3. "Expressive power of constraint query languages" (with Guozhu Dong, Limsoon Wong, and Leonid Libkin, PODS 96). There's a journal version of this in JACM, 45 (1998)
  4. "On the structure of queries in constraint query languages" (with Leonid Libkin) LICS 96.
  5. "Relational queries over Interpreted Structure" (with Leonid Libkin) JACM, 1999.
  6. "Languages for Relational Databases over Interpreted Structures" (with Leonid Libkin) PODS 97.
  7. "Safe Constraint Queries" (with Leonid Libkin) PODS 98. The journal version of this is in SIAM Journal of Computing.
  8. "Exact and Approximate Aggregation in Constraint Databases" (with Leonid Libkin), PODS 99. Actually, I think what I've linked here is the journal version, which should appear in JCSS.
  9. "Reachability and Connectivity Queries in Constraint Databases" (with Martin Grohe, Leonid Libkin, and Luc Segoufin) PODS 2000.
Book Chapters
  1. "Expressive Power: The Finite Case" with Leonid Libkin in Constraint Databases (Kuper,Libkin, and Paradaens eds.)
  2. "Query Safety with Constraints" , with Leonid Libkin in Constraint Databases

Web Programming and Querying

  1. "MAWL: Integrated Web and Telephone Service Creation" (with Dave Atkins, Tom Ball, Tom Baran, Ken Cox, Dave Ladd, Carlos Puchol, Chris Ramming, Ken Rehor, and Curt Tuckey) In Bell Labs Technical Journal, Spring 97.
  2. "Experience with a Domain Specific Language for Form-based Services" (with Dave Atkins, Tom Ball, Glenn Bruns, Ken Rehor, Ken Cox, and Peter Mataga) Usenix Conference on Domain Specific Languages.
  3. QUASAR: Querying Annotation, Structure, and Reasoning. (with Luying Chen and Evgeny Kharlamov) EDBT 2012 Demonstration paper.
  4. ProFoUnd: Program-analysis-based Form Understanding. (with Tim Furche, Andreas Savvides, and Pierre Senellart) WWW 2012 Demonstration paper.

Verification

  1. "Verification of Two Variable Logic revisited" (with Rastislav Lenhardt and James Worrell). In QEST 2012.
  2. "Two variable vs. linear temporal logic in model checking and games" (with Rastislav Lenhardt and James Worrell). In Concur 2011.
  3. "Verification of Tree Updates for Optimization" (with Angela Bonifati, Sergio Flesca, and Avinash Vyas). In CAV 2005.
  4. "On Guard: Producing Run-Time Checks from Integrity Constraints" (with Glenn Bruns). In AMAST 2004.
  5. "Analysis of Recursive State Machines" (with Rajeev Alur, Kousha Etessami, Patrice Godefroid, Tom Reps, and Mihalis Yannakakis). To appear in TOPLAS.
  6. "VeriWeb: Automatically Testing Dynamic Web Sites" (with Juliana Freire and Patrice Godefroid) 11th international World Wide Web Conference.
  7. "Verifiable Properties of Database Transactions" (with Tim Griffin and Leonid Libkin, PODS 96). The journal version appeared in Information and Computation, 147 (1998).
  8. "Model-checking of Unrestricted Hierarchical State Machines" (with Patrice Godefroid and Tom Reps) In ICALP 2001.
  9. "A Decidable Logic for Describing Linked Data Structures" (with Mooly Sagiv and Tom Reps) ESOP 99.

Automata theory

  1. "Regular repair of Specifications" (with Gabriele Puppis and Cristian Riveros). In LICS 2011.
  2. "The cost of traveling between languages" (with Gabriele Puppis and Cristian Riveros). In ICALP 2011.

Model Theory

  1. "Towards a Characterization of Order-Invariant Queries over Tame Structures" (with Luc Segoufin), CSL 05.
  2. "Regular tree languages definable in FO" (with Luc Segoufin), STACS 05. What is linked is the extended version.
  3. "Expressive power of unary counters" (with H.J. Keisler), ICDT 97.
  4. "Embedded Finite Models, Stability, and the Impact of Order" (with John Baldwin, LICS 98). The journal version of this is in the Transactions of the American Mathematical Society.
  5. "Definability with a Predicate for a Semi-linear Set" (with H.J. Keisler). Journal of Symbolic Logic.

Ultrafilters and Applications to Nonstandard Analysis

  1. "Nonstandard Analysis and Special Ultrafilters", in Developments in Nonstandard Mathematics 1994
  2. "Ultrafilters that Extend Measures", Journal of Symbolic Logic, volume 63, 1998
  3. "Hierarchies of Measure-theoretic Ultrafilters", Annals of Pure and Applied Logic, 1999
michael.benedikt@cs.ox.ac.uk