In this paper, we consider first-order logic over unary functions and study the complexity of the evaluation problem for conjunctive queries described by such kind of formulas. A natural notion of ...query acyclicity for this language is introduced and we study the complexity of a large number of variants or generalizations of acyclic query problems in that context (Boolean or not Boolean, with or without inequalities, comparisons, etc...). Our main results show that all those problems are \textit{fixed-parameter linear} i.e. they can be evaluated in time \(f(|Q|).|\textbf{db}|.|Q(\textbf{db})|\) where \(|Q|\) is the size of the query \(Q\), \(|\textbf{db}|\) the database size, \(|Q(\textbf{db})|\) is the size of the output and \(f\) is some function whose value depends on the specific variant of the query problem (in some cases, \(f\) is the identity function). Our results have two kinds of consequences. First, they can be easily translated in the relational (i.e., classical) setting. Previously known bounds for some query problems are improved and new tractable cases are then exhibited. Among others, as an immediate corollary, we improve a result of \~\cite{PapadimitriouY-99} by showing that any (relational) acyclic conjunctive query with inequalities can be evaluated in time \(f(|Q|).|\textbf{db}|.|Q(\textbf{db})|\). A second consequence of our method is that it provides a very natural descriptive approach to the complexity of well-known algorithmic problems. A number of examples (such as acyclic subgraph problems, multidimensional matching, etc...) are considered for which new insights of their complexity are given.
A bounded degree structure is either a relational structure all of whose relations are of bounded degree or a functional structure involving bijective functions only. In this paper, we revisit the ...complexity of the evaluation problem of not necessarily Boolean first-order queries over structures of bounded degree. Query evaluation is considered here as a dynamical process. We prove that any query on bounded degree structures is \(\constantdelaylin\), i.e., can be computed by an algorithm that has two separate parts: it has a precomputation step of linear time in the size of the structure and then, it outputs all tuples one by one with a constant (i.e. depending on the size of the formula only) delay between each. Seen as a global process, this implies that queries on bounded structures can be evaluated in total time \(O(f(|\phi|).(|\calS|+|\phi(\calS)|))\) and space \(O(f(|\phi|).|\calS|)\) where \(\calS\) is the structure, \(\phi\) is the formula, \(\phi(\calS)\) is the result of the query and \(f\) is some function. Among other things, our results generalize a result of \cite{Seese-96} on the data complexity of the model-checking problem for bounded degree structures. Besides, the originality of our approach compared to that \cite{Seese-96} and comparable results is that it does not rely on the Hanf's model-theoretic technic (see \cite{Hanf-65}) and is completely effective.
A first-order sentence of a relational type
L
is
true almost everywhere if the proportion of its models among the structures of type
L
and cardinality
m tends to 1 when
m tends to ∞. It is shown that
...Th(
L
)
, the set of sentences
(of type
L
)
true almost everywhere, is
complete in PSPACE. Further, various upper and lower bounds of the complexity of this theory are obtained. For example, if the arity of the relation symbols of
L
is
d ⩾ 2 and if
Pr Th(
L
)
is the set of prenex sentences of
Th(
L
)
, then
Pr Th(
L
)
∈
DSPACE((
n
/
log
n
)
d
)
and
Pr Th(
L
)
∉
NTIME
(
o
(
n
/
log
n
)
d
)
.
If
R is a binary relation symbol and
L
=
{
R
}
,
(
Th
(
L
)
is the theory of almost all graphs), then
Pr Th
(
L
)
∉
NSPACE
(
o
(
n
/
log
n
)
)
.
These results are optimal modulo open problems in complexity such as NTIME(
T)? DSPACE(
T) and NSPACE(
S) = ? DSPACE(
S
2).
In the surroundings of five industrial plants, noise immissions (industrial noise and non-industrial noise) were measured and residents asked by a questionnaire about the effects (annoyance and ...reactions) caused by industrial noise. The questionnaires of a total of 1498 (58%) residents could be analyzed. The Leq for the industrial noise ranges from 37 to 68 dB(A) in the daytime and from 37 to 59 dB(A) in the nighttime. Ten to 20% of the residents are already strongly annoyed at industrial noise Leq levels of 50 dB(A). The sensitivity to noise is higher in the evening and at night. Residents are disturbed mainly during their rest and recreation and often react by closing the windows. Limits for noise immissions caused by industrial plants in residential areas are proposed (Switzerland).
PDF
