An algebraic theory of functional and multivalued dependencies in relational databases

Computation of the dependency basis is the fundamental step in solving the membership problem for functional dependencies (FDs) and multivalued dependencies (MVDs) in relational database theory. We examine this problem from an algebraic perspective. We introduce the notion of the inference basis of a set M of MVDs and show that it contains the maximum information about the logical consequences of M. We propose the notion of a dependency-lattice and develop an algebraic characterization of inference basis using simple notions from lattice theory. We also establish several interesting properties of dependency-lattices related to the implication problem. Founded on our characterization, we synthesize efficient algorithms for (a): computing the inference basis of a given set M of MVDs; (b): computing the dependency basis of a given attribute set w.r.t. M; and (c): solving the membership problem for MVDs. We also show that our results naturally extend to incorporate FDs also in a way that enables the solution of the membership problem for both FDs and MVDs put together. We finally show that our algorithms are more efficient than existing ones, when used to solve what we term the ‘generalized membership problem’.

Algebraic characterization of rainbow connectivity

The use of algebraic techniques to solve combinatorial problems is studied in this paper. We formulate the rainbow connectivity problem as a system of polynomial equations. We first consider the case of two colors for which the problem is known to be hard and we then extend the approach to the general case. We also present a formulation of the rainbow connectivity problem as an ideal membership problem.

On the Gap-Complexity of Simple RL-Automata

Analysis by reduction is a method used in linguistics for checking the correctness of sentences of natural languages. This method is modelled by restarting automata. All types of restarting automata considered in the literature up to now accept at least the deterministic context-free languages. Here we introduce and study a new type of restarting automaton, the so-called t-RL-automaton, which is an RL-automaton that is rather restricted in that it has a window of size one only, and that it works under a minimal acceptance condition. On the other hand, it is allowed to perform up to t rewrite (that is, delete) steps per cycle. Here we study the gap-complexity of these automata. The membership problem for a language that is accepted by a t-RL-automaton with a bounded number of gaps can be solved in polynomial time. On the other hand, t-RL-automata with an unbounded number of gaps accept NP-complete languages.

Systems of Parallel Communicating Restarting Automata

In der vorliegenden Dissertation werden Systeme von parallel arbeitenden und miteinander kommunizierenden Restart-Automaten (engl.: systems of parallel communicating restarting automata; abgekürzt PCRA-Systeme) vorgestellt und untersucht. Dabei werden zwei bekannte Konzepte aus den Bereichen Formale Sprachen und Automatentheorie miteinander vescrknüpft: das Modell der Restart-Automaten und die sogenannten PC-Systeme (systems of parallel communicating components). Ein PCRA-System besteht aus endlich vielen Restart-Automaten, welche einerseits parallel und unabhängig voneinander lokale Berechnungen durchführen und andererseits miteinander kommunizieren dürfen. Die Kommunikation erfolgt dabei durch ein festgelegtes Kommunikationsprotokoll, das mithilfe von speziellen Kommunikationszuständen realisiert wird. Ein wesentliches Merkmal hinsichtlich der Kommunikationsstruktur in Systemen von miteinander kooperierenden Komponenten ist, ob die Kommunikation zentralisiert oder nichtzentralisiert erfolgt. Während in einer nichtzentralisierten Kommunikationsstruktur jede Komponente mit jeder anderen Komponente kommunizieren darf, findet jegliche Kommunikation innerhalb einer zentralisierten Kommunikationsstruktur ausschließlich mit einer ausgewählten Master-Komponente statt. Eines der wichtigsten Resultate dieser Arbeit zeigt, dass zentralisierte Systeme und nichtzentralisierte Systeme die gleiche Berechnungsstärke besitzen (das ist im Allgemeinen bei PC-Systemen nicht so). Darüber hinaus bewirkt auch die Verwendung von Multicast- oder Broadcast-Kommunikationsansätzen neben Punkt-zu-Punkt-Kommunikationen keine Erhöhung der Berechnungsstärke. Desweiteren wird die Ausdrucksstärke von PCRA-Systemen untersucht und mit der von PC-Systemen von endlichen Automaten und mit der von Mehrkopfautomaten verglichen. PC-Systeme von endlichen Automaten besitzen bekanntermaßen die gleiche Ausdrucksstärke wie Einwegmehrkopfautomaten und bilden eine untere Schranke für die Ausdrucksstärke von PCRA-Systemen mit Einwegkomponenten. Tatsächlich sind PCRA-Systeme auch dann stärker als PC-Systeme von endlichen Automaten, wenn die Komponenten für sich genommen die gleiche Ausdrucksstärke besitzen, also die regulären Sprachen charakterisieren. Für PCRA-Systeme mit Zweiwegekomponenten werden als untere Schranke die Sprachklassen der Zweiwegemehrkopfautomaten im deterministischen und im nichtdeterministischen Fall gezeigt, welche wiederum den bekannten Komplexitätsklassen L (deterministisch logarithmischer Platz) und NL (nichtdeterministisch logarithmischer Platz) entsprechen. Als obere Schranke wird die Klasse der kontextsensitiven Sprachen gezeigt. Außerdem werden Erweiterungen von Restart-Automaten betrachtet (nonforgetting-Eigenschaft, shrinking-Eigenschaft), welche bei einzelnen Komponenten eine Erhöhung der Berechnungsstärke bewirken, in Systemen jedoch deren Stärke nicht erhöhen. Die von PCRA-Systemen charakterisierten Sprachklassen sind unter diversen Sprachoperationen abgeschlossen und einige Sprachklassen sind sogar abstrakte Sprachfamilien (sogenannte AFL's). Abschließend werden für PCRA-Systeme spezifische Probleme auf ihre Entscheidbarkeit hin untersucht. Es wird gezeigt, dass Leerheit, Universalität, Inklusion, Gleichheit und Endlichkeit bereits für Systeme mit zwei Restart-Automaten des schwächsten Typs nicht semientscheidbar sind. Für das Wortproblem wird gezeigt, dass es im deterministischen Fall in quadratischer Zeit und im nichtdeterministischen Fall in exponentieller Zeit entscheidbar ist.

Comparing Entire Prototypes at Semigroup Homomorphisms and Specifically at Regular Languages Substitutions

The following statements are proven: A correspondence of a semigroup in another one is a homomorphism if and only if when the entire prototype of the product of images contains (always) the product of their entire prototypes. The Kleene closure of the maximal rewriting of a regular language at a regular language substitution contains in the maximal rewriting of the Kleene closure of the initial regular language at the same substitution. Let the image of the maximal rewriting of a regular language at a regular language substitution covers the entire given regular language. Then the image of any word from the maximal rewriting of the Kleene closure of the initial regular language covers by the image of a set of some words from the Kleene closure of the maximal rewriting of this given regular language everything at the same given regular language substitution. The purposefulness of the ¯rst statement is substantiated philosophically and epistemologically connected with the spirit of previous mathematical results of the author. A corollary of its is indicated about the membership problem at a regular substitution.

Defending the patch : a labour geography analysis of unions’ construction of and responses to the problem of declining union membership amongst youth

If the trade union movement is to remain an influential force in the industrial, economic and socio/political arenas of industrialised nations it is vital that its recruitment of young members improve dramatically. Australian union membership levels have declined markedly over the last three decades and youth union membership levels have decreased more than any age group. Currently around 10% of young workers aged between 16-24 years are members of unions in Australia compared to 26% of workers aged 45-58 (Oliver, 2008). This decline has occurred throughout the union movement, in all states and in almost all industries and occupations. This research, which consists of interviews with union organisers and union officials, draws on perspectives from the labour geography literature to explore how union personnel located in various places, spaces and scales construct the issue of declining youth union membership. It explores the scale of connections within the labour movement and the extent to which these connections are leveraged to address the problem of youth union membership decline. To offer the reader a sense of context and perspective, the thesis firstly outlines the historical development of the union movement. It also reviews the literature on youth membership decline. Labour geography offers a rich and apposite analytical tool for investigation of this area. The notion of ‘scale’ as a dynamic, interactive, constructed and reconstructed entity (Ellem, 2006) is an appropriate lens for viewing youth-union membership issues. In this non-linear view, scale is a relational element which interplays with space, place and the environment (Howett, in Marston, 2000) rather than being ‘sequential’ and hierarchical. Importantly, the thesis investigates the notion of unions as ‘spaces of dependence’ (Cox, 1998a, p.2), organisations whose space is centred upon realising essential interests. It also considers the quality of unions’ interactions with others – their ‘spaces of engagement‘(Cox, 1998a, p.2), and the impact that this has upon their ability to recruit youth. The findings reveal that most respondents across the spectrum of the union movement attribute the decline in youth membership levels to factors external to the movement itself, such as changes to industrial relations legislation and the impact of globalisation on employment markets. However, participants also attribute responsibility for declining membership levels to the union movement itself, citing factors such as a lack of resourcing and a need to change unions’ perceived identity and methods of operation. The research further determined that networks of connections across the union movement are tenuous and, to date, are not being fully utilised to assist unions to overcome the youth recruitment dilemma. The study concludes that potential connections between unions are hampered by poor resourcing, workload issues and some deeply entrenched attitudes related to unions ‘defending (and maintaining) their patch’.

Fuzzy Membership Functions in a Fuzzy Decision Making Problem

Authors analyses questions of the subjective uncertainty and inexactness situations in the moment of using expert information and another questions which are connected with expert information uncertainty by fuzzy sets with rough membership functions in this article. You can find information about integral problems of individual expert marks and about connection among total marks “degree of inexactness” with sensibility of measurement scale. A lot of different situation which are connected with distribution of the function accessory significance and orientation of the concrete take to task decision making are analyses here.

Online professional communities : understanding the effects of membership on teacher practice

Online communities offer teachers a forum to discuss ideas, seek support, engage in professional discussions and network with a wider peer group. The popularity of online communities for teachers is self-evident by the quantity that has emerged in recent years and they present as opportunities to engage in continued pedagogical growth. The study presented in this paper has focused on the electronic discussions of three online communities for teachers, two Australian-based communities and one UK-based community. The aim was to analyse the content of the messages, via content analysis using the Practical Inquiry Model (Garrison, Anderson & Archer, 2001) in an attempt to determine if membership had an impact pedagogy. This study will present findings that support the conclusion that membership to online communities provides genuine opportunities for continued pedagogical growth for teachers. It will also show that they are being used as a problem solving resource, provide opportunities for professional discourse and professional support.

Approximate Membership Localization within a Web-Based Join Framework

In this paper, we propose a search-based approach to join two tables in the absence of clean join attributes. Non-structured documents from the web are used to express the correlations between a given query and a reference list. To implement this approach, a major challenge we meet is how to efficiently determine the number of times and the locations of each clean reference from the reference list that is approximately mentioned in the retrieved documents. We formalize the Approximate Membership Localization (AML) problem and propose an efficient partial pruning algorithm to solve it. A study using real-word data sets demonstrates the effectiveness of our search-based approach, and the efficiency of our AML algorithm.

Declining youth membership : the views of union officials

Across the industrialized west there has been a sharp decline in union membership (Frege and Kelly2003, Peetz 2002). Even more alarming are the lower unionization rates of young people and the steeper decline in these rates compared to older workers (Serrano and Waddington 2000). At the same time increasing numbers of young people still at school are participating in the labour market. There have been a number of explorations internationally of young people's union membership, but most either track membership decline over time, comparing adult and youth union density (Blanden and Machin 2003, Bryson et al. 2005, Haynes, Vowles and Boxall 2005, Canny 2002, OECD 2006), explore the general experience of young people in the labour market (for example, Lizen, Bolton and Pole 1999) or examine young people's view of unions (for example, Bulbeck 2008). This chapter however takes a different approach, exploring union officials' constructions of 'the problem' of low union density amongst youth. While the data in this study was obtained from Australia, the Australian context has strong similarities with those in other industrialized economies, not least because globalization has meant the spread of neo-liberal industrial relations (IR) policies and structures. Assuming that unions have choices open to them as to how they recruit and retain young people, it is important to analyse officials' construction of 'the problem', as this affects union strategizing and action.

Ageing Australian unions and the ‘youth problem’

Trade union membership, both in aggregate numbers and in density, has declined in the majority of advanced economies globally over recent decades (Blanchflower, 2007). In Australia, the decline in the 1990s was somewhat more precipitate than in most countries (Peetz, 1998). As discussed in Chapter 1, reasons for the decline are multifactorial, including a more hostile environment to unionism created by employers and the state, difficulties ·with workplace union organisation, and structural change in the economy (Bryson and Gomez, 2005; Bryson et a!., 2011; Ebbinghaus et al., 2011; Payne, 1989; Waddington and Kerr, 2002; Waddington and Whitson, 1997). Our purpose in this chapter is to look beyond aggregate Australian union density data, to examine how age relates to membership decline, and how different age groups, particularly younger workers, are located in the story of union decline. The practical implications of this research are that understanding how unions relate to workers of different age groups, and to workers of different genders amongst those age groups, may lead to improved recruitment and better union organisation.

Membership models and the design of authentication protocols for MANETs

Authentication protocols are very much essential for secure communication in mobile ad hoc networks (MANETs). A number of authentication protocols for MANETs have been proposed in the literature which provide the basic authentication service while trying to optimize their performance and resource consumption parameters. A problem with most of these protocols is that the underlying networking environment on which they are applicable have been left unspecified. As a result, lack of specifications about the networking environments applicable to an authentication protocol for MANETs can mislead about the performance and the applicability of the protocol. In this paper, we first characterize networking environment for a MANET as its 'Membership Model' which is defined as a set of specifications related to the 'Membership Granting Server' (MGS) and the 'Membership Set Pattern' (MSP) of the MANET. We then identify various types of possible membership models for a MANET. In order to illustrate that while designing an authentication protocol for a MANET, it is very much necessary to consider the underlying membership model of the MANET, we study a set of six representative authentication protocols, and analyze their applicability for the membership models as enumerated in this paper. The analysis shows that the same protocol may not perform equally well in all membership models. In addition, there may be membership models which are important from the point of view of users, but for which no authentication protocol is available.