The concept of list is very important in functional programming and data structures in computer science. The classical definition of lists was redefined by Jena, Tripathy, and Ghosh (2001) by using the notion of position functions, which is an extension of the concept of count function of multisets and of characteristic function of sets. Several concepts related to lists have been defined from this new angle and properties are proved further in subsequent articles. In this chapter, the authors focus on crisp lists and present all the concepts and properties developed so far. Recently, the functional approach to realization of relational databases and realization of operations on them has been proposed. In this chapter, a list theory-based relational database model using position function approach is designed to illustrate how query processing can be realized for some of the relational algebraic operations. The authors also develop a list theoretic relational algebra (LRA) and realize analysis of Petri nets using this LRA.
TopIntroduction
The concept of set introduced by G. Cantor (1883) is perhaps the most fundamental notion in mathematics. Although the formal definition of a set led to many antinomies (Reisig, 1983), the deviational cases occur in some artificial situations and so the mathematics basing upon this notion is a sound one for most of the situations. In a set the order of occurrences of elements as well the number of times an element occurs is of no importance. However, it was found later that the number of times an element occurs in a collection is significant in many real life situations and cannot be avoided. This paved the way for the introduction of the notion of bags or multisets (Albert, 1991; Miyamoto, 2001; Yager, 1986). In a bag the number of times an element occurs is accounted for. However, the notions like queues and stacks, piles and racks of books, people seating in a vehicle all require the order of occurrence of elements as significant in modeling them. So, the notion of list was introduced to model such situations (Bird and Walder, 1988). In computer science the notion of arrays plays this role. In a list both the number of times and element occurs and their order of occurrence are important. The foundation of some topics like functional programming depends upon the notion of lists. The applications where arrangement of objects is of importance, the list is the most suitable model. Some other examples of lists can be as follows. Without the concept of list model, permutation cannot be represented. Arrangements of books on a shelf, arrangement of commodities in a ration shop, are better modeled through a list. Words used in natural languages are lists and sentences, paragraphs, pages and books are nothing but lists of characters. A computer program is a list of instructions.
A list is a linearly ordered collection of elements; one can talk about the first element of a list, the second element and so on. Lists are also called sequences in mathematics. Like sequences in mathematics, a list can contain an infinite number of elements. An important property of list is that all the elements of a given list must have the same type: one can have a list of numbers, a list of characters, even a list of lists (of values all of same type), but one cannot mix values of different types in the same list. One can put kind of a constraint on lists.
The concept of lists has long since been used in computer science. Lists are as important in functional programming as the sets are in many branches of mathematics. There was no formal definition of list in the same sense as for sets or multisets. In fact, a set is synonymous with its characteristic function and a bag is synonymous with its count function. However, the corresponding notion is the position unction introduced by Jena et al (2001). There are many advantages of this definition instead of the earlier non-formal definition of a list in the literature. The rich theory of functions could be used to define characteristics of lists and establish their properties in a more formal and concise manner.
The notion of database concept came from the principle of sequential files of data for information processing. Due to the computer system support for handling different types of files, it was required to process the information quickly based on a particular type of databases. Several types of databases have been developed for different applications and the structures of these databases are also different. The development of a database concept from sequential file to rough relational database model changed the world where vague and imprecise data can be handled. The relational database model, which is now used, is associated with the relation of attributes in the form of a table, where it is assumed that there is are duplicate tuples stored in the database. In fuzzy relational database model the information or the data stored is vague and imprecise. Whereas, in the bag database model, it is required to count the number of tuples of same type and stores in a counter, in which the duplicacy of tuples are considered.