{"entities":{"Q1986557":{"pageid":1997299,"ns":120,"title":"Item:Q1986557","lastrevid":72220875,"modified":"2026-04-14T03:25:23Z","type":"item","id":"Q1986557","labels":{"en":{"language":"en","value":"Functional dependency restricted insertion propagation"}},"descriptions":{"en":{"language":"en","value":"scientific article; zbMATH DE number 7188525"}},"aliases":{},"claims":{"P31":[{"mainsnak":{"snaktype":"value","property":"P31","hash":"fd5912e4dab4b881a8eb0eb27e7893fef55176ad","datavalue":{"value":{"entity-type":"item","numeric-id":56887,"id":"Q56887"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q1986557$03B88683-F1EA-4599-8DAB-721030046450","rank":"normal"}],"P159":[{"mainsnak":{"snaktype":"value","property":"P159","hash":"41121b2b24db1b3f93e4dedaad86ee23a8935541","datavalue":{"value":{"text":"Functional dependency restricted insertion propagation","language":"en"},"type":"monolingualtext"},"datatype":"monolingualtext"},"type":"statement","id":"Q1986557$6B864641-AEE0-4AD1-BC3D-D0EC496C9BE6","rank":"normal"}],"P225":[{"mainsnak":{"snaktype":"value","property":"P225","hash":"989e3f9198bdc3c1edbe1a5f131c25cd4482d144","datavalue":{"value":"1440.68058","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q1986557$27DBF3CC-0F8B-4D9F-96C0-DF64E544684D","rank":"normal"}],"P16":[{"mainsnak":{"snaktype":"value","property":"P16","hash":"7ac9594bc41defa56e93f58238b731b0750a100f","datavalue":{"value":{"entity-type":"item","numeric-id":896156,"id":"Q896156"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q1986557$B381001A-A65E-41F4-A543-AA7E4C1A6588","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P16","hash":"97f9829e769ecefb14fbc781083551cb2f2f73be","datavalue":{"value":{"entity-type":"item","numeric-id":247844,"id":"Q247844"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q1986557$F8C7E22B-455A-4206-98BD-39CF43BE7090","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P16","hash":"b60afa25a1e25a8fdd2add7e93878519075a2830","datavalue":{"value":{"entity-type":"item","numeric-id":492586,"id":"Q492586"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q1986557$BA3D627B-08C3-43B2-ABA9-1931A1F91782","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P16","hash":"f75c8e2f1470f68f211700e9ee490c532cd89d41","datavalue":{"value":{"entity-type":"item","numeric-id":946655,"id":"Q946655"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q1986557$513655F0-C592-4D71-836E-68A67FFE6B85","rank":"normal"}],"P200":[{"mainsnak":{"snaktype":"value","property":"P200","hash":"f3c424cd94a60f9664f9fb69cc6027e75cc7ff3f","datavalue":{"value":{"entity-type":"item","numeric-id":123643,"id":"Q123643"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q1986557$C9F5A750-E61F-4F8C-8244-C5B9BD3C3203","rank":"normal"}],"P28":[{"mainsnak":{"snaktype":"value","property":"P28","hash":"26a75e2b82c7d52d04b09f73d9891a6078a1dc17","datavalue":{"value":{"time":"+2020-04-08T00:00:00Z","timezone":0,"before":0,"after":0,"precision":11,"calendarmodel":"http://www.wikidata.org/entity/Q1985727"},"type":"time"},"datatype":"time"},"type":"statement","id":"Q1986557$701E4C26-9B1F-42B0-8EA2-16985B64DE2C","rank":"normal"}],"P1448":[{"mainsnak":{"snaktype":"value","property":"P1448","hash":"8a7d795bf63b09213d16a8f3d3ff63351bc8b6d7","datavalue":{"value":"Views in database systems provide an excerpt of underlying information, and they can be used to restrict the amount of information that specific target users need to know or are allowed to access.  While processing of queries over views is simple, propagating updates expressed over views to the underlying base data is known to be hard (and impossible in a side-effect-free manner for large classes of views).  This paper presents complexity results to decide whether there is a side-effect-free propagation of given insertions into subclasses of monotonic views expressed in the relational algebra over relations with functional dependencies.  The problem is abbreviated with the acronym FD-vsef-IP (Functional Dependency, view side-effect-free, Insertion Propagation) and considered for insertions of single tuples as well as groups of tuples.  In their theorems, the authors establish the following results: FD-vsef-IP is NP-complete for union views under group insertions on data complexity (Theorem 1).  FD-vsef-IP is coNP-complete for select-join queries under group insertions on combined complexity (Theorem 2). FD-vsef-IP is NP-complete for select-project-join queries under group insertions with finite domain on data complexity; it is in PTime for select-project-join queries without self-joins under single insertions on data complexity (Theorem 3).  FD-vsef-IP is \\(\\Sigma_2^{\\mathrm{P}}\\)-complete for select-project-join queries under group insertions with finite domain on combined complexity (Theorem 4).  FD-vsef-IP is \\(\\Sigma_2^{\\mathrm{P}}\\)-complete for select-join-union queries under group insertions with finite domain on combined complexity (Theorem 5).  This paper is restricted to the above complexity results.  Practical aspects (such as (a) what to do if an insertion cannot be propagated in a side-effect-free manner or (b) whether to allow view updates if such cases can arise) are not considered.","type":"string"},"datatype":"string"},"type":"statement","id":"Q1986557$BF993151-F5C0-42D8-8FF7-D60CF999C168","rank":"normal"}],"P226":[{"mainsnak":{"snaktype":"value","property":"P226","hash":"bf2726c5c2109371cc10358eaa69bc4df711caf7","datavalue":{"value":"68P15","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q1986557$C3F9010B-DCE8-4E79-8FA7-1B4F74AD4B06","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P226","hash":"8195a9e26c453276e1d31339bf2413392412013d","datavalue":{"value":"68Q17","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q1986557$C72DE46C-5E03-4DFD-B898-8E43A6413499","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P226","hash":"fdd9498216d1fd2eff80e5a7d18782b649eb7b2f","datavalue":{"value":"68Q25","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q1986557$8BB81999-CF07-4E1E-A4BA-B168683E4757","rank":"normal"}],"P1451":[{"mainsnak":{"snaktype":"value","property":"P1451","hash":"44309dfe99b8c8ab3145129c9522c2d84aabca6f","datavalue":{"value":"7188525","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q1986557$7EB3A115-7566-40DA-AE84-2CA9AD512FEF","rank":"normal"}],"P1450":[{"mainsnak":{"snaktype":"value","property":"P1450","hash":"7ebb45d635b15d0e587c63887c999d05a60ce018","datavalue":{"value":"view update","type":"string"},"datatype":"string"},"type":"statement","id":"Q1986557$F5713882-306F-4C14-8C88-57EB85EEA936","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1450","hash":"c5f8382ba04f9f05f645b4d0e4b9ea28f0619583","datavalue":{"value":"complexity","type":"string"},"datatype":"string"},"type":"statement","id":"Q1986557$C1353F22-1859-4630-82BA-EE0C4AFE0FCD","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1450","hash":"f37a034e647f80843b21640ec1d9b6824b15e6b5","datavalue":{"value":"relational algebra","type":"string"},"datatype":"string"},"type":"statement","id":"Q1986557$BE7CB6B2-1BF8-4E2B-B6D5-4509CC9A7278","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1450","hash":"2741b83bca5f96ce6502d31fbc071d253285a86f","datavalue":{"value":"insertion propagation","type":"string"},"datatype":"string"},"type":"statement","id":"Q1986557$AF9FAE63-0059-4767-9277-A1707DD4DB8A","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1450","hash":"0c1cdec68f6f531065eeae64be8360df19d70183","datavalue":{"value":"functional dependency","type":"string"},"datatype":"string"},"type":"statement","id":"Q1986557$2FD10B2B-A977-4D64-B1D3-110E2F203C85","rank":"normal"}],"P1460":[{"mainsnak":{"snaktype":"value","property":"P1460","hash":"57f7fea50d2ce1b39b695c4a1313582eed405e38","datavalue":{"value":{"entity-type":"item","numeric-id":5976449,"id":"Q5976449"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q1986557$F0C6FD5B-1D4C-44ED-9D27-B2348AF0A691","rank":"normal"}],"P205":[{"mainsnak":{"snaktype":"value","property":"P205","hash":"86f01221adae25ab7db15195d3d71ea989274071","datavalue":{"value":"https://doi.org/10.1016/j.tcs.2017.03.043","type":"string"},"datatype":"url"},"type":"statement","id":"Q1986557$25F2BA82-5731-4022-BDE1-C4D49E5DDE45","rank":"normal"}],"P388":[{"mainsnak":{"snaktype":"value","property":"P388","hash":"a4d08602311aaec3b721959aebbd7cff3643daa8","datavalue":{"value":"W2607189612","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q1986557$72DC119E-3547-44EA-A632-B6EC5410A4E2","rank":"normal"}],"P223":[{"mainsnak":{"snaktype":"value","property":"P223","hash":"5d4ac292ad02cc5c58f61f5094cb1164c9f02d13","datavalue":{"value":{"entity-type":"item","numeric-id":3949998,"id":"Q3949998"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q1986557$C7EC0B13-93B5-4C48-96E6-60F1C9DF1A85","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"948ee72dfb42e2ffc1454ffd9bb23bca2c64af87","datavalue":{"value":{"entity-type":"item","numeric-id":3917520,"id":"Q3917520"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q1986557$4E728A62-1C46-4E9B-8028-EA97385DF3F1","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"bc05e62ec0bdc540a4d524fe5622aae1c8b0b4a4","datavalue":{"value":{"entity-type":"item","numeric-id":3770002,"id":"Q3770002"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q1986557$4DEE3B8A-9C50-4611-A3B6-F93B1883DDA5","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"b3ac0dd53f09cacdf3fcbb4eff2811910d7a10d1","datavalue":{"value":{"entity-type":"item","numeric-id":896157,"id":"Q896157"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q1986557$468FD576-7F64-4885-9F85-7A33D435F2C5","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"ae600d82e59da48d9490ff29ee5b51a547bc0409","datavalue":{"value":{"entity-type":"item","numeric-id":4864249,"id":"Q4864249"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q1986557$6BA620A1-DF35-4A16-B2F5-FEFDFF531EF8","rank":"normal"}],"P27":[{"mainsnak":{"snaktype":"value","property":"P27","hash":"d70f45c13b0f436f9bdd75c9330bad5c6bda1a1e","datavalue":{"value":"10.1016/J.TCS.2017.03.043","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q1986557$BCE10972-946F-49D7-910F-96529AF730FB","rank":"normal"}],"P1643":[{"mainsnak":{"snaktype":"value","property":"P1643","hash":"0401ff2c2a8a8b78ee0d3e1ff9db0ed6b6b23139","datavalue":{"value":{"entity-type":"item","numeric-id":2817905,"id":"Q2817905"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"068db48e338c5e9fef0b187d1a8a235392b7fdb2","datavalue":{"value":{"amount":"+0.8675879","unit":"1"},"type":"quantity"},"datatype":"quantity"}],"P1660":[{"snaktype":"value","property":"P1660","hash":"ac3c626774dcd0d16f89557f66586245841a01db","datavalue":{"value":{"entity-type":"item","numeric-id":6767936,"id":"Q6767936"},"type":"wikibase-entityid"},"datatype":"wikibase-item"}]},"qualifiers-order":["P1659","P1660"],"id":"Q1986557$280E5714-599F-4765-8F96-C8A9E7CFBE49","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1643","hash":"29f036a0019fe7c412e2b0488f643e56c1b385c2","datavalue":{"value":{"entity-type":"item","numeric-id":1071523,"id":"Q1071523"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"88ae90428a166b0017af2b8a0c676e78e626e6fc","datavalue":{"value":{"amount":"+0.8216913","unit":"1"},"type":"quantity"},"datatype":"quantity"}],"P1660":[{"snaktype":"value","property":"P1660","hash":"ac3c626774dcd0d16f89557f66586245841a01db","datavalue":{"value":{"entity-type":"item","numeric-id":6767936,"id":"Q6767936"},"type":"wikibase-entityid"},"datatype":"wikibase-item"}]},"qualifiers-order":["P1659","P1660"],"id":"Q1986557$C9E2BD80-135E-4548-BBFE-1E82F2F44640","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1643","hash":"745ce2d04d186f62d3b067c4c57a94fd13213560","datavalue":{"value":{"entity-type":"item","numeric-id":3813330,"id":"Q3813330"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"b92577f5ccf1c690fbc17f5ca686a182e3f33178","datavalue":{"value":{"amount":"+0.8170491","unit":"1"},"type":"quantity"},"datatype":"quantity"}],"P1660":[{"snaktype":"value","property":"P1660","hash":"ac3c626774dcd0d16f89557f66586245841a01db","datavalue":{"value":{"entity-type":"item","numeric-id":6767936,"id":"Q6767936"},"type":"wikibase-entityid"},"datatype":"wikibase-item"}]},"qualifiers-order":["P1659","P1660"],"id":"Q1986557$317D1168-A57D-4775-9E13-A37ED6106067","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1643","hash":"2e37f4fe22fda072adc5af4ac79a927aa8637048","datavalue":{"value":{"entity-type":"item","numeric-id":5312906,"id":"Q5312906"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"4778d3a6cac3211fbce18c7199a8dcc05c5e4386","datavalue":{"value":{"amount":"+0.8150252","unit":"1"},"type":"quantity"},"datatype":"quantity"}],"P1660":[{"snaktype":"value","property":"P1660","hash":"ac3c626774dcd0d16f89557f66586245841a01db","datavalue":{"value":{"entity-type":"item","numeric-id":6767936,"id":"Q6767936"},"type":"wikibase-entityid"},"datatype":"wikibase-item"}]},"qualifiers-order":["P1659","P1660"],"id":"Q1986557$D2DC8FD4-72BC-4780-9C14-738AA637C02F","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1643","hash":"1e38dba107f20e0fa4d5186fe34973cab3d8bd7f","datavalue":{"value":{"entity-type":"item","numeric-id":4552835,"id":"Q4552835"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"b84e046288bbe47d018dfee487974cca4f62b509","datavalue":{"value":{"amount":"+0.81281424","unit":"1"},"type":"quantity"},"datatype":"quantity"}],"P1660":[{"snaktype":"value","property":"P1660","hash":"ac3c626774dcd0d16f89557f66586245841a01db","datavalue":{"value":{"entity-type":"item","numeric-id":6767936,"id":"Q6767936"},"type":"wikibase-entityid"},"datatype":"wikibase-item"}]},"qualifiers-order":["P1659","P1660"],"id":"Q1986557$B81F03DC-2CFD-4A37-91F5-E4C291A9540D","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1643","hash":"275a0b8532f991a89c5fd193d2569ddcebffefd6","datavalue":{"value":{"entity-type":"item","numeric-id":2206774,"id":"Q2206774"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"46f04230c467dd5f98d26068f5cee81616b864c1","datavalue":{"value":{"amount":"+0.81242096","unit":"1"},"type":"quantity"},"datatype":"quantity"}],"P1660":[{"snaktype":"value","property":"P1660","hash":"ac3c626774dcd0d16f89557f66586245841a01db","datavalue":{"value":{"entity-type":"item","numeric-id":6767936,"id":"Q6767936"},"type":"wikibase-entityid"},"datatype":"wikibase-item"}]},"qualifiers-order":["P1659","P1660"],"id":"Q1986557$C179631F-C400-4583-9EEE-A2AE6F51A604","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1643","hash":"c976ccaa020571232e2329ba89693929ba2cc0d1","datavalue":{"value":{"entity-type":"item","numeric-id":5902427,"id":"Q5902427"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"aa2a4a6075974ebfcda8c51204c09317c2bcd1b2","datavalue":{"value":{"amount":"+0.81071043","unit":"1"},"type":"quantity"},"datatype":"quantity"}],"P1660":[{"snaktype":"value","property":"P1660","hash":"ac3c626774dcd0d16f89557f66586245841a01db","datavalue":{"value":{"entity-type":"item","numeric-id":6767936,"id":"Q6767936"},"type":"wikibase-entityid"},"datatype":"wikibase-item"}]},"qualifiers-order":["P1659","P1660"],"id":"Q1986557$741ECC23-5969-4319-8FF3-52DA17465428","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1643","hash":"58433fabbe74e6822bfa41932a5b2de8aa3291eb","datavalue":{"value":{"entity-type":"item","numeric-id":3792281,"id":"Q3792281"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"cf6c4be6eaad255008d9d1f9dd0649d9dd7f3e86","datavalue":{"value":{"amount":"+0.8075192","unit":"1"},"type":"quantity"},"datatype":"quantity"}],"P1660":[{"snaktype":"value","property":"P1660","hash":"ac3c626774dcd0d16f89557f66586245841a01db","datavalue":{"value":{"entity-type":"item","numeric-id":6767936,"id":"Q6767936"},"type":"wikibase-entityid"},"datatype":"wikibase-item"}]},"qualifiers-order":["P1659","P1660"],"id":"Q1986557$713CAC30-ABC8-4F26-BE87-DC7C81D5890C","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1643","hash":"dc16849a32e2c549dfc554c160e4297ce95f310b","datavalue":{"value":{"entity-type":"item","numeric-id":803779,"id":"Q803779"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"f84efa7c7b896971a88615f72dca0f2016223f89","datavalue":{"value":{"amount":"+0.80711746","unit":"1"},"type":"quantity"},"datatype":"quantity"}],"P1660":[{"snaktype":"value","property":"P1660","hash":"ac3c626774dcd0d16f89557f66586245841a01db","datavalue":{"value":{"entity-type":"item","numeric-id":6767936,"id":"Q6767936"},"type":"wikibase-entityid"},"datatype":"wikibase-item"}]},"qualifiers-order":["P1659","P1660"],"id":"Q1986557$0C57BF6F-1113-4302-BFE0-C83202997A6D","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1643","hash":"b83673e1fc707d92b4ccf8f864b8fdf6804bc4f4","datavalue":{"value":{"entity-type":"item","numeric-id":3419813,"id":"Q3419813"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"94ffc6d79e00cb100a56833185c6be078811c1c9","datavalue":{"value":{"amount":"+0.80711246","unit":"1"},"type":"quantity"},"datatype":"quantity"}],"P1660":[{"snaktype":"value","property":"P1660","hash":"ac3c626774dcd0d16f89557f66586245841a01db","datavalue":{"value":{"entity-type":"item","numeric-id":6767936,"id":"Q6767936"},"type":"wikibase-entityid"},"datatype":"wikibase-item"}]},"qualifiers-order":["P1659","P1660"],"id":"Q1986557$09A68C40-CD6D-48D4-A7F7-DBCF8D21AB4A","rank":"normal"}]},"sitelinks":{"mardi":{"site":"mardi","title":"Functional dependency restricted insertion propagation","badges":[],"url":"https://portal.mardi4nfdi.de/wiki/Functional_dependency_restricted_insertion_propagation"}}}}}