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). Natural Computing. Combined full version of ANB 2010 and DNA18 papers.
  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, Provenance, Causality

  1. "What's in a neighborhood? Describing nodes in RDF graphs using shapes" (M. Jakubowski, J. Van den Bussche). RuleML+RR 2024.
  2. "Postulates for provenance: Instance-based provenance for first-order logic" (B. Bogaerts, M. Jakubowski, J. Van den Bussche). PODS 2024.
  3. "Data provenance for SHACL" (T. Delva, A. Dimou, M. Jakubowski, J. Van den Bussche). EDBT 2023.
  4. "Inference in the FO(C) modelling language" (B. Bogaerts, J. Vennekens, M. Denecker, J. Van den Bussche). Proceedings ECAI 2014
  5. "Querying an integrated complex-object dataflow database" (N. Kwasnikowska, J. Van den Bussche). Peter Buneman Festschrift
  6. "A formal account of the Open Provenance Model" (N. Kwasnikowska, L.Moreau, J. Van den Bussche). ACM Transactions on the Web. Revised version of University of Southampton ECS Technical Report 21819, December 2010.
  7. "The open provenance model core specification v1.1" (L. Moreau et al.) In Future Generation Computer Systems.
  8. "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.
  9. "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)
  10. "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.
  11. "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.
  12. "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. "Logical aspects of spatial databases" (B. Kuijpers, J. Van den Bussche). In Finite and Algorithmic Model Theory, 2011.
  2. "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.
  3. "First-order topological properties". Bulletin of the EATCS, vol 87, pp 155-164, 2005. (Logic in Computer Science Column)
  4. "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.
  5. "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.
  6. "Constraint databases: A tutorial introduction" (J. Van den Bussche). SIGMOD Record, vol 29, no 3, pp 44-51, 2000 (Database Principles column).
  7. "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.
  8. "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.
  9. "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.
  10. "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.
  11. "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.)
  12. "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.)
  13. "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.)
  14. "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.
  15. "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.)
  16. "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.
  17. "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. "Mapping-equivalence and oid-equivalence of single-function object-creating conjunctive queries" (A. Bonifati, W. Nutt, R. Torlone, J. Van den Bussche). The VLDB Journal, doi: 10.1007/s00778-016-0421-x.
  2. "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.)
  3. "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.)
  4. "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.)
  5. "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.)
  6. "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.)
  7. "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.
  8. "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.
  9. "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.
  10. "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.
  11. "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 graph patterns by timed automata" (A. Aghasadeghi, J. Van den Bussche, J. Stoyanovich). VLDB Journal, 2023.
  2. "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, JSON

  1. "Compiling SHACL into SQL" (M. Jakubowski, J. Van den Bussche). ISWC 2024 research track paper.
  2. "Expressiveness of SHACL features and extensions for full equality and disjointness tests" (B. Bogaerts, M. Jakubowski, J. Van den Bussche). LMCS, 2024, extended version of ICDT 2022 paper
  3. "What can database query processing do for instance-spanning constraints?" (H. Aamer, M. Montali, J. Van den Bussche). Business Process Intelligence Workshop 2023.
  4. "Subsequence versus substring constraints in sequence pattern languages" (S. Engels, T. Tan, J. Van den Bussche). Acta Informatica, 2019.
  5. "A Framework for Comparing Query Languages in Their Ability to Express Boolean Queries" (D. Surinx, J. Van den Bussche, D. Van Gucht). FoIKS 2018. Journal version in Annals of Mathematics and Artificial Intelligence.
  6. "The primitivity of operators in the algebra of binary relations under conjunctions of containments" (D. Surinx, J. Van den Bussche, D. Van Gucht). LICS 2017.
  7. "J-Logic: Towards logical foundations for JSON querying" (J. Hidders, J. Paredaens, J. Van den Bussche). PODS 2017.
  8. "Relative Expressive Power of Downward Fragments of Navigational Query Languages on Trees and Chains", DBPL 2015.
  9. "On the power of SPARQL in expressing navigational queries" (X.Zhang and J. Van den Bussche). The Computer Journal.
  10. On the satisfiability problem for SPARQL patterns" (X. Zhang, J. Van den Bussche, F. Picalausa). Journal of Artificial Intelligence Research
  11. "On the primitivity of operators in SPARQL" (X. Zhang and J. Van den Bussche). In Information Processing Letters.
  12. "Similarifty 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
  13. "Walk Logic as a framework for path query languages on graph databases" (J. Hellings, B. Kuijpers, J. Van den Bussche, X. Zhang). ICDT 2013.
  14. "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.
  15. "Relative expressive power of navigational querying on graphs using transitive closure" (D. Surinx, G.H.L. Fletcher, M. Gyssens, D. Leinders, J. Van den Bussche, D. Van Gucht, S. Vansummeren, Y. Wu). Second journal version of ICDT 2011 conference paper, with all results involving transitive closure. Published in Logic Journal of the IGPL
  16. "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. Journal version (with all results not involving transitive closure) in Information Sciences.
  17. "Towards a theory of search queries" (G.H.L. Fletcher, J. Van den Bussche, D. Van Gucht, S. Vansummeren). In TODS.
  18. "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.
  19. "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.)
  20. "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.
  21. "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.
  22. "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.)
  23. "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.
  24. "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.)
  25. "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.
  26. "Using SQL with object-oriented databases" (J. Van den Bussche, A. Heuer). Information Systems, vol 18, no 7, pages 461-487, 1993.
  27. "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.
  28. "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.
  29. "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. "Naive Infinite Enumeration of Context-free Languages in Incremental Polynomial Time" (C. Costa Florêncio, J. Daenen, J. Ramon, J. Van den Bussche, D. Van Dyck). Journal of Universal Computer Science.
  2. "Discovering XSD keys from XML data" (M. Arenas, J. Daenen, F. Neven, M. Ugarte, J. Van den Bussche, S. Vansummeren). ACM TODS.
  3. "Expressive power of safe first-order logical decision trees" (J. Gillis and J. Van den Bussche). ILP 2011.
  4. "Induction of relational algebra expressions" (J. Gillis and J. Van den Bussche). ILP 2009.
  5. "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.
  6. "Mining for trees in a graph is NP-complete". arXiv:0709.4655.
  7. "Mining tree-query associations in graphs". arXiv:1008.2626. Full version of two earlier conference papers presented at KDD 2005 and ICDM 2006.
  8. "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.
  9. "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.
  10. "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.
  11. "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.
  12. "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.
  13. "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.
  14. "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. "Input-Output Disjointness for Forward Expressions in the Logic of Information Flows" (H. Aamer, J. Van den Bussche). ICDT 2021.
  2. "Inputs, outputs, and composition in the logic of information flows" (H. Aamer, B. Bogaerts, D. Surinx, E. Ternovska, J. Van den Bussche). KR 2020. Full version in TOCL 2023.
  3. "Executable first-order queries in the logic of information flows" (H. Aamer, B. Bogaerts, D. Surinx, E. Ternovska, J. Van den Bussche). LMCS, 2024, extended version of ICDT202 paper
  4. "On the CRON conjecture" (T.J. Ameloot, J. Van den Bussche), Datalog 2.0 Workshop, Vienna, 2012. Full version published in JCSS: "Positive Dedalus programs tolerate non-causality"
  5. "Putting logic-based distributed systems on stable grounds" (P. Alvaro, T.J. Ameloot, J.M. Hellerstein, W. Marczak, J. Van den Bussche). Author version of Theory and Practice of Logic Programming paper. This is the journal version of the UCBerkeley techreport.
  6. "Deciding eventual consistency for a simple class of relational transducer networks" (T. Ameloot, J. Van den Bussche), ICDT 2012. Journal version "Deciding confluence for a simple class of relational transducer networks" in Theory of Computing Systems, 2015.
  7. "Relational transducers for declarative networking" (T. Ameloot, F. Neven, J. Van den Bussche), JACM vol 60 no 2 (journal version of PODS 2011 paper).
  8. "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.
  9. "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.
  10. "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!

  11. "Rewriting queries using views over monadic database schemas" (J. Van den Bussche). Information Processing Letters, vol 79, p 111-114, 2001.

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.

Logic and databases, Finite model theory

  1. "Preservation theorems for Tarski's relation algebra" (B. Bogaerts, B. ten Cate, B. McLean, J. Van den Bussche). LMCS, 2024.
  2. "Descriptive complexity of deterministic polylogarithmic time and space" (F. Ferrarotti, S. González, J.M. Turull Torres, J. Van den Bussche, J. Virtema). Journal of Computer and System Sciences, journal version of WoLLIC 2019 paper.
  3. "Fully generic queries: Open problems and some partial answers" (D. Surinx, J. Van den Bussche, J. Virtema). MEDI 2019.
  4. "Additive first-order queries" (G. Berger, M. Otto, A. Pieris, D. Surinx, J. Van den Bussche). ICDT 2019.
  5. "Descriptive complexity of deterministic polylogarithmic time" (F. Ferrarotti, S. Gonzalez, J.M. Turull Torres, J. Van den Bussche, J. Virtema). WoLLIC 2019.
  6. "A monotone preservation result for Boolean queries expressed as a containment of conjunctive queries" (D. Surinx, J. Van den Bussche, D. Van Gucht). Information Processing Letters, vol 150, pages 1--5, 2019.
  7. "Expressivity within second-order transitive-closure logic" (F. Ferrarotti, J. Van den Bussche, J. Virtema). CSL 2018.
  8. "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.
  9. "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.)
  10. "Polynomially orderable classes of structures" (J. Van den Bussche, D. Van Gucht).

Matrix queries, Neural networks, and miscellaneous topics

  1. "On the expressive power of message-passing neural networks as global feature map transformers" (F. Geerts, J. Steegmans, J. Van den Bussche). Proceedings FoIKS 2022. Also on arXiv:2203.09555
  2. "Positive neural networks in discrete time implement monotone-regular behaviors" (T. Ameloot, J. Van den Bussche). Neural Computation, 27(12), 2015.
  3. "On matrices and K-relations", FoIKS 2020. Journal version, Annals of Mathematics and Artificial Intelligence
  4. "On the expressive power of query languages for matrices" (R. Brijder, F. Geerts, J. Van den Bussche, T. Weerwag). ICDT 2018. Full version in TODS.
  5. "On the expressive power of update primitives" (T.J. Ameloot, J. Van den Bussche, E. Waller). PODS 2013.
  6. "Quantitatively evaluating formula-variable relevance by forgetting" (X. Liang, Z. Lin, J. Van den Bussche). Canadian AI 2013.
  7. "Database Theory, Yuri, and Me". In Fields of Logic and Computation: Essays dedicated to Yuri Gurevich.
  8. "A theory of stream queries" (Y. Gurevich, D. Leinders, J. Van den Bussche). DBPL 2007.
  9. "The forall-not degree of a connective-free formula" (J. Van den Bussche). Acta Informatica, vol 30, pages 489-502, 1993.
  10. "Converting untyped formulas to typed ones" (J. Van den Bussche, L. Cabibbo). Acta Informatica, vol 35, pages 637-643, 1998.

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: Tue Dec 3 23:34:31 CET 2024
Jan Van den Bussche