Publications by Jan Van den Bussche


DNA Computing

  1. "The DNA query language DNAQL", invited ICDT 2013 paper.
  2. "DNAQL: A query language for DNA sticker complexes" (R. Brijder, J. Gillis, J. Van den Bussche). Combined full version of ANB 2010 and DNA18 papers, submitted.
  3. "A type system for DNAQL" (R. Brijder, J. Gillis, J. Van den Bussche), presented at DNA18, Lecture Notes in Computer Science, volume 7433, 2012.
  4. "A comparison of graph-theoretic DNA hybridization models" (R. Brijder, J. Gillis, J. Van den Bussche), Theoretical Computer Science, vol 429, pages 46-–53, 2012.
  5. "Graph-theoretic formalization of hybridization in DNA sticker complexes" (R. Brijder, J. Gillis, J. Van den Bussche), Natural Computing. This is the journal version of the paper presented at DNA17.
  6. "A formal model for databases in DNA" (J. Gillis and J. Van den Bussche), presented at ANB 2010, Lecture Notes in Computer Science, volume 6479, 2012.

Dataflows and Provenance

  1. "Querying an integrated complex-object dataflow database" (N. Kwasnikowska, J. Van den Bussche). Peter Buneman Festschrift
  2. "A formal account of the Open Provenance Model" (L. Moreau, N. Kwasnikowska, J. Van den Bussche). University of Southampton ECS Technical Report 21819, December 2010.
  3. "The open provenance model core specification v1.1" (L. Moreau et al.) In Future Generation Computer Systems.
  4. "A graph model of data and workflow provenance" (U. Acar, P. Buneman, J. Cheney, J. Van den Bussche, N. Kwasnikowska, S. Vansummeren). Proceedings 2nd USENIX Workshop on the Theory and Practice of Provenance, 2010.
  5. "Relational completeness of query languages for annotated databases" (F. Geerts, J. Van den Bussche). Journal of Computer and System Sciences (special issue on DBPL 2007)
  6. "Mapping the NRC dataflow model to the open provenance model" (N. Kwasnikowska and J. Van den Bussche). Proceedings IPAW 2008, Lectures Notes in Computer Science, vol 5272, p 3-16, 2008.
  7. "A formal model of dataflow repositories" (J. Hidders, N. Kwasnikowska, J. Sroka, J. Tyszkiewicz, J. Van den Bussche). Proceedings DILS, Lecture Notes in Bioinformatics vol 4544, pages 105-121, 2007.
  8. "DFL: A dataflow languages based on Petri nets and nested relational calculus" (J. Hidders, N. Kwasnikowska, J. Sroka, J. Tyszkiewicz, J. Van den Bussche). Information Systems 33 (2008) 261-284. A preliminary version appeared as "Petri net + nested relational calculus = dataflow" in the proceedings of CoopIS 2005.

Spatial databases, constraint query languages

  1. "Linearization and completeness results for terminating transitive closure queries on spatial databases" (F. Geerts, B. Kuijpers, J. Van den Bussche). SIAM Journal on Computing, vol 35, no 6, pp 1386-1439, 2006.
  2. "First-order topological properties". Bulletin of the EATCS, vol 87, pp 155-164, 2005. (Logic in Computer Science Column)
  3. "A characterization of first-order topological properties of planar spatial data" (M. Benedikt, B. Kuijpers, C. Loeding, J. Van den Bussche, T. Wilke). Journal of the ACM, vol 53, no 2, p 273-305, 2006. Extended version of a paper presented at PODS 2004.
  4. "Two- versus three-dimensional connectivity testing of first-order queries to semi-algebraic sets" (F. Geerts, L. Smits, J. Van den Bussche). Acta Informatica, vol 42, no 1, pp 43-56, 2005.
  5. "Constraint databases: A tutorial introduction" (J. Van den Bussche). SIGMOD Record, vol 29, no 3, pp 44-51, 2000 (Database Principles column).
  6. "On-line topological simplification of weighted graphs" (F. Geerts, P. Revesz, J. Van den Bussche). Full version of the paper "On-Line Maintenance of Simplified Weighted Graphs for Efficient Distance Queries" presented at ACM GIS 2006.
  7. "Constraint databases, queries, and query languages" (J. Van den Bussche). Close-to-final version of the first chapter of Constraint Databases (G. Kuper, L. Libkin, J. Paredaens, editors), Springer, 2000.
  8. "On capturing first-order topological properties of planar spatial databases" (B. Kuijpers, J. Van den Bussche). In Database Theory, ICDT'99 (C. Beeri and P. Buneman, editors), Lecture Notes in Computer Science, vol 1540, pages 187--198, Springer, 1999.
  9. "Topological canonization of planar spatial data and its incremental maintenance" (F. Geerts, B. Kuijpers, J. Van den Bussche). In Fundamentals of Information Systems (T. Polle, T. Ripke, K.-D. Schewe, editors), Kluwer International Series in Engineering and Computer Science, vol 496, pages 55--68, 1999.
  10. "Complete geometrical query languages" (M. Gyssens, J. Van den Bussche, D. Van Gucht). Journal of Computer and System Sciences, vol 58, no 3, pages 483-511, 1999. (A preliminary version was presented at PODS'97.)
  11. "On topological elementary equivalence of closed semi-algebraic sets in the real plane" (B. Kuijpers, J. Paredaens, J. Van den Bussche). Journal of Symbolic Logic, vol 65, no 4, pages 1530-1555, 2000. (A preliminary version was presented at ICDT'97.)
  12. "Termination properties of spatial Datalog programs" (B. Kuijpers, J. Paredaens, M. Smits, J. Van den Bussche). Logic in Databases (D. Pedreschi, C. Zaniolo, editors), Lecture Notes in Computer Science, vol 1154, pages 101-116. Springer, 1997. (One direction of the theorem, on testing topological connectivity using the Datalog program of figure 4, is false. Border-visibility is not necessary, only sufficient, for soundness and termination of this program. One can also relax the definition of border-visibility and still get a sufficient condition. Details can be found in Bart Kuijpers's PhD thesis.)
  13. "First-order queries on databases embedded in an infinite structure" (M. Otto, J. Van den Bussche). Information Processing Letters, vol 60, pages 37-41, 1996.
  14. "First-order queries on finite structures over the reals" (J. Paredaens, J. Van den Bussche, D. Van Gucht). SIAM Journal on Computing, vol 27, no 6, pages 1747-1763, 1998. (A preliminary version was presented at LICS'95.)
  15. "Lossless representation of topological spatial data" (B. Kuijpers, J. Paredaens, J. Van den Bussche). Advances in Spatial Databases (M.J. Egenhofer, J.R. Herring, editors), Lecture Notes in Computer Science, vol 951, pages 1-13. Springer, 1995.
  16. "Towards a theory of spatial database queries" (J. Paredaens, J. Van den Bussche, D. Van Gucht). Proceedings 13th ACM Symposium on Principles of Database Systems, pages 279-288. ACM Press, 1994.

Object creation, semi-determinism, computationally complete query languages

  1. "On the completeness of object-creating database transformation languages" (J. Van den Bussche, D. Van Gucht, M. Andries, M. Gyssens). Journal of the ACM, vol 44, no 2, pages 272-319, 1997. (A preliminary version was presented at FOCS'92.)
  2. "The expressive power of complex values in object-based data models" (J. Van den Bussche, J. Paredaens). Information and Computation, vol 120, pages 220-236, 1995. (A preliminary version was presented at PODS'91.)
  3. "The expressive power of cardinality-bounded set values in object-based data models" (J. Van den Bussche, D. Van Gucht). Theoretical Computer Science, vol 149, no 1, pages 49-66, 1995. (A preliminary version was presented at ICDT'92.)
  4. "A semi-deterministic approach to object creation and non-determinism in database queries" (J. Van den Bussche, D. Van Gucht). Journal of Computer and System Sciences, vol 47, no 1, pages 34-47, 1997. (A preliminary version was presented at PODS'92.)
  5. "Expressiveness of efficient semi-deterministic choice constructs" (M. Gyssens, J. Van den Bussche, D. Van Gucht). Automata, Languages and Programming - ICALP'94 (S. Abiteboul, E. Shamir, editors), Lecture Notes in Computer Science, vol 820, pages 106-117. Springer, 1994. (A full version presenting polynomial-time semi-deterministic choice constructs that are more general than swap-choice, is in preparation.)
  6. "Non-deterministic aspects of database transformations involving object creation" (J. Van den Bussche, D. Van Gucht). Modeling Database Dynamics (U. Lipeck, B. Thalheim, editors), Workshops in Computing, pages 3-16. Springer, 1993.
  7. "A computational model for generic graph functions" (M. Gemis, J. Paredaens, P. Peelman, J. Van den Bussche). Graph Transformations in Computer Science (H.J. Schneider, H. Ehrig, editors), Lecture Notes in Computer Science, vol 776, pages 170-187. Springer, 1994.
  8. "Expressiveness and complexity of generic graph machines" (M. Gemis, J. Paredaens, P. Peelman, J. Van den Bussche). Theory of Computing Systems, vol 31, pages 231-249, 1998.
  9. "Abstract state machines and computationally complete query languages" (A. Blass, Y. Gurevich, J. Van den Bussche). Information and Computation, vol 174, no 1, p 20-36, 2002. An extended abstract appears in Abstract State Machines, Theory and Practice (Y. Gurevich, P.W. Kutter, M. Odersky, L. Thiele, editors), Lecture Notes in Computer Science, vol 1912, pages 22-33. Springer, 2000.
  10. "Tree-structured object creation in database transformations". Appeared in the Liber Amicorum for Jan Paredaens's 60th Birthday.


Programming aspects of query languages

  1. "Well-defined NRC queries can be typed" (J. Van den Bussche, S. Vansummeren). Peter Buneman Festschrift
  2. "Polymorphic type inference for the named nested relational calculus" (J. Van den Bussche, S. Vansummeren). ACM Transactions on Computational Logic, 9(1), 2007.
  3. "A crash course in database queries" (J. Van den Bussche, S. Vansummeren, D. Van Gucht). Proceedings 26th ACM Symposium on Principles of Database Systems, p 143-154, ACM Press, 2007. (Invited tutorial.)
  4. "Well-definedness and semantic type-checking for the nested relational calculus" (J. Van den Bussche, D. Van Gucht, S. Vansummeren). Theoretical Computer Science, vol 371, no 3, p 183-199, 2007. Full version of a paper presented at ICDT 2005.
  5. "Meta-SQL: Towards practical meta-querying" (J. Van den Bussche, S. Vansummeren, G. Vossen). System demonstration paper in Advances in Database Technology, EDBT 2004, Lecture Notes in Computer Science, vol 2992, pages 823-825. Springer, 2004.
  6. "Towards practical meta-querying" (J. Van den Bussche, S. Vansummeren, G. Vossen). Information Systems, vol 30, no 4, pages 317-332, 2005.
  7. "Methods and views" (J. Van den Bussche, E. Waller).
  8. "Polymorphic type inference for the relational algebra" (J. Van den Bussche, E. Waller). Journal of Computer and System Sciences, vol 64, p 694-718, 2002. (An extended abstract appeared in PODS'99 under the title "Type inference in the polymorphic relational algebra".)
  9. "Typed query languages for databases containing queries" (F. Neven, J. Van den Bussche, D. Van Gucht, G. Vossen). Information Systems, vol 24, no 7, pages 569-595, 1999. (A preliminary version was presented at PODS'98.)
  10. "Reflective programming in the relational algebra" (J. Van den Bussche, D. Van Gucht, G. Vossen). Journal of Computer and System Sciences, vol 52, no 3, pages 537-549, 1996. (A preliminary version was presented at PODS'93.)

Temporal query languages

  1. "Temporal connectives versus explicit timestamps to query temporal databases" (S. Abiteboul, L. Herr, J. Van den Bussche). Journal of Computer and System Sciences, vol 58, no 1, pages 54-68, 1999. (Combined full version of "Temporal connectives versus explicit timestamps in temporal query languages", Recent Advances in Temporal Databases (J. Clifford, A. Tuzhilin, editors), Workshops in Computing, pages 43-57, Springer, 1995, and "Temporal versus first-order logic to query temporal databases", Proceedings 15th ACM Symposium on Principles of Database Systems, pages 49-57, ACM Press, 1996.)

Querying and Searching Objects, XML, Graphs, RDF

  1. "On the satisfiability problem for SPARQL patterns" (X. Zhang and J. Van den Bussche). arXiv:1406.1404
  2. "On the primitivity of operators in SPARQL" (X. Zhang and J. Van den Bussche). In Information Processing Letters.
  3. "Similarity and bisimilarity notions appropriate for characterizing indistinguishability in fragments of the calculus of relations" (G.H.L. Fletcher, M. Gyssens, D. Leinders, J. Van den Bussche, D. Van Gucht, S. Vansummeren). Journal of Logic and Computation, published online, 2014.
  4. "Walk Logic as a framework for path query languages on graph databases" (J. Hellings, B. Kuijpers, J. Van den Bussche, X. Zhang). ICDT 2013.
  5. "The impact of transitive closure on the boolean expressiveness of navigational query languages on graphs" (G.H.L. Fletcher, M. Gyssens, D. Leinders, J. Van den Bussche, D. Van Gucht, S. Vansummeren, Y. Wu). Annals of Mathematics and Artificial Intellligence, special issue on FoIKS 2012.
  6. "Relative expressive power of navigational querying on graphs" (G.H.L. Fletcher, M. Gyssens, D. Leinders, J. Van den Bussche, D. Van Gucht, S. Vansummeren, Y. Wu). ICDT 2011.
  7. "Towards a theory of search queries" (G.H.L. Fletcher, J. Van den Bussche, D. Van Gucht, S. Vansummeren). In TODS.
  8. "On the tree-transformation power of XSLT" (W. Janssen, A. Korlyukov, J. Van den Bussche). Acta Informatica, vol 43, no 6, pp 371--393, 2007.
  9. "Expressiveness of structured document query languages based on attribute grammars" (F. Neven, J. Van den Bussche). Journal of the ACM, vol 49, no 1, p 56-100, 2002. (A preliminary version was presented at PODS'98.)
  10. "On implementing structured document query facilities on top of a DOOD" (F. Neven, J. Van den Bussche). Deductive and Object-Oriented Databases (F. Bry, R. Ramakrishnan, K. Ramamohanarao, editors), Lecture Notes in Computer Science, vol 1341, pages 351-367. Springer, 1997.
  11. "Deep equality revisited" (S. Abiteboul, J. Van den Bussche). Deductive and Object-Oriented Databases (T.W. Ling, A.O. Mendelzon, L. Vieille, editors), Lecture Notes in Computer Science, vol 1013, pages 213-228. Springer, 1995.
  12. "Applying an update method to a set of receivers" (M. Andries, L. Cabibbo, J. Paredaens, J. Van den Bussche). ACM Transactions on Database Systems, vol 25, no 1, pages 1-40, 2001. (A preliminary version was presented at PODS'95.)
  13. "A graph-oriented object database model" (M. Gyssens, J. Paredaens, J. Van den Bussche, D. Van Gucht). IEEE Transactions on Knowledge and Data Engineering, vol 6, no 4, pages 572-586, 1994.
  14. "GOOD: A graph-oriented object database system" (M. Gemis, J. Paredaens, I. Thyssens, J. Van den Bussche). Proceedings ACM SIGMOD'93 International Conference, pages 505-510. ACM Press, 1993. (Abstract of a video presentation.)
  15. "An extension of path expressions to simplify navigation in object-oriented queries" (J. Van den Bussche, G. Vossen). Deductive and Object-Oriented Databases (S. Ceri, K. Tanaka, S. Tsur, editors), Lecture Notes in Computer Science, vol 760, pages 267-282. Springer, 1993.
  16. "Using SQL with object-oriented databases" (J. Van den Bussche, A. Heuer). Information Systems, vol 18, no 7, pages 461-487, 1993.
  17. "Concepts for graph-oriented object manipulation" (M. Gemis, J. Paredaens, I. Thyssens, J. Van den Bussche). Advances in Database Technology - EDBT'92 (A. Pirotte, editor), Lecture Notes in Computer Science, vol 580, pages 21-38. Springer, 1992.
  18. "An overview of GOOD" (J. Paredaens, J. Van den Bussche, D. Van Gucht, et al.) SIGMOD Record, vol 21, no 1, pages 25-31, 1992.
  19. "A graph- and object-oriented counterpart for SQL" (M. Andries, J. Paredaens, J. Van den Bussche). Future Database '92 (Q. Chen, Y. Kambayashi, R. Sacks-Davis, editors), Advanced Database Research and Development, vol 3, pages 276-285. World Scientific, 1992.

Data mining

  1. "Expressive power of safe first-order logical decision trees" (J. Gillis and J. Van den Bussche). ILP 2011.
  2. "Induction of relational algebra expressions" (J. Gillis and J. Van den Bussche). ILP 2009.
  3. "Finding clusters of positive and negative coregulated genes in Gene expression data" (K. Koch, S. Schönauer, I. Jansen, J. Van den Bussche, T. Burzykowski). BIBE 2007.
  4. "Mining for trees in a graph is NP-complete". arXiv:0709.4655.
  5. "Mining tree-query associations in graphs". arXiv:1008.2626. Full version of two earlier conference papers presented at KDD 2005 and ICDM 2006.
  6. "Learning (k,l)-contextual tree languages for information extraction" (S. Raeymaekers, M. Bruynooghe, J. Van den Bussche). Machine Learning, vol 71, p 155--183, 2008. Full version of a paper presented at ECML 2005.
  7. "Information extraction from Web documents based on local unranked tree automaton inference" (R. Kosala, H. Blockeel, M. Bruynooghe, J. Van den Bussche). Presented at IJCAI 2003.
  8. "Information extraction from structured documents using k-testable tree automata induction" (R. Kosala, H. Blockeel, M. Bruynooghe, J. Van den Bussche). Data & Knowledge Engineering, vol 58, p 129-158, 2006. Extended version of a paper presented at PKDD 2002.
  9. "Relational association rules: Getting WARMeR" (B. Goethals, J. Van den Bussche). Proceedings ESF Exploratory Workshop on Pattern Detection and Discovery, Lecture Notes in Computer Science, volume 2447, pages 125-139, Springer, 2002.
  10. "A tight upper bound on the number of candidate patterns" (F. Geerts, B. Goethals, J. Van den Bussche). arXiv:cs.DB/0112007. ACM Transactions on Database Systems, 30(2)333-363, 2005. Extended version of a paper in Proceedings 2001 IEEE International Conference on Data Mining.
  11. "On supporting interactive association rule mining" (B. Goethals, J. Van den Bussche). Extended version of a paper in Data Warehousing and Knowledge Discovery (Y. Kambayashi, M.K. Mohania, A. Min Tjoa, editors), Lecture Notes in Computer Science, volume 1874, pages 307-316, Springer, 2000.
  12. "A priori versus a posteriori filtering of association rules" (B. Goethals, J. Van den Bussche). Presented at SIGMOD Workshop on Research Issues in Data Mining and Knowledge Discovery, 1999.

Distributed database and Web querying

  1. "On the CRON conjecture" (T.J. Ameloot, J. Van den Bussche), Datalog 2.0 Workshop, Vienna, 2012. Full version accepted for publication in JCSS: "Positive Dedalus programs tolerate non-causality"
  2. "A declarative semantics for Dedalus" (P. Alvaro, T.J. Ameloot, J.M. Hellerstein, W. Marczak, J. Van den Bussche). Improved version of UCBerkeley techreport.
  3. "Deciding eventual consistency for a simple class of relational transducer networks" (T. Ameloot, J. Van den Bussche), ICDT 2012.
  4. "Relational transducers for declarative networking" (T. Ameloot, F. Neven, J. Van den Bussche), JACM vol 60 no 2 (journal version of PODS 2011 paper).
  5. "The navigational power of Web browsers" (M. Bielecki, J. Hidders, J. Paredaens, M. Spielmann, J. Tyszkiewicz, J. Van den Bussche). In Theory of Computing Systems, doi: 10.1007/s00224-010-9294-3. This is an extended version of an earlier paper presented at ICALP 2002.
  6. "Database interrogation using conjunctive queries" (M. Bielecki, J. Van den Bussche). Database Theory, ICDT 2003, Lecture Notes in Computer Science, vol 2572, p 259-269, 2003.
  7. "Distributed computation of Web queries using automata" (M. Spielmann, J. Tyszkiewicz, J. Van den Bussche). Proceedings 21st ACM Symposium on Principles of Database Systems, p 97-108, 2002.

    Check out the system prototype accompanying the above paper!


Semijoin algebra

  1. "Repetitions and permutations of columns in the semijoin algebra" (D. Leinders, J. Van den Bussche). RAIRO Theoretical Informatics and Applications, volume 43, number 2, p 179--187, 2009.
  2. "Database query processing using finite cursor machines" (M. Grohe, Y. Gurevich, D. Leinders, N. Schweikardt, J. Tyszkiewicz, J. Van den Bussche). Theory of Computing Systems, volume 44, number 4, p 533--560, 2009 (special issue on ICDT 2007).
  3. "On the complexity of division and set joins in the relational algebra" (D. Leinders, J. Van den Bussche). Journal of Computer and System Sciences, vol 73, no 4, p 538--549, 2007. Full version of a paper presented at PODS 2005.
  4. "The semijoin algebra and the guarded fragment" (D. Leinders, M. Marx, J. Tyszkiewicz, J. Van den Bussche). Journal of Logic, Language and Information, vol 14, pages 331--343, 2005.
  5. "On the expressive power of semijoin queries" (D. Leinders, J. Tyszkiewicz, J. Van den Bussche). Information Processing Letters 91 (2004) 93-98.

Miscellaneous topics

  1. "On the expressive power of update primitives" (T.J. Ameloot, J. Van den Bussche, E. Waller). PODS 2013.
  2. "Quantitatively evaluating formula-variable relevance by forgetting" (X. Liang, Z. Lin, J. Van den Bussche). Canadian AI 2013.
  3. "Database Theory, Yuri, and Me". In Fields of Logic and Computation: Essays dedicated to Yuri Gurevich.
  4. "A theory of stream queries" (Y. Gurevich, D. Leinders, J. Van den Bussche). DBPL 2007.
  5. "Applications of Alfred Tarski's ideas in database theory" (J. Van den Bussche). In Computer Science Logic (L. Fribourg, editor), Lecture Notes in Computer Science, volume 2142, pages 20-37, Springer, 2001.
  6. "Rewriting queries using views over monadic database schemas" (J. Van den Bussche). Information Processing Letters, vol 79, p 111-114, 2001.
  7. "Adding for-loops to first-order logic" (F. Neven, M. Otto, J. Tyszkiewicz, J. Van den Bussche). Information and Computation, vol 168, no 2, p 156-186, 2001. (A preliminary version appeared in ICDT'99.)
  8. "The forall-not degree of a connective-free formula" (J. Van den Bussche). Acta Informatica, vol 30, pages 489-502, 1993.
  9. "Converting untyped formulas to typed ones" (J. Van den Bussche, L. Cabibbo). Acta Informatica, vol 35, pages 637-643, 1998.
  10. "Polynomially orderable classes of structures" (J. Van den Bussche, D. Van Gucht).

Nested relations

  1. "Solving equations in the relational algebra" (J. Biskup, J. Paredaens, T. Schwentick, J. Van den Bussche). SIAM Journal on Computing, 33(5):1052-1066, 2004.
  2. "Simulation of the nested relational algebra by the flat relational algebra, with an application to the complexity of evaluating powerset algebra expressions" (J. Van den Bussche). Theoretical Computer Science, 254(1-2):363-377, 2001.
  3. "Complex object multi-level fixpoint queries" (J. Van den Bussche). Annals of Mathematics and Artificial Intelligence, vol 7, pages 41-62, 1993. (A preliminary version was presented at MFDBS'91.)
  4. "Evaluation and optimization of complex object selections" (J. Van den Bussche). Deductive and Object-Oriented Databases (C. Delobel, M. Kifer, Y. Masanuga, editors), Lecture Notes in Computer Science, vol 566, pages 21-38. Springer, 1991.
  5. "A formal basis for extending SQL to object-oriented databases" (J. Van den Bussche). Bulletin of the EATCS, vol 40, pages 207-216, 1990.

Last updated: Fri Jun 6 10:00:20 CEST 2014
Jan Van den Bussche