5
\$\begingroup\$

This is my first SQL post over here, and in fact, I have more or less the experience of a regular SQL programmer, except that the task at hand this time was way harder than normal.

I am expecting, hoping and almost demanding a better version of my code, because my version is really bad, but I do not know how to make it better.

My biggest gripe is that SQL does not know of the concept of Set, Array or List in traditional sense. I'm using MariaDB 5.5, which is a superset of MySQL 5.5, as far as I know I have not used any MariaDB-specific features.

The task at hand, also visible at http://sqlfiddle.com/#!2/4b411f/10:

With data:

Format: (TemplateId, OrganizationId)
(1, 1001)
(2, 1002)
(2, 1003)
(2, 1004)
(2, 1005)

Select all templates that have X as a subset of their related organizations

Example:
X = (1003, 1005) (Set notation)
Should return (2) (Set notation)
Because (1003, 1005) subset-of (1002, 1003, 1004, 1005) (Set notation again)

Example 2:
X = (1003, 1005, 999)
Should return nothing
Because (1003, 1005, 999) is-not-subset-of (1002, 1003, 1004, 1005)
Example 2

Schemas:

CREATE TABLE `templates` (
    `templateId` INT(11) NOT NULL AUTO_INCREMENT,
    PRIMARY KEY (`templateId`)
)
COLLATE='utf8_general_ci'
ENGINE=InnoDB
AUTO_INCREMENT=0;

CREATE TABLE `template_organizations` (
    `templateId` INT(11) NOT NULL,
    `organizationId` INT(11) NOT NULL,
    INDEX `templateId` (`templateId`),
    INDEX `organizationId` (`organizationId`),
    CONSTRAINT `FK_template_organizations_templates` FOREIGN KEY (`templateId`) REFERENCES `templates` (`templateId`)
)
COLLATE='utf8_general_ci'
ENGINE=InnoDB;

INSERT INTO templates () VALUES(), ();

INSERT INTO template_organizations (templateId, organizationId)
VALUES(1, 1001), (2, 1002), (2, 1003), (2, 1004), (2, 1005);

I decided to implement it using an is-subset-of approach, leading to the following stored procedures and functions as solution (I know about the 'missing' delimiter calls, but I think HeidiSQL silently inserts them):

select_templates_with_organization_ids: The main stored procedure in question

CREATE DEFINER=`root`@`localhost` PROCEDURE `select_templates_with_organization_ids`(IN `organization_ids` VARCHAR(255))
    LANGUAGE SQL
    NOT DETERMINISTIC
    CONTAINS SQL
    SQL SECURITY DEFINER
    COMMENT ''
BEGIN

SELECT t.templateId FROM templates t
WHERE is_subset_of(organization_ids, (
  SELECT GROUP_CONCAT(t_o.organizationId SEPARATOR ',')
    FROM template_organizations t_o
  WHERE t_o.templateId = t.templateId
));

END

is_subset_of: Returns whether the first set is a subset of the second set

CREATE DEFINER=`root`@`localhost` FUNCTION `is_subset_of`(`inner_str` VARCHAR(255), `outer_str` VARCHAR(255))
    RETURNS tinyint(4)
    LANGUAGE SQL
    NOT DETERMINISTIC
    MODIFIES SQL DATA
    SQL SECURITY INVOKER
    COMMENT ''
BEGIN

DECLARE i INT;
DECLARE maximum INT;
DECLARE result TINYINT;

DROP TEMPORARY TABLE inner_set;
DROP TEMPORARY TABLE outer_set;

CREATE TEMPORARY TABLE inner_set
(value INT(11) NOT NULL, INDEX(value));
CREATE TEMPORARY TABLE outer_set
(value INT(11) NOT NULL, INDEX(value));

SET i = 1;
SET maximum = substr_count(inner_str, ',') + 1;

WHILE i <= maximum DO
  INSERT INTO inner_set (value) VALUES(TRIM(SUBSTRING_INDEX(SUBSTRING_INDEX(inner_str, ',', i), ',', -1)));
  SET i = i + 1;
END WHILE;

SET i = 1;
SET maximum = substr_count(outer_str, ',') + 1;

WHILE i <= maximum DO
  INSERT INTO outer_set (value) VALUES(TRIM(SUBSTRING_INDEX(SUBSTRING_INDEX(outer_str, ',', i), ',', -1)));
  SET i = i + 1;
END WHILE;

SELECT 
  CASE 
    WHEN COUNT(*) > 0 THEN 0
    ELSE 1
  END AS is_subset_of
INTO result
FROM inner_set
LEFT JOIN outer_set ON inner_set.value = outer_set.value
WHERE outer_set.value  IS NULL;
RETURN result;

END

substr_count: Returns the amount of times a string occurs in another string.

CREATE DEFINER=`root`@`localhost` FUNCTION `substr_count`(`str` VARCHAR(255), `delim` VARCHAR(255))
    RETURNS int(11)
    LANGUAGE SQL
    DETERMINISTIC
    NO SQL
    SQL SECURITY INVOKER
    COMMENT ''
BEGIN

RETURN ROUND(
  (
      CHAR_LENGTH(str) - CHAR_LENGTH(REPLACE(str, delim, ""))
  ) / CHAR_LENGTH(delim)
);

END

I am very sure that Mr. Maintainer will enjoy my code thoroughly.

\$\endgroup\$
  • \$\begingroup\$ What do you expect select_templates_with_organization_ids('1001,1002') to return? \$\endgroup\$ – 200_success Jul 29 '14 at 15:06
  • \$\begingroup\$ @200_success No matches. As {1001, 1002} is not a subset of {1001} and neither of {1002, 1003, 1004, 1005}. \$\endgroup\$ – skiwi Jul 29 '14 at 15:08
  • 2
    \$\begingroup\$ I thought I would take some time to figure this one out. An hour later, and I figure you should not be using MySQL/MariaDB \$\endgroup\$ – rolfl Aug 1 '14 at 3:53
1
\$\begingroup\$

Easy with a number table.

CREATE TABLE `Num` (`N` INT(11) PRIMARY KEY AUTO_INCREMENT);
INSERT INTO `Num` () VALUES
    ()
  , ()
  , ()
  , ()
  , ()
  , ()
  , ()
  , ()
  , ()
  , ()
  , ()
  , ()
  , ();

So, take the input string (declared in the SQLFiddle example as @X) and join it to the number table on the difference between its length and its length with the expected delimiter removed, then return your result set using a couple of substring_index calls. This gives you tidy rows to work with from the one parameter. Once you have that, using left join on the expected Ids will produce non-NULL values for template_organization rows, while non-matching values will produce NULL. Counting any column from the joined table will give you the number of matched rows, while counting the parsed, returned rows derived table will give you the number of input parameters. Because of the join, applying the condition of the count of one equaling the count of the other ensures that of the inputs, all of them are found in the outer set. Since you are using MySQL base, avoid the group by for templateId, and your return result will be the templateId(s) that fully contain the input organizationIds.

SELECT O.templateId
FROM (
  SELECT SUBSTRING_INDEX(SUBSTRING_INDEX(@X,',',N.N),',',-1) AS InnerSet
  FROM Num N
  WHERE N.N <= CHAR_LENGTH(@X)-CHAR_LENGTH(REPLACE(@X,',',''))+1
  ) I
  LEFT JOIN template_organizations O ON I.InnerSet = O.organizationId
HAVING COUNT(I.InnerSet) = COUNT(O.organizationId)
;

That last sentence is important! Nothing about your table structure tells me that it's impossible for this procedure to return more than one row if, for example, two templates share a given set of organizaionIds. Keep this in mind when designing the rest of your app, and you'll be fine.

\$\endgroup\$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.