In the theory of formal languages, the pumping lemma for regular languages is a lemma that describes an essential property of all regular languages. Informally, it says that all sufficiently long strings in a regular language may be pumped—that is, have a middle section of the string repeated an arbitrary number of times—to produce a new string that is also part of the language. The pumping lemma is useful for proving that a specific language is not a regular language, by showing that the language does not have the property. Specifically, the pumping lemma says that for any regular language L {\displaystyle L} , there exists a constant p {\displaystyle p} such that any string w {\displaystyle w} in L {\displaystyle L} with length at least p {\displaystyle p} can be split into three substrings x {\displaystyle x} , y {\displaystyle y} and z {\displaystyle z} ( w = x y z {\displaystyle w=xyz} , with y {\displaystyle y} being non-empty), such that the strings x z , x y z , x y y z , x y y y z , . . . {\displaystyle xz,xyz,xyyz,xyyyz,...} are also in L {\displaystyle L} . The process of repeating y {\displaystyle y} zero or more times is known as "pumping". Moreover, the pumping lemma guarantees that the length of x y {\displaystyle xy} will be at most p {\displaystyle p} , thus giving a "small" substring x y {\displaystyle xy} that has the desired property. Languages with a finite number of strings vacuously satisfy the pumping lemma by having p {\displaystyle p} equal to the maximum string length in L {\displaystyle L} plus one. By doing so, no strings at all in L {\displaystyle L} have length at least p {\displaystyle p} . The pumping lemma was first proven by Michael Rabin and Dana Scott in 1959, and rediscovered shortly after by Yehoshua Bar-Hillel, Micha A. Perles, and Eli Shamir in 1961, as a simplification of their pumping lemma for context-free languages. == Formal statement == Let L {\displaystyle L} be a regular language. Then there exists an integer p ≥ 1 {\displaystyle p\geq 1} depending only on L {\displaystyle L} such that every string w {\displaystyle w} in L {\displaystyle L} of length at least p {\displaystyle p} ( p {\displaystyle p} is called the "pumping length") can be written as w = x y z {\displaystyle w=xyz} (i.e., w {\displaystyle w} can be divided into three substrings), satisfying the following conditions: | y | ≥ 1 {\displaystyle |y|\geq 1} | x y | ≤ p {\displaystyle |xy|\leq p} ( ∀ n ≥ 0 ) ( x y n z ∈ L ) {\displaystyle (\forall n\geq 0)(xy^{n}z\in L)} y {\displaystyle y} is the substring that can be pumped (removed or repeated any number of times, and the resulting string is always in L {\displaystyle L} ). (1) means the loop y {\displaystyle y} to be pumped must be of length at least one, that is, not an empty string; (2) means the loop must occur within the first p {\displaystyle p} characters. | x | {\displaystyle |x|} must be smaller than p {\displaystyle p} (conclusion of (1) and (2)), but apart from that, there is no restriction on x {\displaystyle x} and z {\displaystyle z} . In simple words, for any regular language L {\displaystyle L} , any sufficiently long string w {\displaystyle w} (in L {\displaystyle L} ) can be split into 3 parts, i.e. w = x y z {\displaystyle w=xyz} , such that all the strings x y n z {\displaystyle xy^{n}z} for n ≥ 0 {\displaystyle n\geq 0} are also in L {\displaystyle L} . Below is a formal expression of the pumping lemma. ∀ L ⊆ Σ ∗ , regular ( L ) ⟹ ∃ p ≥ 1 , ∀ w ∈ L , | w | ≥ p ⟹ ∃ x , y , z ∈ Σ ∗ , ( w = x y z ) ∧ ( | y | ≥ 1 ) ∧ ( | x y | ≤ p ) ∧ ( ∀ n ≥ 0 , x y n z ∈ L ) {\displaystyle {\begin{array}{l}\forall L\subseteq \Sigma ^{},{\mbox{regular}}(L)\implies \\\quad \exists p\geq 1,\forall w\in L,|w|\geq p\implies \\\qquad \exists x,y,z\in \Sigma ^{},(w=xyz)\land (|y|\geq 1)\land (|xy|\leq p)\land (\forall n\geq 0,xy^{n}z\in L)\end{array}}} == Use of the lemma to prove non-regularity == The pumping lemma is often used to prove that a particular language is non-regular: a proof by contradiction may consist of exhibiting a string (of the required length) in the language that lacks the property outlined in the pumping lemma. Example: The language L = { a n b n : n ≥ 0 } {\displaystyle L=\{a^{n}b^{n}:n\geq 0\}} over the alphabet Σ = { a , b } {\displaystyle \Sigma =\{a,b\}} can be shown to be non-regular as follows: Assume that some constant p ≥ 1 {\displaystyle p\geq 1} exists as required by the lemma. Let w {\displaystyle w} in L {\displaystyle L} be given by w = a p b p {\displaystyle w=a^{p}b^{p}} , which is a string longer than p {\displaystyle p} . By the pumping lemma, there must exist a decomposition w = x y z {\displaystyle w=xyz} with | x y | ≤ p {\displaystyle |xy|\leq p} and | y | ≥ 1 {\displaystyle |y|\geq 1} such that x y i z {\displaystyle xy^{i}z} in L {\displaystyle L} for every i ≥ 0 {\displaystyle i\geq 0} . Since | x y | ≤ p {\displaystyle |xy|\leq p} , the string y {\displaystyle y} only consists of instances of a {\displaystyle a} . Because | y | ≥ 1 {\displaystyle |y|\geq 1} , it contains at least one instance of the letter a {\displaystyle a} . Pumping y {\displaystyle y} to give x y 2 z {\displaystyle xy^{2}z} gives a word with more instances of the letter a {\displaystyle a} than the letter b {\displaystyle b} , since some instances of a {\displaystyle a} but none of b {\displaystyle b} were added. Therefore, x y 2 z {\displaystyle xy^{2}z} is not in L {\displaystyle L} which contradicts the pumping lemma. Therefore, L {\displaystyle L} cannot be regular. The proof that the language of balanced (i.e., properly nested) parentheses is not regular follows the same idea. Given p {\displaystyle p} , there is a string of balanced parentheses that begins with more than p {\displaystyle p} left parentheses, so that y {\displaystyle y} will consist entirely of left parentheses. By repeating y {\displaystyle y} , a string can be produced that does not contain the same number of left and right parentheses, and so they cannot be balanced. == Proof of the pumping lemma == For every regular language there is a finite-state automaton (FSA) that accepts the language. The number of states in such an FSA are counted and that count is used as the pumping length p {\displaystyle p} . For a string of length at least p {\displaystyle p} , let q 0 {\displaystyle q_{0}} be the start state and let q 1 , . . . , q p {\displaystyle q_{1},...,q_{p}} be the sequence of the next p {\displaystyle p} states visited as the string is emitted. Because the FSA has only p {\displaystyle p} states, within this sequence of p + 1 {\displaystyle p+1} visited states there must be at least one state that is repeated. Write q s {\displaystyle q_{s}} for such a state. The transitions that take the machine from the first encounter of state q s {\displaystyle q_{s}} to the second encounter of state q s {\displaystyle q_{s}} match some string. This string is called y {\displaystyle y} in the lemma, and since the machine will match a string without the y {\displaystyle y} portion, or with the string y {\displaystyle y} repeated any number of times, the conditions of the lemma are satisfied. For example, the following image shows an FSA. The FSA accepts the string: abcd. Since this string has a length at least as large as the number of states, which is four (so the total number of states that the machine passes through to scan abcd would be 5), the pigeonhole principle indicates that there must be at least one repeated state among the start state and the next four visited states. In this example, only q 1 {\displaystyle q_{1}} is a repeated state. Since the substring bc takes the machine through transitions that start at state q 1 {\displaystyle q_{1}} and end at state q 1 {\displaystyle q_{1}} , that portion could be repeated and the FSA would still accept, giving the string abcbcd. Alternatively, the bc portion could be removed and the FSA would still accept giving the string ad. In terms of the pumping lemma, the string abcd is broken into an x {\displaystyle x} portion a, a y {\displaystyle y} portion bc and a z {\displaystyle z} portion d. As a side remark, the problem of checking whether a given string can be accepted by a given nondeterministic finite automaton without visiting any state repeatedly, is NP hard. == General version of pumping lemma for regular languages == If a language L {\displaystyle L} is regular, then there exists a number p ≥ 1 {\displaystyle p\geq 1} (the pumping length) such that every string u w v {\displaystyle uwv} in L {\displaystyle L} with | w | ≥ p {\displaystyle |w|\geq p} can be written in the form u w v = u x y z v {\displaystyle uwv=uxyzv} with strings x {\displaystyle x} , y {\displaystyle y} and z {\displaystyle z} such that | x y | ≤ p {\displaystyle |xy|\leq p} , | y | ≥ 1 {\displaystyle |y|\geq 1} and u x y i z v {\displaystyle uxy^{i}zv} is in L {\displaystyle L} for every integer i ≥ 0 {\displaystyle i\geq 0} . From this, the above standard v
Imo.im
imo.im is a proprietary audio/video calling and instant messaging software service. It allows sending music, video, PDFs and other files, along with various free stickers. It supports encrypted group video and voice calls with up to 20 participants. According to its developer, the service possesses over 200 million users and over 50 million messages per day are sent through it. == History == The product was created as a web-based application in 2005 for accessing multiple chat platforms, including Facebook Messenger, Google Talk, Yahoo! Messenger, and Skype chat. It was developed by Pagebites, which is a subsidiary of Singularity IM, Inc. and required a subscriber's phone number to verify the users' account. In March 2014, support for all third-party messaging networks ended. In January 2018, the app reached 500 million installs. imo.im has implemented end-to-end encryption for its chats and calls, ensuring that the conversations remain private between the sender and receiver.
Data stream management system
A data stream management system (DSMS) is a computer software system to manage continuous data streams. It is similar to a database management system (DBMS), which is, however, designed for static data in conventional databases. A DBMS also offers a flexible query processing so that the information needed can be expressed using queries. However, in contrast to a DBMS, a DSMS executes a continuous query that is not only performed once, but is permanently installed. Therefore, the query is continuously executed until it is explicitly uninstalled. Since most DSMS are data-driven, a continuous query produces new results as long as new data arrive at the system. This basic concept is similar to complex event processing so that both technologies are partially coalescing. == Functional principle == One important feature of a DSMS is the possibility to handle potentially infinite and rapidly changing data streams by offering flexible processing at the same time, although there are only limited resources such as main memory. The following table provides various principles of DSMS and compares them to traditional DBMS. == Processing and streaming models == One of the biggest challenges for a DSMS is to handle potentially infinite data streams using a fixed amount of memory and no random access to the data. There are different approaches to limit the amount of data in one pass, which can be divided into two classes. For the one hand, there are compression techniques that try to summarize the data and for the other hand there are window techniques that try to portion the data into (finite) parts. === Synopses === The idea behind compression techniques is to maintain only a synopsis of the data, but not all (raw) data points of the data stream. The algorithms range from selecting random data points called sampling to summarization using histograms, wavelets or sketching. One simple example of a compression is the continuous calculation of an average. Instead of memorizing each data point, the synopsis only holds the sum and the number of items. The average can be calculated by dividing the sum by the number. However, it should be mentioned that synopses cannot reflect the data accurately. Thus, a processing that is based on synopses may produce inaccurate results. === Windows === Instead of using synopses to compress the characteristics of the whole data streams, window techniques only look on a portion of the data. This approach is motivated by the idea that only the most recent data are relevant. Therefore, a window continuously cuts out a part of the data stream, e.g. the last ten data stream elements, and only considers these elements during the processing. There are different kinds of such windows like sliding windows that are similar to FIFO lists or tumbling windows that cut out disjoint parts. Furthermore, the windows can also be differentiated into element-based windows, e.g., to consider the last ten elements, or time-based windows, e.g., to consider the last ten seconds of data. There are also different approaches to implementing windows. There are, for example, approaches that use timestamps or time intervals for system-wide windows or buffer-based windows for each single processing step. Sliding-window query processing is also suitable to being implemented in parallel processors by exploiting parallelism between different windows and/or within each window extent. == Query processing == Since there are a lot of prototypes, there is no standardized architecture. However, most DSMS are based on the query processing in DBMS by using declarative languages to express queries, which are translated into a plan of operators. These plans can be optimized and executed. A query processing often consists of the following steps. === Formulation of continuous queries === The formulation of queries is mostly done using declarative languages like SQL in DBMS. Since there are no standardized query languages to express continuous queries, there are a lot of languages and variations. However, most of them are based on SQL, such as the Continuous Query Language (CQL), StreamSQL and ESP. There are also graphical approaches where each processing step is a box and the processing flow is expressed by arrows between the boxes. The language strongly depends on the processing model. For example, if windows are used for the processing, the definition of a window has to be expressed. In StreamSQL, a query with a sliding window for the last 10 elements looks like follows: This stream continuously calculates the average value of "price" of the last 10 tuples, but only considers those tuples whose prices are greater than 100.0. In the next step, the declarative query is translated into a logical query plan. A query plan is a directed graph where the nodes are operators and the edges describe the processing flow. Each operator in the query plan encapsulates the semantic of a specific operation, such as filtering or aggregation. In DSMSs that process relational data streams, the operators are equal or similar to the operators of the Relational algebra, so that there are operators for selection, projection, join, and set operations. This operator concept allows the very flexible and versatile processing of a DSMS. === Optimization of queries === The logical query plan can be optimized, which strongly depends on the streaming model. The basic concepts for optimizing continuous queries are equal to those from database systems. If there are relational data streams and the logical query plan is based on relational operators from the Relational algebra, a query optimizer can use the algebraic equivalences to optimize the plan. These may be, for example, to push selection operators down to the sources, because they are not so computationally intensive like join operators. Furthermore, there are also cost-based optimization techniques like in DBMS, where a query plan with the lowest costs is chosen from different equivalent query plans. One example is to choose the order of two successive join operators. In DBMS this decision is mostly done by certain statistics of the involved databases. But, since the data of a data streams is unknown in advance, there are no such statistics in a DSMS. However, it is possible to observe a data stream for a certain time to obtain some statistics. Using these statistics, the query can also be optimized later. So, in contrast to a DBMS, some DSMS allows to optimize the query even during runtime. Therefore, a DSMS needs some plan migration strategies to replace a running query plan with a new one. === Transformation of queries === Since a logical operator is only responsible for the semantics of an operation but does not consist of any algorithms, the logical query plan must be transformed into an executable counterpart. This is called a physical query plan. The distinction between a logical and a physical operator plan allows more than one implementation for the same logical operator. The join, for example, is logically the same, although it can be implemented by different algorithms like a Nested loop join or a Sort-merge join. Notice, these algorithms also strongly depend on the used stream and processing model. Finally, the query is available as a physical query plan. === Execution of queries === Since the physical query plan consists of executable algorithms, it can be directly executed. For this, the physical query plan is installed into the system. The bottom of the graph (of the query plan) is connected to the incoming sources, which can be everything like connectors to sensors. The top of the graph is connected to the outgoing sinks, which may be for example a visualization. Since most DSMSs are data-driven, a query is executed by pushing the incoming data elements from the source through the query plan to the sink. Each time when a data element passes an operator, the operator performs its specific operation on the data element and forwards the result to all successive operators. == Examples == AURORA, StreamBase Systems, Inc. Archived 23 March 2009 at the Wayback Machine Hortonworks DataFlow IBM Streams NIAGARA Query Engine NiagaraST: A Research Data Stream Management System at Portland State University Odysseus, an open source Java-based framework for Data Stream Management Systems Pipeline DB PIPES Archived 24 December 2016 at the Wayback Machine, webMethods Business Events QStream SAS Event Stream Processing SQLstream STREAM StreamGlobe StreamInsight TelegraphCQ WSO2 Stream Processor
Opinion Space
Developed at UC Berkeley, "Opinion Space" (also known as The Collective Discovery Engine) is a social media technology designed to help communities generate and exchange ideas about important issues and policies. Version 1.0 was launched on April 4, 2009, at UC Berkeley, and explored the question "Do you think legalizing marijuana is a good idea?" It has since undergone 4 different iterations, and been used in partnership with various organizations including The Occupy movement (Version 4.0, 5/24/2013) and the African Robots Network (Version 4.0, 5/25/2013). Opinion Space has also been used in collaboration with the United States State Department and the University of California's Berkeley Center for New Media (Version 2.0, 12/1/2009 and Version 3.0, 2/25/2012) to gain public perspective on foreign policy issues. Then U.S. Secretary of State Hillary Rodham Clinton explained, "Opinion Space will harness the power of connection technologies to provide a unique forum for international dialogue. This is...an opportunity to extend our engagement beyond the halls of government directly to the people of the world" (2010). The website uses data visualization and statistical analysis to present and develop public opinion and ideas. Opinion Space is a self-organizing system that uses an intuitive graphical "map" that displays patterns, trends, and insights as they emerge and employs the wisdom of crowds to identify and highlight the most insightful ideas. The system uses a game model that incorporates techniques from deliberative polling, collaborative filtering, and multidimensional visualization.
Cloud Data Management Interface
ISO/IEC 17826 Information technology — Cloud Data Management Interface (CDMI) Version 2.0.0 is an international standard that specifies a protocol for self-provisioning, administering and managing access to data stored in cloud storage, object storage, storage area network and network attached storage systems. The CDMI standard is developed and maintained by the Storage Networking Industry Association, who makes a publicly accessible version of the specification available. CDMI defines new resource representations to enable standardized management of any URI-accessible data, and defines RESTful HTTP operations using these representations to discover the capabilities of the storage system, discover stored data, access and update management metadata, specify data storage protocols (such as iSCSI and NFS) through which the stored data is accessed, and provide cross-system and cross-cloud import and export in order to enable data portability. Management functions enabled by CDMI include managing data ownership, identity mapping, access controls, user-specified metadata, and to declaratively specify desired data protection, data retention, constraints on geographic placement, desired quality of service, data versioning and security requirements. CDMI also defines utility services to facilitate data management, such the ability to query data matching specific criteria, and includes extensions to perform bulk updates using CDMI Jobs. == Capabilities == Compliant implementations must provide access to a set of configuration parameters known as capabilities. These are either boolean values that represent whether or not a system supports things such as queues, export via other protocols, path-based storage and so on, or numeric values expressing system limits, such as how much metadata may be placed on an object. As a minimal compliant implementation can be quite small, with few features, clients need to check the cloud storage system for a capability before attempting to use the functionality it represents. Resource allocation assignments limited to the data management interface protocols must possess access bypass capabilities which extend beyond the layered framework. This integral function is vital to the prevention of transport layer session hijacking by unauthorized entities which may circumvent standard interfacing security parameters. == Containers == A CDMI client may access objects, including containers, by either name or object id (OID), assuming the CDMI server supports both methods. When storing objects by name, it is natural to use nested named containers; the resulting structure corresponds exactly to a traditional filesystem directory structure. == Objects == Objects are similar to files in a traditional file system, but are enhanced with an increased amount and capacity for metadata. As with containers, they may be accessed by either name or OID. When accessed by name, clients use URLs that contain the full pathname of objects to create, read, update and delete them. When accessed by OID, the URL specifies an OID string in the cdmi-objectid container; this container presents a flat name space conformant with standard object storage system semantics. Subject to system limits, objects may be of any size or type and have arbitrary user-supplied metadata attached to them. Systems that support query allow arbitrary queries to be run against the metadata. == Domains, Users and Groups == CDMI supports the concept of a domain, similar in concept to a domain in the Windows Active Directory model. Users and groups created in a domain share a common administrative database and are known to each other on a "first name" basis, i.e. without reference to any other domain or system. Domains also function as containers for usage and billing summary data. == Access Control == CDMI exactly follows the ACL and ACE model used for file authorization operations by NFSv4. This makes it also compatible with Microsoft Windows systems. == Metadata == CDMI draws much of its metadata model from the XAM specification. Objects and containers have "storage system metadata", "data system metadata" and arbitrary user specified metadata, in addition to the metadata maintained by an ordinary filesystem (atime etc.). == Queries == CDMI specifies a way for systems to support arbitrary queries against CDMI containers, with a rich set of comparison operators, including support for regular expressions. == Queues == CDMI supports the concept of persistent FIFO (first-in, first-out) queues. These are useful for job scheduling, order processing and other tasks in which lists of things must be processed in order. == Compliance == Both retention intervals and retention holds are supported by CDMI. A retention interval consists of a start time and a retention period. During this time interval, objects are preserved as immutable and may not be deleted. A retention hold is usually placed on an object because of judicial action and has the same effect: objects may not be changed nor deleted until all holds placed on them are removed. == Billing == Summary information suitable for billing clients for on-demand services can be obtained by authorized users from systems that support it. == Serialization == Serialization of objects and containers allows export of all data and metadata on a system and importation of that data into another cloud system. == Foreign protocols == CDMI supports export of containers as NFS or CIFS shares. Clients that mount these shares see the container hierarchy as an ordinary filesystem directory hierarchy, and the objects in the containers as normal files. Metadata outside of ordinary filesystem metadata may or may not be exposed. Provisioning of iSCSI LUNs is also supported. == Client SDKs == CDMI Reference Implementation Droplet libcdmi-java libcdmi-python .NET SDK
Yap (company)
Yap Speech Cloud was a multimodal speech recognition system developed by American technology company Yap Inc. It offered a fully cloud-based speech-to-text transcription platform that was used by customers such as Microsoft. The Company was a contestant at the inaugural TechCrunch conference and was subsequently acquired by Amazon in September 2011 to help develop products such as Alexa Voice Service, Echo, and Fire TV.
Data set (IBM mainframe)
In the context of IBM mainframe computers in the IBM System/360 line and its successors, a data set (IBM preferred) or dataset is a computer file having a record organization. Use of this term began with, e.g., DOS/360 and OS/360, and is still used by their successors, including the current VSE and z/OS. Documentation for these systems historically preferred this term rather than file. A data set is typically stored on a direct access storage device (DASD) or magnetic tape, however unit record devices, such as punch card readers, card punches, line printers and page printers can provide input/output (I/O) for a data set (file). Data sets are not unstructured streams of bytes, but rather are organized in various logical record and block structures determined by the DSORG (data set organization), RECFM (record format), and other parameters. These parameters are specified at the time of the data set allocation (creation), for example with Job Control Language DD statements. Within a running program they are stored in the Data Control Block (DCB) or Access Control Block (ACB), which are data structures used to access data sets using access methods. Records in a data set may be fixed, variable, or “undefined” length. == Data set organization == For OS/360, the DCB's DSORG parameter specifies how the data set is organized. It may be CQ Queued Telecommunications Access Method (QTAM) in Message Control Program (MCP) CX Communications line group DA Basic Direct Access Method (BDAM) GS Graphics device for Graphics Access Method(GAM) IS Indexed Sequential Access Method (ISAM) MQ QTAM message queue in application PO Partitioned Organization PS Physical Sequential among others. Data sets on tape may only be DSORG=PS. The choice of organization depends on how the data is to be accessed, and in particular, how it is to be updated. Programmers utilize various access methods (such as QSAM or VSAM) in programs for reading and writing data sets. Access method depends on the given data set organization. == Record format (RECFM) == Regardless of organization, the physical structure of each record is essentially the same, and is uniform throughout the data set. This is specified in the DCB RECFM parameter. RECFM=F means that the records are of fixed length, specified via the LRECL parameter. RECFM=V specifies a variable-length record. V records when stored on media are prefixed by a Record Descriptor Word (RDW) containing the integer length of the record in bytes and flag bits. With RECFM=FB and RECFM=VB, multiple logical records are grouped together into a single physical block on tape or DASD. FB and VB are fixed-blocked, and variable-blocked, respectively. RECFM=U (undefined) is also variable length, but the length of the record is determined by the length of the block rather than by a control field. The BLKSIZE parameter specifies the maximum length of the block. RECFM=FBS could be also specified, meaning fixed-blocked standard, meaning all the blocks except the last one were required to be in full BLKSIZE length. RECFM=VBS, or variable-blocked spanned, means a logical record could be spanned across two or more blocks, with flags in the RDW indicating whether a record segment is continued into the next block and/or was continued from the previous one. This mechanism eliminates the need for using any "delimiter" byte value to separate records. Thus data can be of any type, including binary integers, floating-point, or characters, without introducing a false end-of-record condition. The data set is an abstraction of a collection of records, in contrast to files as unstructured streams of bytes. == Partitioned data set == A partitioned data set (PDS) is a data set containing multiple members, each of which holds a separate sub-data set, similar to a directory in other types of file systems. This type of data set is often used to hold load modules (old format bound executable programs), source program libraries (especially Assembler macro definitions), ISPF screen definitions, and Job Control Language. A PDS may be compared to a Zip file or COM Structured Storage. A Partitioned Data Set can only be allocated on a single volume and have a maximum size of 65,535 tracks. Besides members, a PDS contains also a directory. Each member can be accessed indirectly via the directory structure. Once a member is located, the data stored in that member are handled in the same manner as a PS (sequential) data set. Whenever a member is deleted, the space it occupied is unusable for storing other data. Likewise, if a member is re-written, it is stored in a new spot at the back of the PDS and leaves wasted “dead” space in the middle. The only way to recover “dead” space is to perform file compression. Compression, which is done using the IEBCOPY utility, moves all members to the front of the data space and leaves free usable space at the back. (Note that in modern parlance, this kind of operation might be called defragmentation or garbage collection; data compression nowadays refers to a different, more complicated concept.) PDS files can only reside on DASD, not on magnetic tape, in order to use the directory structure to access individual members. Partitioned data sets are most often used for storing multiple job control language files, utility control statements, and executable modules. An improvement of this scheme is a Partitioned Data Set Extended (PDSE or PDS/E, sometimes just libraries) introduced with DFSMSdfp for MVS/XA and MVS/ESA systems. A PDS/E library can store program objects or other types of members, but not both. BPAM cannot process a PDS/E containing program objects. PDS/E structure is similar to PDS and is used to store the same types of data. However, PDS/E files have a better directory structure which does not require pre-allocation of directory blocks when the PDS/E is defined (and therefore does not run out of directory blocks if not enough were specified). Also, PDS/E automatically stores members in such a way that compression operation is not needed to reclaim "dead" space. PDS/E files can only reside on DASD in order to use the directory structure to access individual members. == Generation Data Group == A Generation Data Group (GDG) is a group of non-VSAM data sets that are successive generations of historically-related data stored on an IBM mainframe (running OS/360 and its successors or DOS/360 and its successors). A GDG is usually cataloged. An individual member of the GDG collection is called a "Generation Data Set." The latter may be identified by an absolute number, ACCTG.OURGDG(1234), or a relative number: (-1) for the previous generation, (0) for the current one, and (+1) the next generation. A GDG specifies how many generations of a data set are to be kept and at what age a generation will be deleted. Whenever a new generation is created, the system checks whether one or more obsolete generations are to be deleted. The purpose of GDGs is to automate archival, using the command language JCL, the data set name given is generic. When DSN appears, the GDG data set appears along with the history number, where (0) is the most recent version (-1), (-2), ... are previous generations (+1) a new generation (see DD) Another use of GDGs is to be able to address all generations simultaneously within a JCL script without having to know the number of currently available generations. To do this, you have to omit the parentheses and the generation number in the JCL when specifying the dataset. === GDG JCL & features === Generation Data Groups are defined using either the BLDG statement of the IEHPROGM utility or the DEFINE GENERATIONGROUP statement of the newer IDCAMS utility, which allows setting various parameters. LIMIT(10) would limit the number of generations limit to 10. SCRATCH FOR (91) would retain each member, up to the limited#generations, at least 91 days. IDCAMS can also delete (and optionally uncatalog) a GDG. ==== Example ==== Creation of a standard GDG for five safety scopes, each at least 35 days old: Delete a standard GDG: