bag
Very informally, “a set that permits duplicates”; more precisely, a collection of objects, called elements, in which the same element can appear any number of times. An example is the collection {x,y,y,y,z,z}, which can alternatively be written as, e.g., {y,y,x,z,y,z}, since bags, like sets, have no ordering to their elements. The number of times a given element appears in a given bag is the multiplicity (of that element with respect to that bag). Note: As the foregoing text indicates, a bag is usually represented on paper by a commalist of items denoting the elements that constitute the bag in question, that whole commalist then being enclosed in braces.
Tutorial D in particular uses braces to enclose the commalist of argument expressions in certain n-adic operator invocations when the argument expression commalist in question denotes a bag of arguments (as well as when it denotes a set). For example, the Tutorial D expression
SUM {1,2,2} denotes an invocation of the n-adic version of the aggregate operator SUM (see aggregate operator), and it returns 5, not 3.
The set theory operations of inclusion, union, intersection, difference, exclusive union (also known as symmetric difference), and product—but not complement—can all be generalized to apply to bags, as follows. First, inclusion. Let b1 and b2 be bags, and let element x appear exactly n1 times in b1 and exactly n2 times in b2 (n1 0, n2 0). Then bag b1 includes bag b2 (“b1 ⊇ b2”) if and only if n1 n2 for all such elements x; further, b2 is included in b1
(“b2 ⊆ b1”) if and only if b1 includes b2, and b1 is equal to b2 (“b1 = b2”) if and only if each of b1 and b2 includes the other. Note: All of the terms associated with set inclusion (subset, proper subset, and so on) have analogs in connection with bag inclusion (subbag, proper subbag, and so on).
Now let Op be union, intersection, difference, or exclusive union, and let b be the bag obtained by applying Op to bags b1 and b2 (in that order, in the case of difference), where as before element x appears exactly n1 times in b1 and exactly n2 times in b2 (n1 0, n2 0). Then element x appears exactly n times in b, where n is:
MAX{n1,n2} if Op is union
MIN{n1,n2} if Op is intersection
MAX{n1–n2,0} if Op is difference
Very informally, “a set that permits duplicates”; more precisely, a collection of objects, called elements, in which the same element can appear any number of times. An example is the collection {x,y,y,y,z,z}, which can alternatively be written as, e.g., {y,y,x,z,y,z}, since bags, like sets, have no ordering to their elements. The number of times a given element appears in a given bag is the multiplicity (of that element with respect to that bag). Note: As the foregoing text indicates, a bag is usually represented on paper by a commalist of items denoting the elements that constitute the bag in question, that whole commalist then being enclosed in braces.
Tutorial D in particular uses braces to enclose the commalist of argument expressions in certain n-adic operator invocations when the argument expression commalist in question denotes a bag of arguments (as well as when it denotes a set). For example, the Tutorial D expression
SUM {1,2,2} denotes an invocation of the n-adic version of the aggregate operator SUM (see aggregate operator), and it returns 5, not 3.
The set theory operations of inclusion, union, intersection, difference, exclusive union (also known as symmetric difference), and product—but not complement—can all be generalized to apply to bags, as follows. First, inclusion. Let b1 and b2 be bags, and let element x appear exactly n1 times in b1 and exactly n2 times in b2 (n1 0, n2 0). Then bag b1 includes bag b2 (“b1 ⊇ b2”) if and only if n1 n2 for all such elements x; further, b2 is included in b1
(“b2 ⊆ b1”) if and only if b1 includes b2, and b1 is equal to b2 (“b1 = b2”) if and only if each of b1 and b2 includes the other. Note: All of the terms associated with set inclusion (subset, proper subset, and so on) have analogs in connection with bag inclusion (subbag, proper subbag, and so on).
Now let Op be union, intersection, difference, or exclusive union, and let b be the bag obtained by applying Op to bags b1 and b2 (in that order, in the case of difference), where as before element x appears exactly n1 times in b1 and exactly n2 times in b2 (n1 0, n2 0). Then element x appears exactly n times in b, where n is:
MAX{n1,n2} if Op is union
MIN{n1,n2} if Op is intersection
MAX{n1–n2,0} if Op is difference
In no case does b contain any other elements.
Again let elements x1 and x2 appear exactly n1 times in b1 and exactly n2 times in b2,
respectively (n1 0, n2 0), and let b be the product of b1 and b2, in that order. Then the ordered pair <x1,x2> appears exactly n1*n2 times as an element of b, and b contains no other elements.
Finally, there are two further operations, union plus and intersection star (also known by a variety of other names), that have no counterpart in set theory. Let b be the bag obtained by applying one of these operations to bags b1 and b2, where once again element x appears exactly n1 times in b1 and exactly n2 times in b2 (n1 0, n2 0). Then x appears exactly n times as an element of b, where n is:
n1+n2 if Op is union plus
n1*n2 if Op is intersection star
(and b contains no other elements).
Examples: Let b1 and b2 be the bags {w,w,x,x,y} and {x,y,y,y,z,z}, respectively. Then the
following expressions yield the indicated results:
Again let elements x1 and x2 appear exactly n1 times in b1 and exactly n2 times in b2,
respectively (n1 0, n2 0), and let b be the product of b1 and b2, in that order. Then the ordered pair <x1,x2> appears exactly n1*n2 times as an element of b, and b contains no other elements.
Finally, there are two further operations, union plus and intersection star (also known by a variety of other names), that have no counterpart in set theory. Let b be the bag obtained by applying one of these operations to bags b1 and b2, where once again element x appears exactly n1 times in b1 and exactly n2 times in b2 (n1 0, n2 0). Then x appears exactly n times as an element of b, where n is:
n1+n2 if Op is union plus
n1*n2 if Op is intersection star
(and b contains no other elements).
Examples: Let b1 and b2 be the bags {w,w,x,x,y} and {x,y,y,y,z,z}, respectively. Then the
following expressions yield the indicated results:
-
b1 UNION b2
-
b1 INTERSECT b2
-
b1 MINUS b2
-
b2 MINUS b1
-
b1 XUNION b2
-
b1 TIMES b2
-
b1 UNION+ b2
-
b1 INTERSECT* b2
= {w,w,x,x,y,y,y,z,z}
= {x,y}
= {w,w,x}
= {y,y,z,z}
= {w,w,x,y,y,z,z}
= {<w,x>,<w,x>,<x,x>,<x,x>,<y,x>, <w,y>,<w,y>,<x,y>,<x,y>,<y,y>, <w,y>,<w,y>,<x,y>,<x,y>,<y,y>, <w,y>,<w,y>,<x,y>,<x,y>,<y,y>, <w,z>,<w,z>,<x,z>,<x,z>,<y,z>, <w,z>,<w,z>,<x,z>,<x,z>,<y,z>}
= {w,w,x,x,x,y,y,y,y,z,z} = {x,x,y,y,y}
= {w,w,x}
= {y,y,z,z}
= {w,w,x,y,y,z,z}
= {<w,x>,<w,x>,<x,x>,<x,x>,<y,x>, <w,y>,<w,y>,<x,y>,<x,y>,<y,y>, <w,y>,<w,y>,<x,y>,<x,y>,<y,y>, <w,y>,<w,y>,<x,y>,<x,y>,<y,y>, <w,z>,<w,z>,<x,z>,<x,z>,<y,z>, <w,z>,<w,z>,<x,z>,<x,z>,<y,z>}
= {w,w,x,x,x,y,y,y,y,z,z} = {x,x,y,y,y}
A note on SQL: SQL tables in general contain bags (not sets) of rows, and SQL supports
certain bag operations on such tables. To be specific, it supports bag intersection and bag
difference, through its operators INTERSECT ALL and EXCEPT ALL, respectively.
It also supports union plus, through its operator UNION ALL. It doesn’t support bag exclusive union, intersection star, or (oddly enough) true bag union. As for bag product, SQL’s regular product operator—which is supported in a variety of syntactic styles, including, for example, the CROSS version of SQL’s explicit JOIN operator—in fact represents an extended or expanded form of bag product, much as TIMES in Tutorial D represents an extended or expanded form of the set theory product operator. See cartesian product.
It also supports union plus, through its operator UNION ALL. It doesn’t support bag exclusive union, intersection star, or (oddly enough) true bag union. As for bag product, SQL’s regular product operator—which is supported in a variety of syntactic styles, including, for example, the CROSS version of SQL’s explicit JOIN operator—in fact represents an extended or expanded form of bag product, much as TIMES in Tutorial D represents an extended or expanded form of the set theory product operator. See cartesian product.
댓글 없음:
댓글 쓰기