Publications by Dirk Van Gucht

Graph Databases - Calculus of Binary Relations

1. "Similarity and bisimilarity" (G.H.L. Fletcher, M. Gyssens, D. Leinders, J. Van den Bussche, D. Van Gucht, S. Vansummeren). Journal of Logic and Computation Advance Access April 2014
2. "The impact of transitive closure on the expressiveness of navigational query languages on unlabeled graphs" (M. Gyssens, G.H.L. Fletcher, D. Van Gucht, J. Van den Bussche, S. Vansummeren, Y. Wu). Annals of Mathematics and Artificial Intelligence April 2013.
3. "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). Proceedings of the 14th International Conference on Database Theory, pp. 197-207, March 2011
4. "A Study of a Positive Fragment of Path Queries: Expressiveness, Normal Form, and Minimization" (Y. Wu, D. Van Gucht, M. Gyssens, J. Paredaens). The Computer Journal, Volume 54, 7: 1091-1118, 2011

Tree Databases - XPath

1. "Structural Recursion as a Query Language on Lists and Ordered Trees" (E. L. Robertson, L. Saxton, D. Van Gucht, and S. Vansummeren) Theory of Computing Systems: 44(4), 590-619 (2009)
2. "A Methodology for Coupling Fragments of XPath with Structural Indexes for XML Documents" (G. H. L. Fletcher, D. Van Gucht, M. Gyssens, S. Brenes, Y. Wu and J. Paredaens Journal of Information Systems, 34(7): 657-670, 2009
3. "Structural characterizations of the semantics of XPath as navigation tool on a document" (M. Gyssens, J. Paredaens, D. Van Gucht, G.H.L Fletcher). Proceedings of the twenty-fifth ACM SIGMOD-SIGACT-SIGART symposium on Principles of database systems, 2006.
4. "A grammar-based approach towards unifying hierarchical data models" (M. Gyssens, J. Paredaens, D. Van Gucht). SIAM Journal on Computing, 23, 6, pages 1093--1137, 1994. (An abstract of this paper appeared in SIGMOD 89.)
5. "A query language for list-based complex objects " (Latha S. Colby, Edward L. Robertson, Lawrence V. Saxton, Dirk Van Gucht). Proceedings of the thirteenth ACM SIGACT-SIGMOD-SIGART symposium on Principles of database systems Publisher: ACM Press, 1994. (Long version "A query language for list-based complex objects" )
6. "Concepts for Modeling and Querying List-Structured Data" (L. Colby, L.V. Saxton, D. Van Gucht). Information Processing and Management, 30, 5, pages 687--709, 1994.

Machine Learning- Reasoning about Conditional Independence

1. "On the Conditional Independence Implication Problem: a Lattice-theoretic Approach" (M. Niepert, M. Gyssens, B. Sayrafi, D. Van Gucht, G.H.L Fletcher). Artificial Intelligence , 202, pages 29-51, 2013.
2. "Logical and Algorithmic Properties of Stable Conditional Independence" (M. Niepert, D. Van Gucht, M. Gyssens). International Journal on Approximate Reasoning (IJAR) 51(5):531-543, 2010

Data mining - Inference Systems for Reasoning About Uncertainty

1. "Differential constraints " (Bassem Sayrafi, Dirk Van Gucht). Proceedings of the twenty-fourth ACM SIGMOD-SIGACT-SIGART symposium on Principles of database systems Publisher: ACM Press, 2005.
2. "An Inequality for Mixed $L^p$-Norms" (H. Bercovici, D. Van Gucht, D). Mathematical Inequalities & Applications , Vol. 8, No. 4 (2005), pages 743--748.
3. "Measures in Databases and Data Mining" (Sayrafi, B., Van Gucht, D., and Gyssens, M.) Indiana University TR 602 (Nov. 2004).
4. "Inference Systems Derived from Additive Measures" (B. Sayrafi, D. Van Gucht D). Proceedings of the Workshop on Causality and Causal Discovery, in conjunction with the Seventeenth Canadian Conference on Artificial Intelligence (AI'2004), Ontario, Canada, 2004, pp. 16-29.

Data mining - Frequent Itemset Mining

1. "Peak-Jumping Frequent Itemset Mining Algorithms" (N. Dexters, P.W. Purdom, D. Van Gucht). Proceedings PKDD Int. Conf. Principles of Data Mining and Knowledge Discovery.
2. "Data mining (DM): A probability analysis for candidate-based frequent itemset algorithms " (Nele Dexters, Paul W. Purdom, Dirk Van Gucht). Proceedings of the 2006 ACM symposium on Applied computing SAC '06 Publisher: ACM Press, 2006.
3. "On the effectiveness and efficiency of computing bounds on the support of item-sets in the frequent item-sets mining problem " (Bassem Sayrafi, Dirk Van Gucht, Paul W. Purdom). Proceedings of the 1st international workshop on open source data mining: frequent pattern mining implementations OSDM '05 Publisher: ACM Press, 2005.
4. "Average-Case Analysis of the Apriori Algorithm" (Draft version.) (P.W. Purdom, D. Van Gucht, D. Groth). SIAM Journal of Computing, Vol.~33, No.~5, pages 1223--1260, 2004.

BP - Completeness, Instance Completeness

1. "Towards a theory of search queries" (G. H. L. Fletcher, J. Van den Bussche, D. Van Gucht, S.Vansummeren) Proceedings of International Conference on Database Theory, pp. 201-211, March 2009
2. "BP-Completeness" D. Van Gucht

Reflective or meta query languages

1. "A Calculus for Data Mapping" (G. Fletcher, C. Wyss, E. Robertson, D. Van Gucht, D) Int. Workshop on Database Interoperability (InterDB), at the 7th Int. Conf. on Coordination Models and Languages}, Namur, Belgium, 23 April 2005. Elsevier ENTCS.
2. "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.)
3. "Reflective programming in the relational algebra" (Jan Van den Bussche, Dirk Van Gucht, Gottfried Vossen). Proceedings of the twelfth ACM SIGACT-SIGMOD-SIGART symposium on Principles of database systems Publisher: ACM Press, 1993
4. "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.)
5. "Typed query languages for databases containing queries" (Frank Neven, Dirk Van Gucht, Jan Van den Bussche, Gottfried Vossen). Proceedings of the seventeenth ACM SIGACT-SIGMOD-SIGART symposium on Principles of database systems Publisher: ACM Press, 1998.
6. "A Uniform Data Model for Relational Data and Meta-Data Query Processing" (M. Jain, A. Mendhekar, D.~Van Gucht) Proc. of the 7th Conference on Management of Data\/} (COMAD 95), pages 146--165.
7. "Design and Implementation of Reflective SQL" (M.M. Dalkilic, M. Jain, D. Van Gucht, A. Mendhekar). Technical Report 451, Indiana University Computer Science Department, Indiana, February 1996.
8. "Query Processing: A relational algebra for data/metadata integration in a federated database system" (C.M. Wyss, D. Van Gucht). Proceedings of the tenth international conference on Information and knowledge management, 2001.
9. "MD-SQL: A Language for Meta-Data Queries over Relational Databases" Indiana University, TR 528, 1999. (C.M. Rood, D. Van Gucht, F. I. Wyss). (Appeared as "Augmenting SQL with Dynamic Typing to Support Interoperability in a Relational Federation" Proceedings of the 4th Workshop on Engineering Federated Information Systems, pages 5--18, October 2001.)

Spatial databases, constraint query languages

1. "An expressive language for linear spatial database queries" (L. Van deurzen, M. Gyssens, D. Van Gucht). Proceedings of the seventeenth ACM SIGACT-SIGMOD-SIGART symposium on Principles of database systems (Full version in Journal of Computer and Systems Sciences, Vol.~64, Issue 4, pages 579--627, 2004.)
2. "Adding a Path Connectness Operator to FO+Poly (Linear)" Draft version. (C. Giannella, D. Van Gucht). Acta Informatica , 38, pages 621--648, 2002.
3. "On the Expressiveness of Linear-Constraint Query Languages for Spatial Databases" (L. Vandeurzen, M. Gyssens, and D. Van Gucht). Theoretical Computer Science, 254(1-2), pages 423-463 (2001).
4. "Linear-Constraint Databases" (M. Gyssens, L. Vandeurzen, D. Van Gucht). Chapter 9 in Constraint Databases, G. Kuper, L. Libkin and J. Paredaens (editors), Springer-Verlag, pages 199--304, 2000.
5. "Genericity in Spatial Databases". (B. Kuijpers, D. Van Gucht). Chapter 12 in Constraint Databases, G. Kuper, L. Libkin and J. Paredaens (editors), Springer Verlag, pages 293--304, 2000.
6. "On the decidability of semi-linearity for semi-algebraic sets and its implications for spatial databases (extended abstract)" (F. Dumortier, M. Gyssens, L. Vandeurzen, D. Van Gucht). Proceedings of the sixteenth ACM SIGACT-SIGMOD-SIGART symposium on Principles of database systems Publisher: ACM Press. (Full version Journal of Computer and System Sciences, 58, 3, pages 535--571, 1999. CORRIGENDUM. Journal of Computer and System Sciences, 59, 3, pages 557--562, 1999.
7. "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.)
8. "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.)
9. "Complete geometrical query languages (extended abstract)" (Marc Gyssens, Jan Van den Bussche, Dirk Van Gucht). Proceedings of the sixteenth ACM SIGACT-SIGMOD-SIGART symposium on Principles of database systems Publisher: ACM Press, 1997.
10. "On Query Languages For Linear Queries Definable with Polynomial Constraints" (L. Vandeurzen, M. Gyssens, D. Van Gucht) Proc. of the 2nd International Principles and Practice Constraint Programming} (CP 96), pages 468--481, 1996.
11. " On the Desirability and Limitations of Linear Spatial Database Models" (L. Vandeurzen, M. Gyssens, D. Van Gucht) Proc. of the 4th International Symposium on Large Spatial Databases (SSD 95), pages 14--28, 1995.
12. "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 Object-Creating Query Languages (Extended Abstract)" (J. Van den Bussche, D. Van Gucht, M. Andries, M. Gyssens). Proc. of the 33rd Annual IEEE Conference on Foundations of Computer Science (FOCS 92), pages 372--379, 1992.
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 Proceedings of the eleventh ACM SIGACT-SIGMOD-SIGART symposium on Principles of database systems Publisher: ACM Pressversion was presented at ICDT'92.)
4. "Semi-determinism" (Jan Van den Bussche, Dirk Van Gucht). Proceedings of the eleventh ACM SIGACT-SIGMOD-SIGART symposium on Principles of database systems Publisher: ACM Press, 1992.
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.

Object-oriented/graph-oriented query languages

1. "A graph-oriented object database model" (M. Gyssens, J. Paredaens, J. Van den Bussche, D. Van Gucht). Proceedings of the ninth ACM SIGACT-SIGMOD-SIGART symposium on Principles of database systems Publisher: ACM Press
2. "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. ().
3. "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.)
4. "An overview of GOOD " (J. Paredaens, J. Van den Bussche, M. Andries, M. Gemis, M. Gyssens, D. Van Gucht, V. Sarathy, L. Saxton). ACM SIGMOD Record, Volume 21 Issue 1, 1992.
5. "Algebraic Foundation and Optimization for Object Based Query Languages" (V.M. Sarathy, L.V. Saxton, D. Van Gucht) Proc. of the 9th International Conference on Data Engineering (ICDE), pages 81--90, 1993.
6. "Tagging as an Alternative to Object Creation" (M. Gyssens, L.V. Saxton, D. Van Gucht) Query Processing for Advanced Database Systems, J.C. Freytag, D. Maier, and G. Vossen (editors), Morgan Kaufmann, pages 201--237, 1994.

Nested Relational Databases - Query Languages

1. "Well-definedness and semantic type-checking for the nested relational calculus" (J. Van den Bussche, D. Van Gucht, S. Vansummeren). Theoretical Computer Science 371(3): 183-199 (2007).
2. ``Well-definedness and semantic type-checking in the nested relational calculus and XQuery.'' (Van den Bussche, J., Van Gucht, D., and Vansummeren, S.). Proc. of the 2005 International Conference on Database Theory (ICDT '05), Edinburgh, Scotland, pages 99--113, 2005.
3. "Equivalence and Normal Forms for the Restricted and Bounded Fixpoint in the Nested Algebra" (M. Gyssens, D. Suciu, D.~Van Gucht). Information and Computation, 164, 1, pages 85--117, 2001
4. "The Restricted and the Bounded Fixpoint Closures of the Nested Relational Algebra are Equivalent" (M. Gyssens, D. Suciu, D. Van Gucht). Proc. of the 5th Workshop on Database Programming Languages (DBPL 95), 5, pages 1--13, 1995.
5. "Converting nested algebra expressions into flat algebra expressions" (J. Paredaens, D. Van Gucht). ACM Transactions on Database Systems (TODS), Volume 17 Issue 1, 1992.
6. "The Powerset Algebra as a Natural Tool to Handle Nested Database Relations" (M. Gyssens, D. Van Gucht). Journal of Computer and System Sciences, 45, 1, pages 76--103, 1992. (An abstract of this paper appeared in SIGMOD 88.)
7. "A Comparison Between Algebraic Query Languages for Flat and Nested Databases" (M. Gyssens, D. Van Gucht). Theoretical Computer Science, 87, 2, pages 263--286, 1991.
8. "A uniform approach toward handling atomic and structured information in the nested relational database model " (M. Gyssens, J. Paredaens, D. Van Gucht). Journal of the ACM (JACM), Volume 36 Issue 4 , 1989.
9. "An Introduction to the Completeness of Languages for Complex Objects and Nested Relations" (S. Abiteboul, C. Beeri, M. Gyssens, D. Van Gucht). Nested Relations and Complex Objects, pages 117--138, 1989.
10. " Possibilities and limitations of using flat operators in nested algebra expressions " (J. Paredaens, D. Van Gucht). Proceedings of the seventh ACM SIGACT-SIGMOD-SIGART symposium on Principles of database systems Publisher: ACM Press, 1988.
11. "The powerset algebra as a result of adding programming constructs to the nested relational algebra" (M. Gyssens, D. Van Gucht). ACM SIGMOD Record , Proceedings of the 1988 ACM SIGMOD international conference on Management of data SIGMOD '88, Volume 17 Issue 3, 1988.
12. "The Expressiveness of Query Languages for Nested Relations" (M. Gyssens, D. Van Gucht). IEEE Data Engineering, 11, 3, pages 48--55, 1988.
13. "On the expressive power of the extended relational algebra for the unnormalized relational model " (D. Van Gucht). Proceedings of the sixth ACM SIGACT-SIGMOD-SIGART symposium on Principles of database systems Publisher: ACM Press, 1987.
14. "High Level Data Manipulation Languages for Unnormalized Relational Database Models" (D. Van Gucht, P.C. Fischer). Proc. of the XP 7.52 Workshop on Database Theory, Austin, TX, 1986.

Nested Relational Databases - Implementation Aspects

1. "A Storage Structure for Unnormalized Relational Databases" (A. Deshpande, D. Van Gucht). Proc. of the GI Conference on Database Systems for Office Automation, Engineering, and Scientific Applications (BTW 1987), pages 481--486, 1987.
2. "A Storage Structure for Nested Relational Databases" (A. Deshpande, D. Van Gucht). Nested Relations and Complex Objects, pages 69--84, 1989.
3. "An Implementation for Nested Relational Databases" (A. Deshpande, D. Van Gucht). Proc. of the Fourteenth International Conference on Very Large Data Bases (VLDB 88), pages 76--87, 1988.

Nested relations - Structural Aspects -Constraints

1. "On a Hierarchy of Classes for Nested Databases" (M. Gyssens, J. Paredaens, D. Van Gucht). Information Processing Letters, 36, 5, 259--266, 1990.
2. "Multilevel Nested Relational Structures" (D. Van Gucht, P.C. Fischer) Journal of Computer and System Sciences , 36, 1 pages 77--105, 1988. (An abstract of this paper appeared in PODS 86.)
3. "Weak multivalued dependencies " (Patrick C. Fischer, Dirk Van Gucht). Proceedings of the 3rd ACM SIGACT-SIGMOD symposium on Principles of database systems Publisher: ACM Press, 1987.
4. "Some Classes of Multilevel Relational Structures" (D. Van Gucht, P.C. Fischer). Proc. of the 5th SIGACT-SIGMOD Symposium on Principles of Database Systems (PODS 86), pages 60--69, 1986.
5. "Interactions between Dependencies and Nested Relational Structures" (P.C. Fischer, L.V. Saxton, S.J. Thomas, D. Van Gucht). Journal of Computer and Systems Sciences 31, 3, pages 343--353, 1985.
6. "Determining When a Structure Is a Nested Relation" (P.C. Fischer, D. Van Gucht). Proc. of the 11th International Conference on Very Large Data Bases (VLDB 1985), pages 171--180, 1985.
7. "Structure of Relations Satisfying Certain Families of Dependencies" (P.C. Fischer, D. Van Gucht). Proc. of the 2nd Symposium on Theoretical Aspects of Computer Science (STACS 85), pages 131--142, 1985.

Generalized quantifiers

1. "Providing better support for a class of decision support queries" (Sudhir G. Rao, Antonio Badia, Dirk van Gucht). ACM SIGMOD Record , Proceedings of the 1996 ACM SIGMOD international conference on Management of data SIGMOD '96, Volume 25 Issue 2, 1996.
2. "Query Languages with Generalized Quantifiers" (A. Badia, M. Gyssens, D. Van Gucht) Applications of Logic Databases , R. Ramakrishnan, Ed. Kluwer, 1995.
3. "Extended Query Graphs for Declarative Specifications of Set Oriented Queries" (V.M. Sarathy, D. Van Gucht, A. Badia) Proc. of the Workshop on Combining Declarative and Object Oriented Databases, pages 61--71, 1993.
4. "An Object Based Algebra for Parallel Query Processing and Optimization" (Vijay M. Sarathy, Lawrence V. Saxton, and Dirk Van Gucht). Indiana University TR368, 1992.
5. "Implementation of a Graph Oriented Query Language: IUGQL" (V.M. Sarathy, D. Van Gucht) Technical Report 376, Indiana University Computer Science Department, Indiana, March 1993.
6. "A Hierarchy of Faithful Set Creation in Pure OODB's" (J. Van den Bussche, D. Van Gucht). Proc. the 4th International Conference on Database Theory (ICDT 92) pages 326--340, 1992.

Genetic algorithms and other Optimization Techniques

1. "Genetic Algorithms for the Traveling Salesman Problem" (J.J. Grefenstette, R. Gopal, B.J. Rosmaita, D. Van Gucht). Proceedings of the 1st International Conference on Genetic Algorithms, 1985.
2. "The effects of population size, heuristic crossover and local improvement on a genetic algorithm for the traveling salesman problem" (P. Jog, J.Y. Suh, D. Van Gucht). Proceedings of the Third International Conference on Genetic algorithms, 1989.
3. "Distributed Genetic Algorithms" (J.Y. Suh and D. Van Gucht). Indiana University Technical Report No. 225, 1987.
4. "Image registration by genetic search" (J.M. Fitzpatrick, J.J. Grefenstette, D. Van Gucht). Proceedings of IEEE Southeast Conference, 1984.
5. "Parallel Genetic Algorithms Applied to the Traveling Salesman Problem" (P. Jog, J.Y. Suh, D. Van Gucht) SIAM Journal on Optimization Vol. 1, No. 4, pages 515--529, 1991. Also published as IU Tech Report TR314.
6. "Incorporating Heuristic Information into Genetic Search" (J.Y Suh, D. Van Gucht). Proc. of the 2nd Conference on Genetic Algorithms, pages 100--107, 1988.
7. "Parallelisation of Probabilistic Sequential Search Algorithms" (P. Jog, D. Van Gucht). Proc. of the 2nd International Conference on Genetic Algorithms, pages 170--176, 1988.

Miscellaneous topics

1. "An Approach towards the Study of Symmetric Queries" (M. Gyssens, J. Paredaens, D. Van Gucht, Y. Wu) Proceedings of the VLDB (Very Large Data Bases) Endowment 7(1): 25-36, 2013
2. "BP-Completeness" D.Van Gucht Encyclopedia of Database Systems, 265-266, 2009
3. "Completeness Relational Query Languages" (V. Vianu and D. Van Gucht) Encyclopedia of Database Systems, 2009
4. "CE: The Classifier-Estimator Framework for Data Mining" (M.M. Dalkilic, E. Robertson, D. Van Gucht). Proc. of the 7th IFIP 2.6 Working Conference on Database Semantics, Chapman/Hall, 1998.
5. "Leveled Entity-Relationship Diagrams" (M. Gandhi, E. Robertson, Van Gucht). Proc. of the 1994 Entity-Relationship Model Conference (ER 94), pages 420--436, 1994.
6. "Polynomially orderable classes of structures" (J. Van den Bussche, D. Van Gucht). 1992.
7. "The structure of the relational database model" J Paredaens, P De Bra, M Gyssens, D Van Gucht - 1989 - Springer-Verlag New York, Inc. New York, NY, USA.
8. "An Alternative Way to Represent the Cogroup of a Relation in the Context of Nested Databases" (S. Abiteboul, M. Gyssens, D. Van Gucht). Information Processing Letters, 32, 6, pages 317--324, 1989.
9. (J. Paredaens, D. Van Gucht). "An Application of the Theory of Graphs and Hypergraphs to the Decomposition of Relational Database Schemes" Proc. of the 8th Colloquium on Trees in Algebra and Programming, (CAAP 1983), pages 350--366, 1983.
10. "Interaction-Free Multivalued Dependencies" (D. Van Gucht). Theoretical Computer Science, 62, 1-2, pages 221--233, 1988. (An abstract of this paper appeared in ICDT 86.)