Natural joins are defined, in a semantically correct way, on data structures, called I-tables, of an extended relational database model with indefinite and maybe information. An algorithm for computing natural joins under the extended model is proposed which reduces the number of pair-up operations and block accesses to a linear order of complexity with respect to the size of I-tables. Procedures for the extended natural joins are examined with respect to efficiency, which is evaluated based upon the number of pair-up operations and I/O block accesses. A linear order of pair-up operations is achieved by using the 'compare, concatenate, and then permute' strategy, and a linear order of I/O activities is attained by employing virtual relations with pointers.>

A generalized relational model which is capable of representing and manipulating disjunctive and maybe kinds of information is presented. A data structure, called M-table, is defined, and the information contained in the M-table is precisely stated. Redundant information in M-tables is characterized, and an operator to remove this redundant information is presented. The relational algebra is suitably generalized to deal with M-tables. Additional operators, R-projection and merge, are presented. Queries can be expressed as a combination of the various generalized relational algebraic operators. The M-table accurately models the two bounds on the external interpretation of a query. The sure component of an M-table corresponds to one of the bounds which is the set of objects which belong to the external interpretation of the query. The maybe component of an M-table corresponds to the other bound which is the set of objects for which the possibility of belonging to the external interpretation of the query cannot be ruled out.>

The authors present a generalization of the relational model to represent indefinite and maybe kinds of incomplete information. They introduce a data structure called M-table which is capable of representing disjunctive/indefinite and maybe facts. The notion of redundancy in the context of indefinite and maybe information is studied. The information content of an M-table is precisely defined. The relational algebra is then generalized in a semantically correct manner to operate on M-tables. Queries are posed in the same manner as in the conventional relational algebra; however, the user may now expect indefinite as well as maybe answers.>

This paper extends the relational model to represent indefinite and maybe kinds of incomplete information. A data structure, called an I-table, which is capable of representing indefinite and maybe facts, is introduced. The information content of I-tables is precisely defined, and an operator to remove redundant facts is presented. The relational algebra is then extended in a semantically correct way to operate on I-tables. Queries are posed in the same way as in conventional relational algebra; however, the user may now expect indefinite as well as maybe answers.

An extension is presented of the relational model to present indefinite and maybe kinds of incomplete information. A data structure, called an I-table, is introduced, which is capable of representing indefinite and maybe facts. The information content of the I-table is defined and an operator to remove redundant facts is presented. The relational algebra is then extended, in a semantically correct way, to operate on I-tables. Queries are posed in the same way as in conventional relational algebra, but the user may expect indefinite as well as maybe answers.>

Abstract This paper presents an extension of Pascal with string pattern matching. Pattern definitions are built using six basic operations: alternation, concatenation, immediate value assignment, intersection, difference and complement. The last three have not been previously implemented and they increase the expressive power beyond context‐free languages. The pattern matching actions are augmented with three options: trace, prefix and suffix. Comparisons with a SNOBOL4 implementation are also presented. This experiment demonstrates that Pascal with pattern matching is a useful tool for string processing applications.

A polynomial time algorithm is presented for string pattern matching. Earley’s parsing algorithm is adapted for context-free patterns and is extended to allow the augmentation of the immediate assignment operation of SNOBOL4 and a powerful descriptive operator not previously implemented, set complement. Canonical pattern definition systems are defined to describe patterns for which our algorithm will perform pattern matching. The languages generated by such systems are called extended context-free languages, and are shown to properly contain the family of context-free languages and all families of k-intersection languages which have been shown to establish an infinite hierarchy between the family of context-free languages and the family of context-sensitive languages. It is also shown that for an alphabet of one character, the immediate assignment operator cannot be expressed in terms of the complement operator. Some results on the closure properties and unsolvable problems for this new family are also shown. It is shown that the worst-case time and space complexity of our algorithm is polynomial if the immediate assignment is used, and that the time (space) complexity is cubic (cubic) if the complement but not the immediate assignment operator is used, and is cubic (square) if neither operator is used. Our algorithm has no difficulty with left-recursion or null string alternatives which are problems with the SNONOL4 pattern matching algorithm.