{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2026,9,20]],"date-time":"2026-09-20T03:34:42Z","timestamp":1789875282604,"version":"4.0.1"},"reference-count":32,"publisher":"Association for Computing Machinery (ACM)","issue":"1","license":[{"start":{"date-parts":[[2007,12,1]],"date-time":"2007-12-01T00:00:00Z","timestamp":1196467200000},"content-version":"vor","delay-in-days":0,"URL":"https:\/\/www.acm.org\/publications\/policies\/copyright_policy#Background"}],"content-domain":{"domain":["dl.acm.org"],"crossmark-restriction":true},"short-container-title":["ACM Trans. Comput. Logic"],"published-print":{"date-parts":[[2007,12]]},"abstract":"<jats:p>The named nested relational calculus is the canonical query language for the complex object database model and is equipped with a natural static type system. Given an expression in the language, without type declarations for the input variables, there is the problem of whether there are any input type declarations under which the expression is well-typed. Moreover, if there are, then which are they, and what is the corresponding output type for each of these? This problem is solved by a logic-based approach, and the decision problem is shown to be NP-complete.<\/jats:p>","DOI":"10.1145\/1297658.1297661","type":"journal-article","created":{"date-parts":[[2007,12,21]],"date-time":"2007-12-21T14:52:36Z","timestamp":1198248756000},"page":"3","update-policy":"https:\/\/doi.org\/10.1145\/crossmark-policy","source":"Crossref","is-referenced-by-count":8,"title":["Polymorphic type inference for the named nested relational calculus"],"prefix":"10.1145","volume":"9","author":[{"given":"Jan Van den","family":"Bussche","sequence":"first","affiliation":[{"name":"Hasselt University and Transnational University of Limburg, Diepenbeck, Belgium"}],"role":[{"vocabulary":"crossref","role":"author"}]},{"given":"Stijn","family":"Vansummeren","sequence":"additional","affiliation":[{"name":"Hasselt University and Transnational University of Limburg, Diepenbeck, Belgium"}],"role":[{"vocabulary":"crossref","role":"author"}]}],"member":"320","published-online":{"date-parts":[[2007,12]]},"reference":[{"key":"e_1_2_1_1_1","unstructured":"Abiteboul S. Hull R. and Vianu V. 1995. Foundations Of Databases. Addison-Wesley.   Abiteboul S. Hull R. and Vianu V. 1995. Foundations Of Databases. Addison-Wesley."},{"key":"e_1_2_1_2_1","doi-asserted-by":"publisher","DOI":"10.1145\/328939.328943"},{"key":"e_1_2_1_3_1","doi-asserted-by":"crossref","unstructured":"Baader F. and Snyder W. 2001. Unification theory. In Handbook of Automated Reasoning. Elsevier and MIT Press 445--532.  Baader F. and Snyder W. 2001. Unification theory. In Handbook of Automated Reasoning. Elsevier and MIT Press 445--532.","DOI":"10.1016\/B978-044450813-3\/50010-2"},{"key":"e_1_2_1_4_1","volume-title":"Proceedings of Object-Oriented Programming (ECOOP'93)","volume":"707","author":"Balsters H.","unstructured":"Balsters , H. , de By , R. A. , and Zicari , R . 1993. Typed sets as a basis for object-oriented database schemas . In Proceedings of Object-Oriented Programming (ECOOP'93) . Lecture Notes in Computer Science , vol. 707 . Springer, 161--184. Balsters, H., de By, R. A., and Zicari, R. 1993. Typed sets as a basis for object-oriented database schemas. In Proceedings of Object-Oriented Programming (ECOOP'93). Lecture Notes in Computer Science, vol. 707. Springer, 161--184."},{"key":"e_1_2_1_5_1","doi-asserted-by":"publisher","DOI":"10.1006\/jcss.1995.1063"},{"key":"e_1_2_1_6_1","volume-title":"Proceedings of the 4th International Conference on Database Theory. Lecture Notes in Computer Science","volume":"646","author":"Breazu-Tannen V.","unstructured":"Breazu-Tannen , V. , Buneman , P. , and Wong , L . 1992. Naturally embedded query languages . In Proceedings of the 4th International Conference on Database Theory. Lecture Notes in Computer Science , vol. 646 . Springer-Verlag, 140--154. Breazu-Tannen, V., Buneman, P., and Wong, L. 1992. Naturally embedded query languages. In Proceedings of the 4th International Conference on Database Theory. Lecture Notes in Computer Science, vol. 646. Springer-Verlag, 140--154."},{"key":"e_1_2_1_7_1","doi-asserted-by":"publisher","DOI":"10.1145\/235968.233368"},{"key":"e_1_2_1_8_1","volume-title":"Proceedings of the 6th International Conference on Database Theory (ICDT'97)","volume":"1186","author":"Buneman P.","unstructured":"Buneman , P. , Davidson , S. B. , Fernandez , M. F. , and Suciu , D . 1997. Adding structure to unstructured data . In Proceedings of the 6th International Conference on Database Theory (ICDT'97) , F. N. Afrati and P. Kolaitis, Eds. Lecture Notes in Computer Science , vol. 1186 . Springer, 336--350. Buneman, P., Davidson, S. B., Fernandez, M. F., and Suciu, D. 1997. Adding structure to unstructured data. In Proceedings of the 6th International Conference on Database Theory (ICDT'97), F. N. Afrati and P. Kolaitis, Eds. Lecture Notes in Computer Science, vol. 1186. Springer, 336--350."},{"key":"e_1_2_1_9_1","doi-asserted-by":"publisher","DOI":"10.1016\/0304-3975(95)00024-Q"},{"key":"e_1_2_1_10_1","doi-asserted-by":"publisher","DOI":"10.1145\/227604.227609"},{"key":"e_1_2_1_11_1","doi-asserted-by":"publisher","DOI":"10.1016\/0743-1066(84)90022-0"},{"key":"e_1_2_1_12_1","volume-title":"A Mathematical Introduction to Logic","author":"Enderton H. B.","unstructured":"Enderton , H. B. 2001. A Mathematical Introduction to Logic . Academic Press . 2 nd Ed. Enderton, H. B. 2001. A Mathematical Introduction to Logic. Academic Press. 2nd Ed.","edition":"2"},{"key":"e_1_2_1_13_1","volume-title":"Proceedings of the International Conference on Database Theory (ICDT'01)","volume":"1973","author":"Fern\u00e1ndez M. F.","unstructured":"Fern\u00e1ndez , M. F. , Sim\u00e9on , J. , and Wadler , P . 2001. A semi-monad for semi-structured data . In Proceedings of the International Conference on Database Theory (ICDT'01) . Lecture Notes in Computer Science , vol. 1973 . Springer, 263--300. Fern\u00e1ndez, M. F., Sim\u00e9on, J., and Wadler, P. 2001. A semi-monad for semi-structured data. In Proceedings of the International Conference on Database Theory (ICDT'01). Lecture Notes in Computer Science, vol. 1973. Springer, 263--300."},{"key":"e_1_2_1_14_1","doi-asserted-by":"publisher","DOI":"10.1023\/A:1008683107812"},{"key":"e_1_2_1_15_1","volume-title":"Haskell 98 Language and Libraries","author":"Jones S. P.","unstructured":"Jones , S. P. 2003. Haskell 98 Language and Libraries . Cambridge University Press . Jones, S. P. 2003. Haskell 98 Language and Libraries. Cambridge University Press."},{"key":"e_1_2_1_16_1","unstructured":"Kanellakis P. C. Mairson H. G. and Mitchell J. C. 1991. Unification and ML-type reconstruction. In Computational Logic---Essays in Honor of Alan Robinson. MIT Press 444--478.  Kanellakis P. C. Mairson H. G. and Mitchell J. C. 1991. Unification and ML-type reconstruction. In Computational Logic---Essays in Honor of Alan Robinson. MIT Press 444--478."},{"key":"e_1_2_1_17_1","doi-asserted-by":"publisher","DOI":"10.1145\/96709.96748"},{"key":"e_1_2_1_18_1","doi-asserted-by":"publisher","DOI":"10.1145\/357162.357169"},{"key":"e_1_2_1_19_1","doi-asserted-by":"publisher","DOI":"10.1007\/3-540-44881-0_31"},{"key":"e_1_2_1_20_1","volume-title":"Understanding SQL's Stored Procedures. Morgan Kaufmann","author":"Melton J.","unstructured":"Melton , J. 1998. Understanding SQL's Stored Procedures. Morgan Kaufmann , San Mateo, CA . Melton, J. 1998. Understanding SQL's Stored Procedures. Morgan Kaufmann, San Mateo, CA."},{"key":"e_1_2_1_21_1","volume-title":"Foundations for Programming Languages","author":"Mitchell J. C.","unstructured":"Mitchell , J. C. 1996. Foundations for Programming Languages . MIT Press . Mitchell, J. C. 1996. Foundations for Programming Languages. MIT Press."},{"key":"e_1_2_1_22_1","doi-asserted-by":"publisher","DOI":"10.1002\/(SICI)1096-9942(199901\/03)5:1%3C35::AID-TAPO4%3E3.0.CO;2-4"},{"key":"e_1_2_1_23_1","doi-asserted-by":"publisher","DOI":"10.1145\/218570.218572"},{"key":"e_1_2_1_24_1","doi-asserted-by":"publisher","DOI":"10.1016\/0022-0000(78)90043-0"},{"key":"e_1_2_1_25_1","volume-title":"Types and Programming Languages","author":"Pierce B. C.","unstructured":"Pierce , B. C. 2002. Types and Programming Languages . MIT Press . Pierce, B. C. 2002. Types and Programming Languages. MIT Press."},{"key":"e_1_2_1_26_1","unstructured":"R\u00e9my D. 1993. Type inference for records in a natural extension of ML. In Theoretical Aspects of Object-Oriented Programming. Types Semantics and Language Design C. A. Gunter and J. C. Mitchell Eds. MIT Press.   R\u00e9my D. 1993. Type inference for records in a natural extension of ML. In Theoretical Aspects of Object-Oriented Programming. Types Semantics and Language Design C. A. Gunter and J. C. Mitchell Eds. MIT Press."},{"key":"e_1_2_1_28_1","series-title":"Lecture Notes in Computer Science","volume-title":"Proceedings of Functional and Logic Programming (FLOPS'01)","author":"Sulzmann M.","unstructured":"Sulzmann , M. 2001. A general type inference framework for Hindley\/Milner style systems . In Proceedings of Functional and Logic Programming (FLOPS'01) . Lecture Notes in Computer Science , vol. 2024 . Springer-Verlag , 248--263. Sulzmann, M. 2001. A general type inference framework for Hindley\/Milner style systems. In Proceedings of Functional and Logic Programming (FLOPS'01). Lecture Notes in Computer Science, vol. 2024. Springer-Verlag, 248--263."},{"key":"e_1_2_1_29_1","volume-title":"ML97 Ed","author":"Ullman J. D.","unstructured":"Ullman , J. D. 1998. Elements of ML Programming , ML97 Ed . Prentice-Hall . Ullman, J. D. 1998. Elements of ML Programming, ML97 Ed. Prentice-Hall."},{"key":"e_1_2_1_30_1","doi-asserted-by":"publisher","DOI":"10.1007\/978-3-540-30570-5_7"},{"key":"e_1_2_1_31_1","doi-asserted-by":"publisher","DOI":"10.1006\/jcss.2001.1812"},{"key":"e_1_2_1_32_1","doi-asserted-by":"publisher","DOI":"10.1007\/s00236-005-0162-6"},{"key":"e_1_2_1_33_1","doi-asserted-by":"publisher","DOI":"10.1016\/0890-5401(91)90050-C"}],"container-title":["ACM Transactions on Computational Logic"],"original-title":[],"language":"en","link":[{"URL":"https:\/\/dl.acm.org\/doi\/10.1145\/1297658.1297661","content-type":"unspecified","content-version":"vor","intended-application":"text-mining"},{"URL":"https:\/\/dl.acm.org\/doi\/pdf\/10.1145\/1297658.1297661","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2025,6,18]],"date-time":"2025-06-18T15:14:03Z","timestamp":1750259643000},"score":1,"resource":{"primary":{"URL":"https:\/\/dl.acm.org\/doi\/10.1145\/1297658.1297661"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2007,12]]},"references-count":32,"journal-issue":{"issue":"1","published-print":{"date-parts":[[2007,12]]}},"alternative-id":["10.1145\/1297658.1297661"],"URL":"https:\/\/doi.org\/10.1145\/1297658.1297661","relation":{},"ISSN":["1529-3785","1557-945X"],"issn-type":[{"value":"1529-3785","type":"print"},{"value":"1557-945X","type":"electronic"}],"subject":[],"published":{"date-parts":[[2007,12]]},"assertion":[{"value":"2007-12-01","order":2,"name":"published","label":"Published","group":{"name":"publication_history","label":"Publication History"}}]}}