Читать книгу Declarative Logic Programming - Michael Kifer - Страница 11
Оглавление1.8 Current Systems and Comparison
This section describes and compares four current systems that implement Datalog: XSB, LogicBlox, Datomic, and Flora-2/Ergo. We show how a selection of Datalog rules and queries are written for each system, and report on experiments that illustrate their performance.
These systems all implement Datalog (or a superset). However, the observed performance of each system is unique. They show asymptotically different behavior due to fundamental factors, including their choices for evaluation strategies, selection of underlying data structures, and data indexing. Even when these factors are the same, there are differences in performance due to implementation details, such as the choice of implementation language.
1.8.1 Preliminaries: Data and Queries
For the illustration of rules and queries, we use the Mathematics Genealogy data [MathGen 2000] that contains basic facts about people, dissertations, and advisor relationships between people and dissertations. We assume the following EDB predicates, which are slightly different from those in the introductory example. In particular, an advisor ID (AID) is connected to a dissertation ID (DID), and a dissertation has a candidate (CID) who wrote it.
The data sets contains 198,962 people, 202,505 dissertations, and 211,107 facts of the advised predicate. In each of the systems, we answer the following five queries to illustrate the performance.
1. Who are the grand-advisors of David Scott Warren?
2. Which candidates got their degrees from the same university as their advisor?
3. Which candidates worked in a different area than at least one of their advisors?
4. Who are the academic ancestors of David Scott Warren?
5. How many academic ancestors does David Scott Warren have?
These queries make use of simple joins, recursive rules, and aggregations that facilitate assessing the performance of the systems in various aspects. In the next subsections, we introduce four systems and how these queries are expressed in each.
1.8.2 XSB
XSB [Sagonas et al. 1994] is a top-down implementation of Prolog extended with tabled resolution as described in Section 1.5.2.1. XSB allows fine-grained control over which tabling strategy and indexes to use for each predicate, and the choices for tabling and indexing affect asymptotic behavior. Consider Query 1, which is written in XSB as follows:
Here the rule defining enumallq1/0 uses a Prolog idiom of a fail-loop, which has the effect of generating all results in the most efficient way.
By default, XSB indexes each predicate on its first argument. However that may not be the most effective choice. For example, in the rule defining q1, after the first subgoal binds D, top-down evaluation will need to obtain values for the first argument of adv given a binding for the second argument. The following directive creates an index on the second argument:
To illustrate tabling, consider Query 4:
For this query, one can show that there can be repeated subgoals for predicate anc. The following tabling directive will avoid reevaluating such repeated subgoals and, therefore, avoid an infinite loop, which would affect an ordinary Prolog system:
Rules for Queries 2 and 3 can be written in XSB as follows:
Query 5 can be implemented using the aggregate construct findall in XSB, which returns all answers to a query as a list via the last argument:
The same query can also be implemented using the table aggregation construct in XSB as follows:
The special tabling directive in the first line works as follows: whenever an answer acc for q4 is generated, XSB calls cnt(acc, _, NewAcc), removes acc from the table, and adds NewAcc. For the first answer found, the first argument in the call to cnt would be 0, as indicated by the tabling directive. So q5_2 returns the number of facts found for q4.
1.8.3 LogicBlox
LogicBlox [Aref et al. 2015] is a commercial system unifying the programming model for enterprise software development that combines transactions with analytics by using a flavor of Datalog called LogiQL. LogiQL is a strongly typed, extended form of Datalog that allows coding of entire enterprise applications, including business logic, workflows, user interfaces, statistical modeling, and optimization tasks. LogicBlox evaluates LogiQL rules in a bottom-up fashion.
In terms of the language, in addition to pure Datalog, LogiQL has functional predicates that map keys to values, and various aggregation operators. In LogiQL, the arguments of each EDB predicate need to be typed. For our queries, these types can be specified as follows:
In the specification above, person is a functional predicate (shown by the bracket notation), mapping person IDs to names. Using these specifications, Query 1 can be answered with the following rules:
Apart from the use of the functional predicates shown above, Queries 2–4 can be implemented similarly to XSB:
Query 5 can be specified using the aggregation construct in LogiQL as follows.
1.8.4 Datomic
Datomic [Anderson et al. 2016] is a distributed NoSQL database, which uses Datalog as its rule and query language. Since the system is closed-source and no academic paper has been published by the implementation team, one can only rely on the documentation for its details. Datalog evaluation in Datomic is performed bottomup, and indexing directives can be specified.
The syntax of a Datalog rule in Datomic is quite distinct from that used in the logic programming literature. It is akin to the RDF query language SPARQL [Prud’hommeaux et al. 2008]. Datomic operates on object-like predicates. For example, for our EDB predicate dissertation, rather than representing it as a predicate with arguments, each dissertation is considered an object with an identifier and arguments that can be accessed as fields. Therefore, all EDB predicates are represented by binary predicates written in infix form, and they use square brackets. For example, a dissertation’s candidate ID can be thought of as a predicate :dissertation/cid whose form in the body is [?d :dissertation/cid ?c], where variables are preceded by ?. In contrast, IDB predicates are written in prefix notation and use round parentheses, as seen in the rules below.
A rule is written as a list whose first element is the conclusion of the rule and the rest of the elements in the list are the body. For example, a new predicate author whose arguments are the dissertation ID and the candidate ID can be defined via the following rule:
Once a new predicate is defined, it can be used in the body of a rule to define more predicates, as shown in the definition of the advisor relationship below.
Queries use a similar syntax, where a list of variables appears after the keyword :find and the body is given after the :where keyword. Therefore, Query 1 can be defined as follows (the three dots after the arguments to :find will return a collection):
In this fashion, Queries 2–4 can be written in Datomic as follows:
Aggregates are handled in Datomic by applying aggregate functions to variables. For instance, Query 5 is written as follows:
1.8.5 Flora-2 and Ergo
Flora-2 [Kifer 2015, Yang et al. 2003] is a knowledge-representation and reasoning system that supports Datalog as a subset of its various reasoning paradigms, such as the ones described in Section 1.4. The bouquet of these extensions is unique to Flora-2 and many were pioneered by that system. The list of these advanced features includes well-founded negation (Section 1.4.1), aggregation (Section 1.4.3), object-oriented extensions based on F-logic and defeasible reasoning (Section 1.4.6), HiLog (Section 1.4.7), logical updates (Section 1.4.8), certain styles of functional programming, explicit logical quantifiers, and more. Flora-2 uses XSB as an underlying inference engine. In particular, it relies on XSB’s top-down evaluation strategy, but also brings in new elements such as dynamic reordering of subgoals. Ergo is a commercial variant of Flora-2 offered by Coherent Knowledge, LLC. It includes additional language extensions and optimizations as well as development tools and connectors to various external data sources (for example, SPARQL endpoints, tabular data and JSON). Our running example of the fragment of the Genealogy Database, expressed in Flora-2, is shown below. To illustrate the object-oriented features of this system, we modify the database schema to use frame-based rather than predicate-based representation. (If we used predicate representation then Flora-2 rules would be similar to XSB’s with minor syntactic differences.)
These declarations specify the types of the attributes for classes Dissertation and Person (=> means “has type”). In this application, these declarations are not required, but they make the schema of the database explicit and easier to grasp.
Since the object-oriented schema above is quite different from the original relational schema in Section 1.8.1, the next pair of rules specifies the “bridge” between the two schemes:
We recall that the symbol -> means “has value” and thus the first rule above says that, given a tuple 〈d, c, t, g, u, y, ar〉 in table dissertation and a tuple 〈adv, d〉 in advised, one can derive that d is an object in class Dissertation such that: its attribute cid has value c, the attribute advisor has a value adv, title has value t, and so on. Note that an attribute can have multiple values and so, if dissertation d was advised by several advisors, the advisor attribute for d will be multi-valued.
The next batch of statements contains the actual queries for our running example. It starts with three auxiliary rules that define additional view-methods for classes Dissertation and Person. The first rule, for example, says that if there is a Dissertation-object (denoted by a name-less variable ?) that has a candidate with Id ?P (i.e., the attribute cid has value ?P) and an advisor ?A then that dissertation’s advisor is also an advisor for ?P. The next two rules recursively define the method ancAdvisor in class Person.
The last rule is interesting because it appears in the form of a fact, but is really a shorthand for a rule like
but count{…} is an evaluable aggregate function that can be placed directly as an argument to q5. This last query provides a glimpse of how logical and functional styles can be mixed in Flora-2.
1.8.6 Experiments
In this section, we report experimental results on two of the four modern systems we have discussed: XSB and LogicBlox. The systems that we have chosen for experiments are representative of two schools of evaluation, top-down and bottom-up. Each school has its own challenges, and we will illustrate those challenges via experiments, and show techniques to tackle them.
An issue pertinent to both schools of evaluation is indexing. During an evaluation, a system needs to retrieve facts for a predicate given some bound arguments. XSB, by default, generates an index on the first argument of each predicate. However, as we will illustrate, that index may not be enough. In such cases, XSB allows the user to specify additional indexing directives. LogicBlox automatically generates relevant indexes, and the user cannot affect the system’s choices. We will illustrate the importance of indexing in XSB via experiments.
An issue pertinent only to top-down evaluation is repeated calls to subgoals, as described in Section 1.5.2.1. We will show how the user specifies tabling directives, and the difference in query evaluation time with and without tabling in XSB.
An issue pertinent only to bottom-up evaluation is that, in its basic form, it does not take the particular query into account. Many methods exist to transform the rules so that the query is taken into account, most notably the Magic Sets transformation [Bancilhon et al. 1986]. We will use demand transformation instead [Tekle and Liu 2010], since it is a simpler method and its space complexity can be exponentially less (in the number of arguments of predicates) than Magic Sets. We will illustrate the effect of demand transformation via experiments in the LogicBlox system.
Another impact on performance for a system is the inclusion of database features such as atomicity and durability. These require various mechanisms, including locks and writes to disk, which impact performance negatively. LogicBlox has various such features, but XSB does not, and the experiment results should be evaluated in this light as well.
Optimization of Datalog queries by transforming rules and queries has been widely studied. These include specialization and recursion conversion [Tekle et al. 2008]; the latter is illustrated for relevant queries for both systems.
We now show our experiments for each query. We performed the experiments on a 2.8 GHz Intel Core i5 with 8 GB RAM, using XSB 3.7 and LogicBlox 4.3.10. We performed each experiment 10 times and took the average times of the runs.
Loading Input Data. Input data load times are important to the viability of a system, but it is a task that need be performed only once, and does not change with respect to a given query. For this reason, we separate loading input data from query answering in our experiments. In order to load the input data into XSB, we run the following query:
and in order to load the input data into LogicBlox, we install the definitions of the input predicates, and then run import scripts via its TDX mechanism.
Setting up the environment and loading of input data as described above takes 3.91 s in XSB, and 14.9 s in LogicBlox.
Query 1.1 The first query asks for the grand-advisors of David Scott Warren.
XSB. Recall the rules and query in XSB:
Note that a call to q1 will be made with its argument as a free variable, and therefore the following calls will be made in the body of the rule for q1: (i) a call to person with the second argument bound due to the first subgoal, since that argument is a constant; (ii) a call to adv with the second argument bound due to the second subgoal, since D will be bound by the first subgoal; (iii) another call to adv with the second argument bound due to the third subgoal, since X will be bound by the second subgoal; and (iv) another call to person with the first argument bound due to the final subgoal, since Y will be bound by the third subgoal.
The rules and query may be analyzed for each relevant predicate to find binding patterns for predicates, as shown above. For optimal performance, it is critical to have indexes corresponding to each binding pattern for the IDB predicates. As noted, XSB provides indexes on the first argument by default. For each non-default index, we write the indexing directives as follows:
The query is answered in 261 ms without the index, and in 238 ms with the index, 9.6% faster. The effect is not so dramatic, since only one subgoal binds the second argument of person. We will see more dramatic effects in other queries.
LogicBlox. Recall that in LogicBlox, we do not have control over the indexing mechanism. Running the first query takes 1400 ms. However, LogicBlox does not take the query into account, and therefore will infer facts for the adv predicate for every possible pair, but the only relevant ones are David Scott Warren’s advisors, and their advisors in turn. To avoid the extra computation, we can perform demand transformation, which yields the following rules:
The demand predicate stores David Scott Warren, and his advisors, so that the new rules only infer facts of the adv predicate that are relevant to our query. This version takes 944 ms, 33% faster than the original rules. This example illustrates that demand transformation is important, even for a small query.
Query 1.2 This query finds the people who got their degrees from the same university as their advisor.
XSB. Running the rules and query as given in XSB results in quite a long execution time, 49.2 min. However, if we analyze the rules for binding patterns, and therefore add the following indexing directive, which indexes the dissertation predicate on its first, second, and the combination of second and fifth arguments:
the running time is reduced to 511 ms, almost 5800 times faster than the original! The effect here is more dramatic than in the previous query because of repeated calls to dissertation with a different binding pattern than only the first argument being bound.
LogicBlox. The original rules and query take 2.14 s to run. Performing demand transformation in the original rules does not result in a new program, since in this order of subgoals, there is no IDB predicate with bound arguments in a left-to-right evaluation. However, we can change the order of subgoals to obtain the following rule for q2, to effect a different demand for adv without changing the semantics or performance of the given rule.
The demand for adv can be defined as
We can see that this join is quite expensive, joining every pair of people and filtering with respect to their universities. Therefore, demand transformation results in slower performance. Our experiments confirm this behavior, since this set of rules takes 77.9 s, 36 times slower.
Query 1.3 This query finds the people who worked in a different area than their advisors.
XSB. This query is similar in essence to Query 2, and without indexing the query takes 47.4 minutes to run. With the correct indexing directives, it takes 325 ms, 8750 times faster.
LogicBlox. Since Queries 2 and 3 are very similar, we again get the best performance with the initial rules, since the demand transformation after subgoal reordering results in extra work. The original rules and query take 1.74 s to run. If the adv predicate is moved to a later position and demand transformation is applied, the resulting rules and query take 74.4 s, 43 times slower.
Queries 1.4/5 These queries find the academic ancestors of David Scott Warren, and their count, respectively. The count is only a small overhead for each system, therefore we have grouped the queries together.
XSB. For all the prior queries, it can be shown that, based on the rules and the nature of the data (the genealogy information does not contain cycles), this query would terminate even without tabling. However, even in the absence of repeated subqueries, recursion could lead to exponential time complexity. As we discussed, the solution to this problem in top-down systems is tabling. To enable tabling, we write the following directive with the rules for ancestry:
Recall that our query will generate an initial subquery for anc with the second argument bound (to David Scott Warren). However, adding the tabling directive does not seem to help, since for every person, this set of rules will generate a query: Is this person an ancestor of David Scott Warren?
This strategy results in a lot of unnecessary computation, and XSB quickly runs out of memory; tabling did not help us get the answers here. Can we, however, reduce the number of queries, and therefore evaluate the query efficiently? The answer was already provided in Section 1.5.2.1, where we showed that left-recursive transitive closure is much more efficient than right-recursive, if tabling is used. Indeed, if we reorder the goals in the second rule as follows:
we will only ever ask: Who is an ancestor of David Scott Warren? And, voilà, we get the answers quickly, in 3.19 s. This example shows that tabling and subgoal ordering are essential to optimizing queries for top-down evaluation. Getting the count for Query 5 only takes a marginal 0.2% longer. The performance can be further improved by indexing the tabled predicate adv on its second argument, since it is always called with the second argument bound, with the directive:
This change improves the runtime to 181 ms, 17 times faster than without the index.
Apart from indexing and reordering, we can change the recursion to obtain another left-recursive version of the rules above:
However, this version runs slower at 11.3 s, since it immediately creates a subquery with both arguments free (neither X nor Z are bound in the head), therefore it finds all possible ancestry pairs.
These experiments show that the correct choice of directives, of rule type, and goal ordering can drastically affect the performance of queries. As a final remark, note that in the evaluation of such recursive queries, tabling directives should always be provided to avoid infinite recursion or exponential time complexity. Without tabling, XSB fails to complete this query in a pre-defined amount of time (1 h).
LogicBlox. Since basic bottom-up evaluation computes the ancestry for every possible pair of people, it is extremely inefficient not to take the query into account. LogicBlox takes 79.1 s to get the answers to the query, in contrast to XSB answering the query in a fraction of a second.
The time complexity of the evaluation for this query in LogicBlox is quadratic (with a polylog factor) in the size of the genealogy graph. We can reduce that time to linear, and observe a benefit that brings the performance to acceptable levels, if we perform demand transformation after reordering the goals as we did for XSB. These changes yield the following rules:
After this transformation, the query takes only 1.14 s in LogicBlox, 70 times faster than the original rules. Adding the count for Query 5 results in a marginal increase of only 0.03%.
Summary. We have illustrated the behavior of the two systems for each of our queries. In particular, specifying indexes and tabling for XSB, and demand transformation for LogicBlox have been shown to dramatically improve the running time. Note that these improvements are not constant-time, but rather asymptotic speedups. We have also shown that even when the systems theoretically should have similar asymptotic behavior, differences in implementation can result in significant variations in actual running times.
1.9 Conclusions
Datalog was a product of converging trends in databases, logic programming, and artificial intelligence with the goal of being able to support more advanced (than conventional databases) reasoning while being amenable to optimization and alternative evaluation strategies needed for larger data sets. After the initial surge in enthusiasm, the field entered a period of reduced interest and activity for a number of reasons. Among the most important ones was the blow-back due to “over-promise.” In the 1980s and early 1990s, the technology was simply not ready for production deployment, and it is not coincidental that this period of decline had a big overlap with the so-called “AI Winter.” Back then, the necessary theory and technology was yet to be developed and the pace was not keeping up with the expectations. On top of it, computers were severely underpowered compared to today and simply could not support the computational demands of either AI or logic programming. Another important factor was that the chosen application-area target—databases—was not optimal: DBMSs are demanding to implement, the query language is just one component of a DBMS out of many, and special-purpose solutions—albeit clunky—were available for applications requiring recursion (such as a bill of materials).
By the late 1990s, however, the situation started to change: computers became hundreds of times more powerful and the technology finally started to catch up with the needs. Importantly, that technology came both from the “ivory tower”—academia—as well as from application-driven research and practitioners. Moreover, people discovered that the application base for Datalog is much broader than just data management. Datalog has shown advantages in areas that involve complex, mutually recursive reasoning (program analysis) and benefits for distributed, asynchronous evaluation (declarative networking). Datalog was likewise recognized as an important reasoning tool for the Semantic Web as well as a design and prototyping tool. It is often used as an intermediate form that is easy to map to because it supports analysis and optimization, and can be translated to a variety of representations and evaluation techniques. Finally, Datalog simply took its place in the diverse family of programming languages.
The original idea about Datalog as a query language for DBMS turned out to be not that outlandish either: companies such as LogicBlox and Datomic have built DBMSs based on Datalog, and they include schemas, concurrency control and most of the usual accouterments of database systems. It just took more time.
In summary, do not expect Datalog (or any other language) to replace other technologies going forward, but it is clear that it has established itself as a viable option in commercially relevant applications. One should expect that there will be additional areas where Datalog will show advantages, such as data analytics.
Acknowledgments
The authors wish to thank Jeff Ullman, Raghu Ramakrishnan, Molham Aref, Moshe Vardi, Joe Hellerstein, and Serge Abiteboul for their comments on the ups and downs of Datalog. TJ Green helped early on with the structure of this chapter. Georg Gottlob and Bob Kowalski read this material and shared with us invaluable comments and critique, as did several anonymous reviewers. Special thanks is due Annie Liu for, without her gentle but persistent push and thoughtful comments, this chapter would not have been completed.
References
S. Abiteboul and C. Beeri. Oct. 1995. The power of languages for the manipulation of complex values. The VLDB Journal, 4(4):727–794. DOI: 10.1007/BF01354881. 34
S. Abiteboul and S. Grumbach. Sept. 1987. COL: A logic-based language for complex objects. In Advanced in Database Programming Languages: Proc. of the Workshop on Database Programming Languages, pp. 253–276. DOI: 10.1016/0022-0000(93)90021-N. 33
S. Abiteboul and P. C. Kanellakis. May/Jun. 1989. Object identity as a query language primitive. In ACM SIGMOD Conference on Management of Data, pp. 159–173. DOI: 0.1145/66926.66941. 33
S. Abiteboul and V. Vianu. 1990. Procedural languages for database queries and updates. Journal of Computer and System Sciences, 41(2):181–229. DOI: 10.1016/0022-0000(90)90036-K. 43
S. Abiteboul, R. Hull, and V. Vianu. 1995. Foundations of Databases. Addison-Wesley. 76
S. Abiteboul, P. Buneman, and D. Suciu. 2000. Data on the Web: From Relations to Semistructured Data and XML. Morgan Kaufmann, San Francisco, CA. 34, 36
S. Abiteboul, Z. Abrams, S. Haar, and T. Milo. 2005. Diagnosis of asynchronous discrete event systems: Datalog to the rescue! In Proc. of the Twenty-fourth ACM SIGMOD-SIGACTSIGART Symposium on Principles of Database Systems, PODS ’05, pp. 358–367. ACM. DOI: 10.1145/1065167.1065214. 82
S. Abiteboul, M. Bienvenu, A. Galland, and E. Antoine. 2011. A rule-based language for web data management. In Proc. of the Thirtieth ACM SIGMOD-SIGACT-SIGART Symposium on Principles of Database Systems, PODS ’11, pp. 293–304. ACM. DOI: 10.1145/1989284.1989320. 84
F. Afrati and S. S. Cosmadakis. 1989. Expressiveness of restricted recursive queries. In Proc. of the Twenty-first Annual ACM Symposium on Theory of Computing, STOC ’89, pp. 113–126. ACM. DOI: 10.1145/73007.73018. 77
F. Afrati, C. H. Papadimitriou, G. Papageorgiou, A. Roussou, Y. Sagiv, and J. D. Ullman. 1986. Convergence of sideways query evaluation. In ACM Symposium on Principles of Database Systems, pp. 24–30. DOI: 10.1145/6012.15400.. 42
R. Agrawal, R. Cochrane, and B. Lindsay. 1991. On maintaining priorities in a production rule system. In International Conference on Very Large Data Bases, pp. 479–487. Morgan Kaufmann, San Francisco, CA. 42
A. V. Aho and J. D. Ullman. 1979. Universality of data retrieval languages. In Proc. of the 6th ACM SIGACT-SIGPLAN Symposium on Principles of Programming Languages, POPL ’79, pp. 110–119. ACM. DOI: 10.1145/567752.567763. 13, 50, 77
H. Aït-Kaci and R. Nasr. 1986. LOGIN: A logic programming language with builtin inheritance. Journal of Logic Programming, 3: 185–215. DOI: 10.1016/0743-1066(86)90013-0. 33, 34
H. Aït-Kaci and A. Podelski. Aug. 1993. Towards a meaning of LIFE. Journal of Logic Programming, 16: 195–234. DOI: 10.1016/0743-1066(93)90043-G. 33, 34
J. J. Alferes, A. Brogi, J. A. Leite, and L. M. Pereira. Sept. 2002. Evolving logic programs. In Proc. of Logics in Artificial Intelligence: 8th European Conference, pp. 50–62. Springer, Berlin, Heidelberg. DOI: 10.1007/3-540-45757-7_5. 43
M. Alviano, N. Leone, M. Manna, G. Terracina, and P. Veltri. 2012. Magic-sets for Datalog with existential quantifiers. In Proc. of the Second International Workshop on Datalog in Academia and Industry: Datalog 2.0, pp. 31–43. Springer, Berlin, Heidelberg. DOI: 10.1007/978-3-642-32925-8_5. 28
J. Anderson, M. Gaare, J. Holguín, N. Bailey, and T. Pratley. 2016. The Datomic database. In Professional Clojure, pp. 169–215. Wiley Online Library. 88
R. Angles and C. Gutierrez. 2008. The expressive power of SPARQL. In Proc. of the 7th International Conference on The Semantic Web, ISWC ’08, pp. 114–129. Springer-Verlag, Berlin, Heidelberg. DOI: 10.1007/978-3-540-88564-1_8. 76
K. R. Apt, H. A. Blair, and A. Walker. 1988. Towards a theory of declarative knowledge. In J. Minker, editor, Foundations of Deductive Databases and Logic Programming, pp. 89–148. Morgan Kaufmann Publishers Inc., San Francisco, CA, USA. DOI: 10.1016/B978-0-934613-40-8.50006-3. 19
M. Aref, B. ten Cate, T. J. Green, B. Kimelfeld, D. Olteanu, E. Pasalic, T. L. Veldhuizen, and G. Washburn. 2015. Design and implementation of the LogicBlox system. In Proc. of the 2015 ACM SIGMOD International Conference on Management of Data, SIGMOD ’15, pp. 1371–1382. ACM. DOI: 10.1145/2723372.2742796. 28, 29, 87
F. Arni, K. Ong, S. Tsur, H. Wang, and C. Zaniolo. Jan. 2003. The deductive database system LDL++. Theory and Practice of Logic Programming, 3(1):61–94. DOI: 10.1017/S1471068402001515. 67
M. P. Ashley-Rollman, S. C. Goldstein, P. Lee, T. C. Mowry, and P. Pillai. Oct. 2007. Meld: A declarative approach to programming ensembles. In 2007 IEEE/RSJ International Conference on Intelligent Robots and Systems, pp. 2794–2800. DOI: 10.1109/IROS.2007.4399480. 83
F. Baader, D. Calvanese, D. L. McGuinness, D. Nardi, and P. F. Patel-Schneider, editors. 2003. The Description Logic Handbook: Theory, Implementation, and Applications. Cambridge University Press, New York. 64, 78
F. Bancilhon. Sept. 1978. On the completeness of query languages for relational data bases. In Proc. of the 7th Symposium on Mathematical Foundations of Computer Science, pp. 112–123. DOI: 10.1007/3-540-08921-7_60. 13
F. Bancilhon and S. N. Khoshafian. Apr. 1989. A calculus for complex objects. Journal of Computer and System Sciences, 38(2):326–340. DOI: 10.1016/0022-0000(89)90005-6. 34
F. Bancilhon and R. Ramakrishnan. 1986. An amateur’s introduction to recursive query processing strategies. In Proc. of the 1986 ACM SIGMOD International Conference on Management of Data, SIGMOD ’86, pp. 16–52. ACM. DOI: 10.1145/16894.16859. 48, 60, 61
F. Bancilhon, D. Maier, Y. Sagiv, and J. D. Ullman. 1986. Magic sets and other strange ways to implement logic programs. In ACM Symposium on Principles of Database Systems, pp. 1–15. DOI: 10.1145/6012.15399. 16, 50, 51, 93
R. Basseda and M. Kifer. June 2015a. State space planning using Transaction Logic. In International Symposium on Practical Aspects of Declarative Languages (PADL 2015), pp. 17–33. DOI: 10.1007/978-3-319-19686-2_2. 46
R. Basseda and M. Kifer. Aug. 2015b. Planning with regression analysis in Transaction Logic. In Web Reasoning and Rule Systems, 9th International Conference (RR 2015), pp. 45–60. DOI: 10.1007/978-3-319-22002-4_5. 46
R. Basseda, M. Kifer, and A. J. Bonner. Sept. 2014. Planning with Transaction Logic. In 8th International Conference on Web Reasoning and Rule Systems, (RR 2014), vol. 8741 of Lecture Notes in Computer Science, pp. 29–44. Springer. DOI: 10.1007/978-3-319-11113-1_3. 46
M. Y. Becker and P. Sewell. 2004. Cassandra: Distributed access control policies with tunable expressiveness. In Proc. of the Fifth IEEE International Workshop on Policies for Distributed Systems and Networks, POLICY ’04, pp. 159–168. IEEE Computer Society. DOI: 10.1109/POLICY.2004.1309162. 82
C. Beeri. 1989. Formal models for object-oriented databases. In International Conference on Deductive and Object-Oriented Databases, pp. 370–395. Elsevier Science Publishers. DOI: 10.1016/B978-0-444-88433-6.50030-7. 34
C. Beeri and R. Ramakrishnan. 1991. On the power of magic. Journal of Logic Programming, 10(3&4):255–299. DOI: 10.1016/0743-1066(91)90038-Q. 51
C. Beeri and M. Y. Vardi. 1981. The implication problem for data dependencies. In S. Even and O. Kariv, editors, Automata, Languages and Programming: Eighth Colloquium, pp. 73–85. Springer, Berlin, Heidelberg. DOI: 10.1007/3-540-10843-2_7. 26
C. Beeri, R. Nasr, and S. Tsur. 1988. Embedding ψ-terms in a horn-clause logic language. In Third International Conference on Data and Knowledge Bases: Improving Usability and Responsiveness, pp. 347–359. Morgan Kaufmann. DOI: 10.1016/B978-1-4832-1313-2.50033-0. 33
C. Beeri, S. Naqvi, O. Shmueli, and S. Tsur. Apr. 1991. Set constructors in a logic database language. Journal of Logic Programming, 10: 181–232. DOI: 10.1016/0743-1066(91)90036-O. 33
T. Berners-Lee, J. Handler, and O. Lassila. May 2001. The Semantic Web. Scientific American. 78
D. G. Bobrow. Apr. 1980. Artificial Intelligence: Special Issue on Non-Monotonic Logic, vol. 13 no. 1-2. Elsevier. 21
H. Boley and M. Kifer, July 2013a. RIF Basic logic dialect. W3C Recommendation. Available at: http://www.w3.org/TR/rif-bld/. 78
H. Boley and M. Kifer, July 2013b. RIF Framework for logic dialects. W3C Recommendation. Available at: http://www.w3.org/TR/rif-fld/. 78
A. J. Bonner and M. Kifer. June 1993. Transaction Logic programming. In International Conference on Logic Programming, pp. 257–282. MIT Press. 43, 45
A. J. Bonner and M. Kifer. Oct. 1994. An overview of Transaction Logic. Theoretical Computer Science, 133: 205–265. DOI: 10.1016/0304-3975(94)90190-2. 43, 45
A. J. Bonner and M. Kifer. Nov. 1995. Transaction Logic programming (or a logic of declarative and procedural knowledge). Technical Report CSRI-323, University of Toronto. Available at: http://www.cs.toronto.edu/~bonner/transaction-logic.html. 45
A. J. Bonner and M. Kifer. Sept. 1996. Concurrency and communication in Transaction Logic. In Joint International Conference and Symposium on Logic Programming, pp. 142–156. MIT Press. 45
A. J. Bonner and M. Kifer. 1998a. The state of change: A survey. In Freitag et al. [1998]. Springer. 39
A. J. Bonner and M. Kifer. 1998b. Results on reasoning about action in Transaction Logic. In Freitag et al. [1998]. Springer-Verlag. 46
A. J. Bonner, M. Kifer, and M. Consens. Aug./Sept. 1993. Database programming in Transaction Logic. In Proc. of the Fourth International Workshop on Database Programming Languages, pp. 309–337. DOI: 10.1007/978-1-4471-3564-7_18. 45
G. Brewka, J. Dix, and K. Konolige. 1997. Nonmonotonic Reasoning: An Overview, vol. 73 of CSLI Lecture Notes. CSLI Publications, Stanford, CA. 21
F. Bry. Oct. 1990. Query evaluation in recursive databases: Bottom-up and top-down reconciled. Data Knowledge Engineering, 5(4):289–312. DOI: 10.1016/B978-0-444-88433-6.50010-1. 61
M. Calautti, G. Gottlob, and A. Pieris. 2015. Chase termination for guarded existential rules. In Proc. of the 34th ACM Symposium on Principles of Database Systems, PODS 2015, pp. 91–103. DOI: 10.1145/2745754.2745773. 27
A. Calì, G. Gottlob, and A. Pieris. 2011. New expressive languages for ontological query answering. In Proc. of the Twenty-Fifth AAAI Conference on Artificial Intelligence, AAAI 2011, pp. 1541–1546. 25, 28
A. Calì, G. Gottlob, and M. Kifer. 2013. Taming the infinite chase: Query answering under expressive relational constraints. Journal of Artificial Intelligence Research, 48: 115–174. 26, 28
M. J. Carey, D. J. DeWitt, J. E. Richardson, and E. J. Shekita. 1986. Object and file management in the EXODUS extensible database system. In Proc. of the 12th International Conference on Very Large Data Bases, VLDB ’86, pp. 91–100. Morgan Kaufmann Publishers Inc., San Francisco, CA. 68
M. Carlsson et al. 2015. SICStus Prolog User’s Manual. RISE SICS AB, Kista, Sweden. http://sicstus.sics.se/sicstus/docs/latest4/pdf/sicstus.pdf. 33
S. Ceri and L. Tanca. 1987. Optimization of systems of algebraic equations for evaluating Datalog queries. In Proc. of the 13th International Conference on Very Large Data Bases, VLDB ’87, pp. 31–41. Morgan Kaufmann Publishers Inc., San Francisco, CA. 63
S. Ceri, G. Gottlob, and L. Lavazza. 1986. Translation and optimization of logic queries: The algebraic approach. In Proc. of the 12th International Conference on Very Large Data Bases, VLDB ’86, pp. 395–402. Morgan Kaufmann Publishers Inc., San Francisco, CA. 63
S. Ceri, G. Gottlob, and G. Wiederhold. Feb. 1989. Efficient database access from Prolog. IEEE Trans. on Software Engineering, 15(2):153–164. DOI: 10.1109/32.21742. 63
U. S. Chakravarthy, J. Grant, and J. Minker. June 1990. Logic-based approach to semantic query optimization. ACM Trans. on Database Systems, 15(2):162–207. DOI: 10.1145/78922.78924. 31
A. Chandra and D. Harel. Apr. 1985. Horn clause queries and generalizations. Journal of Logic Programming, 2(1):1–15. DOI: 10.1016/0743-1066(85)90002-0. 77
C. Chang. 1977. DEDUCE 2: Further investigations of deduction in relational data bases. In H. Gallaire and J. Minker, editors, Logic and Data Bases, pp. 201–236, Plenum Press, New York. DOI: 10.1007/978-1-4684-3384-5_8. 13, 63
S. Chaudhuri. 1998. An overview of query optimization in relational systems. In Proc. of the Seventeenth ACM SIGACT-SIGMOD-SIGART Symposium on Principles of Database Systems, pp. 34–43. ACM Press. 64
S. Chaudhuri and M. Y. Vardi. 1992. On the equivalence of recursive and nonrecursive datalog programs. In Proc. of the Eleventh ACM SIGACT-SIGMOD-SIGART Symposium on Principles of Database Systems, PODS ’92, pp. 55–66. ACM. DOI: 10.1006/jcss.1997.1452. 64
W. Chen and D. S. Warren. Mar. 1989. C-logic for complex objects. In ACM Symposium on Principles of Database Systems, pp. 369–378. ACM. DOI: 10.1145/73721.73757. 33
W. Chen and D. S. Warren. Jan. 1996. Tabled evaluation with delaying for general logic programs. JACM, 43(1):20–74. DOI: 10.1145/227595.227597. 21, 59, 71
W. Chen, M. Kifer, and D. S. Warren. June 1989a. HiLog as a platform for database programming languages (or why predicate calculus is not enough). In Proc. of the Second International Workshop on Database Programming Languages, pp. 315–329. 37
W. Chen, M. Kifer, and D. S. Warren. Oct. 1989b. HiLog: A first-order semantics for higher-order logic programming constructs. In North American Conference on Logic Programming, pp. 1090–1114. MIT Press, Cambridge, MA. 37
W. Chen, M. Kifer, and D. S. Warren. Feb. 1993. HiLog: A foundation for higher-order logic programming. Journal of Logic Programming, 15(3):187–230. DOI: 10.1016/0743-1066(93)90039-J. 37, 38
D. Chimenti, R. Gamboa, R. Krishnamurthy, S. Naqvi, S. Tsur, and C. Zaniolo. Mar. 1990. The LDL system prototype. IEEE Trans. on Knowledge and Data Engineering, 2(1):76–90. DOI: 10.1109/69.50907. 66
B. Chin, D. von Dincklage, V. Ercegovac, P. Hawkins, M. S. Miller, F. Och, C. Olston, and F. Pereira. 2015. Yedalog: Exploring knowledge at scale. In 1st Summit on Advances in Programming Languages (SNAPL 2015), pp. 63–78. 83
J. Chomicki. 1990. Polynomial time query processing in temporal deductive databases. In ACM Symposium on Principles of Database Systems, pp. 379–391. DOI: 10.1145/298514.298589. 41
K. L. Clark. 1978. Negation as failure. In H. Gallaire and J. Minker, editors, Logic and Data Bases, pp. 293-322, Plenum Press, New York. 18
Coherent Knowledge LLC, 2017. Ergo Suite. Available at: http://coherentknowledge.com/. 28, 34, 38
A. Colmerauer and P. Roussel. 1996. The birth of Prolog. In T. J. Bergin, Jr. and R. G. Gibson, Jr., editors, History of Programming Languages—II, pp. 331–367. ACM. DOI: 10.1145/154766.155362. 11
N. Conway, W. R. Marczak, P. Alvaro, J. M. Hellerstein, and D. Maier. 2012. Logic and lattices for distributed programming. In Proc. of the Third ACM Symposium on Cloud Computing, SoCC ’12, pp. 1:1–1:14. ACM. DOI: 10.1145/2391229.2391230. 25
C. Cornelio, A. Loreggia, and V. Saraswat. 2015. Logical conditional preference theories. Technical report, T.J. Watson Research Center. arXiv preprint: 1504.06374. 24
S. S. Cosmadakis, H. Gaifman, P. C. Kanellakis, and M. Y. Vardi. 1988. Decidable optimization problems for database logic programs (preliminary report). In Proc. of the 20th Annual ACM Symposium on Theory of Computing, pp. 477–490. DOI: 10.1145/62212.62259. 64
V. S. Costa, R. Rocha, and L. Damas. 2012. The YAP Prolog system. Theory and Practice of Logic Programming, 12(1-2):5–34. DOI: 10.1017/S1471068411000512. 52
F. Cuppens and R. Demolombe. 1988. A Prolog-relational DBMS interface using delayed evaluation. In Proc. of the Third International Conference on Data and Knowledge Bases: Improving Usability and Responsiveness, pp. 135–148. DOI: 10.1016/B978-1-4832-1313-2.50018-4. 63
B. P. L. da Silva, J.-F. Baget, and M. Croitoru. 2012. A generic platform for ontological query answering. In M. Bramer and M. Petridis, editors, Proc. of AI-2012, The Thirty-second SGAI International Conference on Innovative Techniques and Applications of Artificial Intelligence, pp. 151–164. Springer London, London, UK. DOI: 10.1007/978-1-4471-4739-8_11. 28
V. Dahl. Mar. 1982. On database systems development through logic. ACM Trans. on Database Systems, 7(1):102–123. DOI: 10.1145/319682.319700. 14
V. Dahl. 1986. Logic programming for constructive expert database systems. In Proc. from the First International Workshop on Expert Database Systems, pp. 209–217. Benjamin-Cummings Publishing Co., Inc., Redwood City, CA. 14
E. Dantsin, T. Eiter, G. Gottlob, and A. Voronkov. Sept. 2001. Complexity and expressive power of logic programming. ACM Computing Surveys, 33(3):374–425. DOI: 10.1145/502807.502810. 77
R. Davis. Feb. 1986. Knowledge-based systems. Science, 231(4741):957–964. 14
O. de Moor, M. Verbaere, E. Hajiyev, P. Avgustinov, T. Ekman, N. Ongkingco, D. Sereni, and J. Tibble. 2007. Keynote address: .QL for source code analysis. In Proc. of the Seventh IEEE International Working Conference on Source Code Analysis and Manipulation, SCAM ’07, pp. 3–16. IEEE Computer Society. DOI: 10.1109/SCAM.2007.31. 79, 80
C. de Sainte Marie, G. Hallmark, and A. Paschke, Feb. 2013. RIF production rule dialect. W3C Recommendation. Available at: http://www.w3.org/TR/rif-prd/. 42
H. Decker. 1986. Integrity enforcement on deductive databases. In Proc. of the Expert Database Conference, pp. 381–395. 31
S. Decker, D. Brickley, J. Saarela, and J. Angele. Dec. 1998. A query and inference service for RDF. In QL’98—The Query Languages Workshop. 78
M. Denecker, M. Bruynooghe, and V. W. Marek. 2001. Logic programming revisited: Logic programs as inductive definitions. ACM Trans. Comput. Log., 2(4):623–654. DOI: 10.1145/383779.383789. 22
M. A. Derr, S. Morishita, and G. Phipps. Apr. 1994. The Glue-Nail deductive database system: Design, implementation, and evaluation. The VLDB Journal, 3(2):123–160. DOI: 10.1007/BF01228879. 68
A. Deutsch, A. Nash, and J. Remmel. 2008. The chase revisited. In Proc. of the Twenty-seventh ACM SIGMOD-SIGACT-SIGART Symposium on Principles of Database Systems, PODS ’08, pp. 149–158. ACM. DOI: 10.1145/1376916.1376938. 26, 27
S. W. Dietrich. 1987. Extension tables: Memo relations in logic programming. In Proc. of the 1987 Symposium on Logic Programming, pp. 264–272. 59
S. W. Dietrich and D. S. Warren. 1986. Extension tables: Memo relations in logic programming. Technical Report 86/18, Dept. of Computer Science, SUNY at Stony Brook. 59
C. Draxler. Aug. 1993. A powerful Prolog to SQL compiler. Technical report, CIS Centre for Information Processing. 63
T. Eiter, G. Gottlob, and H. Mannila. Sept. 1997. Disjunctive Datalog. ACM Trans. Database Syst., 22(3):364–418. DOI: 10.1145/261124.261126. 22
T. Eiter, T. Lukasiewicz, R. Schindlauer, and H. Tompits. June 2004a. Combining answer set programming with description logics for the semantic web. In Proc. of the International Conference of Knowledge Representation and Reasoning (KR’04), pp. 141–151. DOI: 10.1016/j.artint.2008.04.002. 78
T. Eiter, T. Lukasiewicz, R. Schindlauer, and H. Tompits. Oct. 2004b. Well-founded semantics for description logic programs in the semantic Web. In Rules and Rule Markup Languages for the Semantic Web, pp. 81–97. DOI: 10.1007/978-3-540-30504-0_7. 78
T. Feder and M. Y. Vardi. Feb. 1999. The computational structure of monotone monadic SNP and constraint satisfaction: A study through Datalog and group theory. SIAM J. Computing, 28(1):57–104. DOI: 10.1137/S0097539794266766. 77
C. Fellenstein, C. O. Green, L. M. Palmer, A. Walker, and D. J. Wyler. July 1985. A prototype manufacturing knowledge base in Syllog. IBM Journal of Research and Development, 29(4):413–421. DOI: 10.1147/rd.294.0413. 14
N. V. Findler, editor. 1979. Associative Networks: The Representation and Use of Knowledge by Computers. Academic Press, Inc., Orlando, FL, USA. 14
P. Fodor and M. Kifer. July 2011. Transaction Logic with defaults and argumentation theories. In International Conference on Logic Programming, pp. 162–174. DOI: 10.4230/LIPIcs.ICLP.2011.162. 45
M. Freeston. 1987. The BANG file: A new kind of grid file. In Proc. of the 1987 ACM SIGMOD International Conference on Management of Data, SIGMOD ’87, pp. 260–269. ACM. DOI: 10.1145/38714.38743. 69
J. Freire, T. Swift, and D. S. Warren. July 1997. Taking I/O seriously: Resolution reconsidered for disk. In Proc. of the Joint Conference and Symposium on Logic Programming, pp. 198–212. MIT Press. 72
B. Freitag, H. Schütz, and G. Specht. 1992. LOLA—a logic language for deductive databases and its implementation. In Proc. of the Second International Symposium on Database Systems for Advanced Applications, pp. 216–225. World Scientific Press. 73
B. Freitag, H. Decker, M. Kifer, and A. Voronkov, editors. 1998. Transactions and Change in Logic Databases, vol. 1472 of LNCS. Springer-Verlag, Berlin. 103
J. Frohn, R. Himmeröder, G. Lausen, W. May, and C. Schlepphorst. 1998. Managing semistructured data with FLORID: A deductive object-oriented perspective. Information Systems, 23(8):589–613. 34, 36, 73
K. Fuchi. 1981. Aiming for knowledge information processing systems. In Proc. of the International Conference on Fifth Generation Computer Systems, pp. 110–117. 12
K. Fuchi and K. Furukawa. Apr. 1987. The role of logic programming in the Fifth Generation Computer Project. New Generation Computing, 5(1):3–28. DOI: 10.1007/BF03037455. 12
T. Furche, G. Gottlob, G. Grasso, X. Guo, G. Orsi, C. Schallhart, and C. Wang. Oct. 2014. DIADEM: Thousands of websites to a single database. Proc. VLDB Endow., 7(14):1845–1856. DOI: 10.14778/2733085.2733091. 83
F. Furfaro, S. Greco, S. Ganguly, and C. Zaniolo. 2002. Pushing extrema aggregates to optimize logic queries. Information Systems, 27(5):321–343. DOI: 10.1016/S0306-4379(02)00006-6. 82
H. Gaifman, H. G. Mairson, Y. Sagiv, and M. Y. Vardi. 1993. Undecidable optimization problems for database logic programs. J. ACM, 40(3):683–713. DOI: 10.1145/174130.174142. 64
H. Gallaire and J. Minker, editors. 1978. Logic and Data Bases, Symposium on Logic and Data Bases, Advances in Data Base Theory, Plenum Press, New York.
H. Gallaire, J. Nicolas, and J. Minker, editors. 1981. Advances in Data Base Theory, Vol. 1, Based on the Proc. of the Workshop on Formal Bases for Data Bases, Advances in Data Base Theory, Plenum Press, New York.
H. Garcia-Molina, J. D. Ullman, and J. Widom. 2009. Database Systems: The Complete Book (2nd ed.). Pearson Education. 6
M. Gelfond and V. Lifschitz. 1988. The stable model semantics for logic programming. In Logic Programming: Proc. of the Fifth Conference and Symposium, pp. 1070–1080. MIT Press. 20, 21
R. G. Goebel. 1985. A Logic Data Model for the Machine Representation of Knowledge. Ph.D. thesis, University of British Columbia. 14
J. E. Gonzalez, R. S. Xin, A. Dave, D. Crankshaw, M. J. Franklin, and I. Stoica. 2014. GraphX: Graph processing in a distributed dataflow framework. In Proceedings of the 11th USENIX Conference on Operating Systems Design and Implementation, OSDI’14, pp. 599–613. USENIX Association, Berkeley, CA. 83
G. Gottlob and C. Koch. Jan. 2004. Monadic datalog and the expressive power of languages for Web information extraction. J. ACM, 51(1):74–113. DOI: 10.1145/962446.962450. 77
G. Gottlob and C. H. Papadimitriou. 1999. On the complexity of single-rule datalog queries. In Proc. of the 6th International Conference on Logic Programming and Automated Reasoning, LPAR ’99, pp. 201–222. Springer-Verlag, London, UK. DOI: 10.1007/3-540-48242-3_13. 77
G. Gottlob, S. Ceri, and L. Tanca. Mar. 1989. What you always wanted to know about Datalog (and never dared to ask). IEEE Trans. on Knowledge & Data Engineering, 1(1):146–166. DOI: 10.1109/69.43410. 60
G. Gottlob, C. Koch, R. Baumgartner, M. Herzog, and S. Flesca. 2004. The Lixto data extraction project: Back and forth between theory and practice. In Proc. of the Twentythird ACM SIGMOD-SIGACT-SIGART Symposium on Principles of Database Systems, PODS ’04, pp. 1–12. ACM. DOI: 10.1145/1055558.1055560. 83
G. Gottlob, M. Manna, and A. Pieris. 2013. Combining decidability paradigms for existential rules. TPLP, 13(4-5):877–892. DOI: 10.1017/S1471068413000550. 28
G. Gottlob, T. Lukasiewicz, and A. Pieris. 2014. Datalog±: Questions and answers. In Proc. of the Fourteenth International Conference on Principles of Knowledge Representation and Reasoning, KR 2014, pp. 682–685. 25
J. Grant and J. Minker. 1981. Optimization in deductive and conventional relational database systems. In H. Gallaire, J. Nicolas, and J. Minker, editors, Advances in Data Base Theory, pp. 195-234, Vol. 1. Plenum Press, New York. DOI: 10.1007/978-1-4615-8297-7_8. 63
B. C. Grau, I. Horrocks, B. Motik, B. Parsia, P. Patel-Schneider, and U. Sattler. Nov. 2008. OWL 2: The next step for OWL. Web Semantics, 6(4):309–322. DOI: 10.1016/j.websem.2008.05.001. 78
C. C. Green. 1969. Application of theorem proving to problem solving. In International Joint Conference on Artificial Intelligence, pp. 219–240. 14, 41
C. C. Green and B. Raphael. 1968. The use of theorem-proving techniques in question-answering systems. In Proc. of the 1968 23rd ACM National Conference, ACM ’68, pp. 169–181. ACM. DOI: 10.1145/800186.810578. 13
B. Grosof and T. Swift. July 2013. Radial restraint: A semantically clean approach to bounded rationality for logic programs. In AAAI Conference on Artificial Intelligence. AAAI Press. 28
R. V. Guha, O. Lassila, E. Miler, and D. Brickley. Dec. 1998. Enabling inferencing. In QL’98—The Query Languages Workshop. 78
H. Guo and G. Gupta. Nov. 2001. A simple scheme for implementing tabled logic programming systems based on dynamic reordering of alternatives. In Proc. of the 17th International Conference on Logic Programming, ICLP 2001, pp. 181–196. DOI: 10.1007/3-540-45635-X_20. 59
L. M. Haas, J. C. Freytag, G. M. Lohman, and H. Pirahesh. 1989. Extensible query processing in Starburst. In Proc. of the 1989 ACM SIGMOD International Conference on Management of Data, SIGMOD ’89, pp. 377–388. ACM. DOI: 10.1145/67544.66962. 73
C. D. Hafner and K. Godden. Apr. 1985. Portability of syntax and semantics in DATALOG. ACM Trans. on Information Systems, 3(2):141–164. DOI: 10.1145/3914.3982. 16
E. Hajiyev, M. Verbaere, and O. de Moor. 2006. CodeQuest: Scalable source code queries with Datalog. In Proc. of the 20th European Conference on Object-Oriented Programming, ECOOP’06, pp. 2–27. Springer-Verlag, Berlin, Heidelberg. DOI: 10.1007/11785477_2. 79
D. Harel. 1979. First-Order Dynamic Logic, vol. 68 of Lecture Notes in Computer Science. Springer-Verlag. DOI: 10.1007/3-540-09237-4. 39
D. Harel, D. Kozen, and R. Parikh. Oct. 1982. Process Logic: Expressiveness, decidability, completeness. Journal of Computer and System Sciences, 25(2):144–170. DOI: 10.1016/0022-0000(82)90003-4. 39
P. J. Hayes. 1977. In defence of logic. In Proc. of the 5th International Joint Conference on Artificial Intelligence, Vol. 1, IJCAI’77, pp. 559–565. Morgan Kaufmann Publishers Inc., San Francisco, CA. 14
P. J. Hayes. 1980. The logic of frames. In Frame Conceptions and Text Understanding, pp. 46–61. Walter de Gruyter, Berlin. DOI: 10.1016/B978-0-934613-03-3.50034-9. 14
A. Heuer and P. Sander. 1989. Semantics and evaluation of rules over complex objects. In International Conference on Deductive and Object-Oriented Databases, pp. 439–458. DOI: 10.1016/B978-0-444-88433-6.50033-2. 33
M. A. W. Houtsma and P. M. G. Apers. 1992. Algebraic optimization of recursive queries. Data & Knowledge Engineering, 7(4):299–325. DOI: 10.1016/0169-023X(92)90029-B. 63
N. Immerman. 1982. Relational queries computable in polynomial time (extended abstract). In Proceedings of the Fourteenth Annual ACM Symposium on Theory of Computing, STOC ’82, pp. 147–152. ACM. DOI: 10.1145/800070.802187. 77
Y. E. Ioannidis, J. Chen, M. A. Friedman, and M. M. Tsangaris. 1988. Bermuda—an architectural perspective on interfacing Prolog to a database machine. In Expert Database Conference, pp. 229–255. 63
Z. G. Ives, T. J. Green, G. Karvounarakis, N. E. Taylor, V. Tannen, P. P. Talukdar, M. Jacob, and F. Pereira. Sept. 2008. The ORCHESTRA collaborative data sharing system. SIGMOD Rec., 37(3):26–32. DOI: 10.1145/1462571.1462577. 83
D. S. Johnson and A. Klug. 1984. Testing containment of conjunctive queries under functional and inclusion dependencies. Journal of Computer and System Sciences, 28: 167–189. DOI: 10.1016/0022-0000(84)90081-3. 27, 28, 32
N. D. Jones, C. K. Gomard, and P. Sestoft. 1993. Partial Evaluation and Automatic Program Generation. Prentice-Hall, Inc., Upper Saddle River, NJ. 51
C. Kellogg, P. Klahr, and L. Travis. 1977. Deductive planning and pathfinding for relational data bases. In H. Gallaire and J. Minker, editors, Logic and Data Bases, pp. 179-200, Plenum Press, New York. DOI: 10.1007/978-1-4684-3384-5_7. 13, 63
D. B. Kemp and P. J. Stuckey. Oct. 1991. Semantics of logic programs with aggregates. In Proc. of International Symposium on Logic Programming, pp. 387–401. MIT Press. 24
L. Kerschberg. 1990. Expert database systems: Knowledge/data management environments for intelligent information systems. Information Systems, 15(1):151–160. DOI: 10.1016/0306-4379(90)90021-G. 14
G. Kiernan, C. de Maindreville, and E. Simon. 1990. Making deductive databases a practical technology: A step forward. In Proc. of the 1990 ACM SIGMOD International Conference on Management of Data, SIGMOD ’90, pp. 237–246. ACM. DOI: 10.1145/93605.98733. 73
W. Kießling, H. Schmidt, W. Strauß, and G. Dünzinger. Apr. 1994. DECLARE and SDS: Early efforts to commercialize deductive database technology. The VLDB Journal, 3(2):211–243. 72
M. Kifer, 2015. Knowledge representation & reasoning with Flora-2. The Flora-2 Web Site. Available at: http://flora.sourceforge.net. 34, 38, 46, 91
M. Kifer and G. Lausen. 1989. F-Logic: A higher-order language for reasoning about objects, inheritance and schema. In ACM SIGMOD Conference on Management of Data, pp. 134–146. ACM. DOI: 10.1145/66926.66939. 33, 34
M. Kifer and A. Li. Sept. 1988. On the semantics of rule based expert systems with uncertainty. In International Conference on Database Theory, vol. 326 of Lecture Notes in Computer Science, pp. 186–202. Springer-Verlag. DOI: 10.1007/3-540-50171-1_6. 14
M. Kifer and E. L. Lozinskii. Feb. 1987. Implementing logic programs as a database system. In IEEE 3rd International Conference on Data Engineering, pp. 375–385. DOI: 10.1109/ICDE.1987.7272403. 51
M. Kifer and E. L. Lozinskii. 1988. SYGRAF: Implementing logic programs in a database style. IEEE Trans. on Software Engineering, 14(7):922–935. DOI: 10.1109/32.42735. 51
M. Kifer and E. L. Lozinskii. Sept. 1990. On compile-time query optimization in deductive databases by means of static filtering. ACM Trans. on Database Systems, 15(3):385–426. DOI: 10.1145/88636.87121. 51
M. Kifer and J. Wu. Mar. 1989. A logic for object-oriented logic programming (Maier’s Ologic revisited). In ACM Symposium on Principles of Database Systems, pp. 379–393. ACM. DOI: 10.1145/73721.73758. 33, 34
M. Kifer and J. Wu. Aug. 1993. A logic for programming with complex objects. Journal of Computer and System Sciences, 47(1):77–120. 34
M. Kifer, G. Lausen, and J. Wu. July 1995. Logical foundations of object-oriented and framebased languages. Journal of ACM, 42: 741–843. DOI: 10.1145/210332.210335. 33, 34, 35
R. A. Kowalski. June 1974. Predicate logic as programming language. In Proceedings of the IFIP Congress, vol. 74, pp. 569–544. 11
R. A. Kowalski. Jan. 1988. The early years of logic programming. Commun. ACM, 31(1):38–43. DOI: 10.1145/35043.35046. 11
R. A. Kowalski. 2014. Logic programming. In J. Siekmann, editor, Computational Logic, vol. 9 of History of Logic. D. Gabbay and J. Woods, editors, pp. 523–569. Elsevier. 12
R. A. Kowalski and F. Sadri. 2012. A logic-based framework for reactive systems. In Rules on the Web: Research and Applications, RuleML 2012, vol. 7438 of Lecture Notes in Computer Science, pp. 1–15. Springer. DOI: 10.1007/978-3-642-32689-9_1. 43
R. A. Kowalski and M. Sergot. 1986. A logic-based calculus of events. New Generation Computing, 4: 67–95. DOI: 10.1007/BF03037383. 41
R. A. Kowalski, F. Sadri, and P. Soper. 1987. Integrity checking in deductive databases. In Proc. of the 13th International Conference on Very Large Data Bases, VLDB ’87, pp. 61–69. Morgan Kaufmann Publishers Inc., San Francisco, CA. 29, 31
L. V. S. Lakshmanan and R. Missaoui. 1992. On semantic query optimization in deductive databases. In Proc. of the Eighth International Conference on Data Engineering, pp. 368–375. IEEE Computer Society. DOI: 10.1109/ICDE.1992.213173. 32
L. V. S. Lakshmanan, I. N. Subramanian, and F. Sadri. 1996. A declarative language for querying and restructuring the Web. In Proc. of the 6th International Workshop on Research Issues in Data Engineering (RIDE ’96) Interoperability of Nontraditional Database Systems, RIDE ’96, pp. 12–21. IEEE Computer Society. DOI: 10.1109/RIDE.1996.492238. 36, 73
M. S. Lam, J. Whaley, V. B. Livshits, M. C. Martin, D. Avots, M. Carbin, and C. Unkel. 2005. Context-sensitive program analysis as database queries. In Proc. of the Twenty-fourth ACM SIGMOD-SIGACT-SIGART Symposium on Principles of Database Systems, PODS ’05, pp. 1–12. ACM. DOI: 10.1145/1065167.1065169. 79, 80
M. S. Lam, S. Guo, and J. Seo. 2013. SociaLite: Datalog extensions for efficient social network analysis. In Proc. of the 2013 IEEE International Conference on Data Engineering (ICDE 2013), ICDE ’13, pp. 278–289. IEEE Computer Society. DOI: 10.1109/ICDE.2013.6544832. 82
O. Lassila and R. R. Swick. Feb. 1999. Resource description framework (RDF) model and syntax specification. Technical report, W3C. Available at: http://www.w3.org/TR/1999/REC-rdf-syntax-19990222/. 34, 78
G. Lausen and B. Ludäascher. 1995. Updates by reasoning about states. In Eder J., Kalinichenko L.A. (editors) East/West Database Workshop. Workshops in Computing. Springer, London. 41
S. Lee and J. Han. 1988. Semantic query optimization in recursive databases. In Proc. of the Fourth International Conference on Data Engineering, pp. 444–451. IEEE Computer Society. DOI: 10.1109/ICDE.1988.105490. 32
N. Leone, G. Pfeifer, W. Faber, T. Eiter, G. Gottlob, S. Perri, and F. Scarcello. July 2006. The DLV system for knowledge representation and reasoning. ACM Trans. on Computational Logic, 7(3):499–562. DOI: 10.1145/1149114.1149117. 83
A. Y. Levy and Y. Sagiv. 1995. Semantic query optimization in datalog programs (extended abstract). In Proc. of the Fourteenth ACM SIGACT-SIGMOD-SIGART Symposium on Principles of Database Systems, PODS ’95, pp. 163–173. ACM. DOI: 10.1145/212433.220207. 32
Y. A. Liu and S. D. Stoller. 2009. From Datalog rules to efficient programs with time and space guarantees. ACM Trans. Prog. Lang. Syst., 31(6):1–38. DOI: 10.1145/1552309.1552311. 49, 52, 535
Y. A. Liu and S. D. Stoller. Jan. 2018. Founded semantics and constraint semantics of logic rules. In International Symposium on Logical Foundations of Computer Science, vol. 10703 of Lecture Notes in Computer Science, pp. 221–241. Springer. DOI: 10.1007/978-3-319-72056-2_14. 22
J. W. Lloyd. 1993. Foundations of Logic Programming, 2nd. Springer-Verlag New York, Inc., Secaucus, NJ. 9, 11
J. W. Lloyd, L. Sonenberg, and R. W. Topor. 1987. Integrity constraint checking in stratified databases. Journal of Logic Programming, 4(4):331–343. DOI: 10.1016/0743-1066(87)90009-4. 30
B. T. Loo, T. Condie, J. M. Hellerstein, P. Maniatis, T. Roscoe, and I. Stoica. 2005. Implementing declarative overlays. In Proc. of the Twentieth ACM Symposium on Operating Systems Principles, SOSP ’05, pp. 75–90. ACM. DOI: 10.1145/1095809.1095818. 81
B. T. Loo, T. Condie, M. Garofalakis, D. E. Gay, J. M. Hellerstein, P. Maniatis, R. Ramakrishnan, T. Roscoe, and I. Stoica. 2006. Declarative networking: Language, execution and optimization. In Proc. of the 2006 ACM SIGMOD International Conference on Management of Data, SIGMOD ’06, pp. 97–108. ACM. DOI: 10.1145/1142473.1142485. 80, 81
B. T. Loo, T. Condie, M. Garofalakis, D. E. Gay, J. M. Hellerstein, P. Maniatis, R. Ramakrishnan, T. Roscoe, and I. Stoica. Nov. 2009. Declarative networking. Commun. ACM, 52(11):87–95. DOI: 10.1145/1592761.1592785. 80
D. Maier. Aug. 1986a. A logic for objects. In Workshop on Foundations of Deductive Databases and Logic Programming, pp. 6–26. Washington D.C. 33, 34
D. Maier. 1986b. Databases in the Fifth Generation project: Is Prolog a database language? In G. Ariav and J. Clifford, editors, New Directions for Database Systems, pp. 18–34. Ablex Publishing Corporation. 12
D. Maier and D. S. Warren. 1981. Incorporating computed relations in relational databases. In Proc. of the 1981 ACM SIGMOD International Conference on Management of Data, SIGMOD ’81, pp. 176–187. ACM. DOI: 10.1145/582318.582345. 23
D. Maier and D. S. Warren. 1988. Computing with Logic: Logic Programming with Prolog. Benjamin/Cummings. 15
D. Maier, A. O. Mendelzon, and Y. Sagiv. 1979. Testing implications of data dependencies. Trans. Database Syst., 4(4):455–469. DOI: 10.1145/320107.320115. 27
F. Maier, D. Nute, W. D. Potter, J. Wang, M. J. Twery, H. M. Rauscher, P. Knopp, S. Thomasma, M. Dass, and H. Uchiyama. 2002. PROLOG/RDBMS integration in the NED intelligent information system. In On the Move to Meaningful Internet Systems, 2002—DOA/CoopIS/ODBASE Proc. of the Confederated International Conferences DOA, CoopIS and ODBASE, p. 528. DOI: 10.1007/3-540-36124-3_35. 63
V. W. Marek and M. Truszczyński. 1999. Stable models and an alternative logic programming paradigm. In K. R. Apt, V. W. Marek, M. Truszczynski, and D. S. Warren, editors, The Logic Programming Paradigm: A 25-Year Perspective, pp. 375–398. Springer, Berlin, Heidelberg. DOI: 10.1007/978-3-642-60085-2_17. 22
D. Martinenghi, H. Christiansen, and H. Decker. 2006. Integrity checking and maintenance in relational and deductive databases and beyond. In Z. Ma, editor, Intelligent Databases: Technologies and Applications, pp. 238–285. Idea Group Publishing. DOI: 10.4018/978-1-59904-120-9.ch010. 30, 31
MathGen, 2000. Mathematics Genealogy Project. Available at: http://genealogy.math.ndsu.nodak.edu/. Last accessed 1 August 2016. 84
F. G. McCabe. 1992. Logic and Objects. Prentice Hall International, London, England. 33
J. M. McCarthy and P. J. Hayes. 1969. Some philosophical problems from the standpoint of artificial intelligence. In B. Meltzer and D. Michie, editors, Machine Intelligence, vol. 4, pp. 463–502. Edinburgh University Press. Reprinted in Readings in Artificial Intelligence, 1981, Tioga Publishing Co. DOI: 10.1016/B978-0-934613-03-3.50033-7. 40
D. A. Miller and G. Nadathur. July 1986. Higher-order logic programming. In International Conference on Logic Programming, vol. 225 of Lecture Notes in Computer Science, pp. 448–462. Springer-Verlag. 38
J. Minker. 1977. An experimental relational data base system based on logic. In H. Gallaire and J. Minker, editors, Logic and Data Bases, pp. 107-147, Plenum Press, New York. DOI: 10.1007/978-1-4684-3384-5_5. 13
J. Minker. Mar. 1994. Overview of disjunctive logic programming. Annals of Mathematics and Artificial Intelligence, 12(1): 1–24. DOI: 10.1007/BF01530759. 22
J. Minker and D. Seipel. 2002. Disjunctive logic programming: A survey and assessment. In Computational Logic: Logic Programming and Beyond, pp. 171–197. Springer. DOI: 10.1007/3-540-45628-7_18. 22
J. Minker, D. Seipel, and C. Zaniolo. 2014. Logic and databases: A history of deductive databases. In J. H. Siekmann, editor, Computational Logic, vol. 9 of Handbook of the History of Logic, pp. 571–627. Elsevier. DOI: 10.1016/B978-0-444-51624-4.50013-7. 13, 15
M. Minsky. 1975. A framework for representing knowledge. In P. Winston, editor, The Psychology of Computer Vision, pp. 211–277. McGraw-Hill, New York. 14, 35
S. Morishita. 1993. An alternating fixpoint tailored to magic programs. In Proc. of the Twelfth ACM SIGACT-SIGMOD-SIGART Symposium on Principles of Database Systems, PODS ’93, pp. 123–134. ACM. DOI: 10.1145/153850.153861. 69
K. A. Morris, J. D. Ullman, and A. Van Gelder. 1986. Design overview of the NAIL! system. In Proc. of the Third International Conference on Logic Programming, pp. 554–568. Springer-Verlag, London, UK. DOI: 10.1007/3-540-16492-8_104. 68
C. Moss. 1994. Prolog++: The Power of Object-Oriented and Logic Programming. Addison-Wesley. 33
B. Motik, I. Horrocks, R. Rosati, and U. Sattler. Nov. 2006. Can OWL and logic programming live together happily ever after? In International Semantic Web Conference (ISWC2006), pp. 501–514. DOI: 10.1007/11926078_36. 78
T. Moto-oka and H. S. Stone. Mar. 1984. Fifth-generation computer systems: A Japanese project. Computer, 17(3):6–13. DOI: 10.1109/MC.1984.1659076. 12, 48
P. Moura. July 2000. Logtalk documentation. Technical Report DMI-2000/1, University of Beira Interior, Portugal. Available at: http://logtalk.org/papers/trdmi20001us.pdf. 33
P. Moura, P. Crocker, and P. Nunes. Jan. 2008. High-level multi-threading programming in logtalk. In Practical Aspects of Declarative Languages (PADL), vol. 4902 of Lecture Notes in Computer Science. Springer. DOI: 10.1007/978-3-540-77442-6_18. 33
I. S. Mumick and H. Pirahesh. May 1994. Implementation of Magic-sets in a relational database system. SIGMOD Rec., 23(2):103–114. DOI: 10.1145/191839.191860. 73
S. Naqvi and R. Krishnamurthy. Mar. 1988. Database updates in logic programming. In ACM Symposium on Principles of Database Systems, pp. 251–262. ACM. DOI: 10.1145/308386.308451. 46
S. Naqvi and S. Tsur. 1989. A Logical Language for Data and Knowledge Bases. Computer Science Press, Rockville, MD. 46
J. Naughton. 1986. Data independent recursion in deductive databases. In Proc. of the Fifth ACM SIGACT-SIGMOD Symposium on Principles of Database Systems, PODS ’86, pp. 267–279. ACM. DOI: 10.1145/6012.15420. 64
W. Nejdl. 1987. Recursive strategies for answering recursive queries—the RQA/FQI strategy. In Proc. of the 13th International Conference on Very Large Data Bases, VLDB ’87, pp. 43–50. Morgan Kaufmann Publishers Inc., San Francisco, CA. 60
J. Nicolas and H. Gallaire. 1977. Data base: Theory vs. interpretation. In H. Gallaire and J. Minker, editors, Logic and Data Bases, pp. 33-54, Plenum Press, New York. 13, 19
J. Nicolas and K. Yazdanian. 1977. Integrity checking in deductive data bases. In H. Gallaire and J. Minker, editors, Logic and Data Bases, pp. 325-344, Plenum Press, New York. 29
C. H. Papadimitriou. 1985. A note the expressive power of Prolog. Bulletin of the EATCS, 26: 21–22. 77
J. Paredaens. 1978. On the expressive power of the relational algebra. Information Processing Letters, 7(2):107–111. DOI: 10.1016/0020-0190(78)90055-8. 13
N. Pelov, M. Denecker, and M. Bruynooghe. May 2007. Well-founded and stable semantics of logic programs with aggregates. Theory and Practice of Logic Programming, 7(03):301–353. DOI: 10.1017/S1471068406002973. 24
A. Polleres. 2007. From SPARQL to rules (and back). In Proc. of the 16th International Conference on World Wide Web, WWW ’07, pp. 787–796. ACM. DOI: 10.1145/1242572.1242679. 76
H. H. Porter, Oct. 1985. Optimizations to Earley deduction for DATALOG programs. Available at: http://www.cs.pdx.edu/~harry/earley/datalog.pdf. 16
E. Prud’hommeaux, A. Seaborne, et al. 2008. SPARQL query language for RDF. W3C recommendation 15 January 2008. http://www.w3.org/TR/rdf-sparql-query/. 88
T. C. Przymusinski. 1988a. On the declarative semantics of deductive databases and logic programs. In Foundations of Deductive Databases and Logic Programming, pp. 193–216. Morgan Kaufmann. DOI: 10.1016/B978-0-934613-40-8.50009-9. 20
T. C. Przymusinski. 1988b. Perfect model semantics. In Proc. of the Fifth International Conference and Symposium on Logic Programming, pp. 1081–1096. 19
T. C. Przymusinski. 1989. Every logic program has a natural stratification and an iterated least fixed point model. In Proc. of the Eighth ACM SIGACT-SIGMOD-SIGART Symposium on Principles of Database Systems, PODS ’89, pp. 11–21. ACM. DOI: 10.1145/73721.73723. 20
F. Puppe. 1993. Characterization and history of expert systems. In Systematic Introduction to Expert Systems, pp. 3–8. Springer. DOI: 10.1007/978-3-642-77971-8_1. 14
R. Ramakrishnan. Oct./Nov. 1991. Magic templates: A spellbinding approach to logic programs. Journal of Logic Programming, 11(3-4):189–216. DOI: 10.1016/0743-1066(91)90026-L. 51, 68
R. Ramakrishnan and J. D. Ullman. 1995. A survey of deductive database systems. Journal of Logic Programming, 23(2):125–149. DOI: 10.1016/0743-1066(94)00039-9. 65
R. Ramakrishnan, D. Srivastava, S. Sudarshan, and P. Seshadri. Apr. 1994. The CORAL deductive system. The VLDB Journal, 3(2):161–210. DOI: 10.1007/BF01228880. 67
K. Ramamohanarao, J. Shepherd, I. Balbin, G. S. Port, L. Naish, J. A. Thom, J. Zobel, and P. W. Dart. 1988. The NU-Prolog deductive database system. In Prolog and Databases, pp. 212–250. Halsted Press. 72
R. Reiter. 1977a. Deductive question-answering on relational data bases. In H. Gallaire and J. Minker, editors, Logic and Data Bases, pp. 149-177, Plenum Press, New York. DOI: 10.1007/978-1-4684-3384-5_6. 13, 63
R. Reiter. 1977b. On closed world data bases. In H. Gallaire and J. Minker, editors, Logic and Data Bases, pp. 55-76, Plenum Press, New York. 13, 21
R. Reiter. 1981. On the integrity of typed first order data bases. In H. Gallaire, J. Nicolas, and J. Minker, editors, Advances in Data Base Theory, pp. 137-157, Vol. 1. Plenum Press, New York. 31
R. Reiter. 1991. The frame problem in the situation calculus: A simple solution (sometimes) and a completeness result for goal regression. In V. Lifschitz, editor, Aritifial Intelligence and Mathematical Theory of Computation: Papers in Honor of John McCarty, pp. 359–380. Academic Press. 41
M. Rezk and M. Kifer. 2012. Transaction Logic with partially defined actions. Journal of Data Semantics, 1(2):99–131. DOI: 10.1007/s13740-012-0007-8. 46
J. A. Robinson. 1965. A machine-oriented logic based on the resolution principle. Journal of the ACM, 12(1):23–41. DOI: 10.1145/321250.321253. 11
D. Roman and M. Kifer. Sept. 2007. Reasoning about the behavior of semantic Web services with Concurrent Transaction Logic. In International Conference on Very Large Data Bases (VLDB), pp. 627–638. 46
A. Rosenthal, S. Heiler, U. Dayal, and F. Manola. June 1986. Traversal recursion: A practical approach to supporting recursive applications. SIGMOD Rec., 15(2):166–176. DOI: 10.1145/16894.16871. 13
K. A. Ross and Y. Sagiv. 1992. Monotonic aggregation in deductive databases. In Proc. of the Eleventh ACM SIGACT-SIGMOD-SIGART Symposium on Principles of Database Systems, PODS ’92, pp. 114–126. ACM. DOI: 10.1145/137097.137852. 25
D. Saccà and C. Zaniolo. 1986a. The generalized counting method for recursive logic queries. In G. Ausiello and P. Atzeni, editors, ICDT’86, International Conference on Database Theory, Rome, Italy, Sept. 8–10, 1986, vol. 243 of Lecture Notes in Computer Science, pp. 31–53. Springer. DOI: 10.1007/3-540-17187-8_28. 51, 66
D. Saccà and C. Zaniolo. 1986b. On the implementation of a simple class of logic queries for databases. In A. Silberschatz, editor, Proc. of the Fifth ACM SIGACT-SIGMOD Symposium on Principles of Database Systems, pp. 16–23. ACM. DOI: 10.1145/6012.6013. 51
Y. Sagiv. 1987. Optimizing Datalog programs. In Proc. of the Sixth ACM SIGACT-SIGMODSIGART Symposium on Principles of Database Systems, PODS ’87, pp. 349–362. ACM. DOI: 10.1145/28659.28696. 32, 64
K. Sagonas, T. Swift, and D. S. Warren. May 1994. XSB as an efficient deductive database engine. In Proc. of the 1994 ACM SIGMOD International Conference on Management of Data, pp. 442–453. DOI: 10.1145/191839.191927. 71, 85
Semafora, GmbH, 1999. Ontobroker. Available at: http://www.semafora-systems.com/en/. 34
J. Seo, J. Park, J. Shin, and M. S. Lam. Sept. 2013. Distributed SociaLite: A Datalog-based language for large-scale graph analysis. Proc. of the VLDB Endowment, 6(14):1906–1917. 82
A. Shkapsky, K. Zeng, and C. Zaniolo. Aug. 2013. Graph queries in a next-generation Datalog system. Proc. of the VLDB Endowment, 6(12):1258–1261. DOI: 10.14778/2536274.2536290. 65, 83
A. Shkapsky, M. Yang, M. Interlandi, H. Chiu, T. Condie, and C. Zaniolo. 2016. Big data analytics with Datalog queries on Spark. In Proc. of the 2016 International Conference on Management of Data, SIGMOD ’16, pp. 1135–1149. ACM. DOI: 10.1145/2882903.2915229. 83
O. Shmueli. 1993. Equivalence of DATALOG queries is undecidable. J. Log. Program., 15(3):231–241. DOI: 10.1016/0743-1066(93)90040-N. 64
Y. Smaragdakis and M. Bravenboer. 2011. Using Datalog for fast and easy program analysis. In Proc. of the First International Conference on Datalog Reloaded, Datalog’10, pp. 245–251. Springer-Verlag, Berlin, Heidelberg. DOI: 10.1007/978-3-642-24206-9_14. 79, 80
W. Snyder and J. Schmolze. July 1996. Rewrite semantics for production rule systems: Theory and applications. In 13th International Conference on Automated Deduction, vol. 1104 of LNAI, pp. 508–522. Springer. DOI: 10.1007/3-540-61511-3_110. 42
T. Swift and D. S. Warren. 2011. XSB: Extending the power of Prolog using tabling. Theory and Practice of Logic Programming, vol. 12, no. 1-2, pp. 157–187. Cambridge University Press. 24, 28, 52, 59
H. Tamaki and T. Sato. 1986. OLD resolution with tabulation. In Third International Conference on Logic Programming, pp. 84–98. DOI: 10.1007/3-540-16492-8_66. 59
P. Tarau. 2004. Agent-oriented logic programming constructs in Jinni. In International Conference on Logic Programming, vol. 3132 of Lecture Notes in Computer Science. DOI: 10.1007/978-3-540-27775-0_46. 33
K. T. Tekle and Y. A. Liu. 2010. Precise complexity analysis for efficient datalog queries. In Proc. of the 12th International ACM SIGPLAN Conference on Principles and Practice of Declarative Programming, pp. 35–44. DOI: 10.1145/1836089.1836094. 52, 58, 61, 93
K. T. Tekle and Y. A. Liu. 2011. More efficient Datalog queries: subsumptive tabling beats magic sets. In T. K. Sellis, R. J. Miller, A. Kementsietsidis, and Y. Velegrakis, editors, Proc. of the ACM SIGMOD International Conference on Management of Data, SIGMOD 2011, pp. 661–672. ACM. DOI: 10.1145/1989323.1989393. 52, 58, 61
K. T. Tekle, K. Hristova, and Y. A. Liu. 2008. Generating specialized rules and programs for demand-driven analysis. In Algebraic Methodology and Software Technology, 12th International Conference, AMAST 2008, Urbana, IL, USA, July 28–31, pp. 346–361. 51, 93
S. Tsur and C. Zaniolo. 1986. LDL: A logic-based data language. In Proc. of the 12th International Conference on Very Large Data Bases, VLDB ’86, pp. 33–41. Morgan Kaufmann Publishers Inc., San Francisco, CA. DOI: 10.1007/978-3-540-79980-1_26. 24, 65
J. D. Ullman. 1987. Database theory: Past and future. In ACM Symposium on Principles of Database Systems, pp. 1–10. ACM. DOI: 10.1145/28659.28660. 34
J. D. Ullman. 1989. Bottom-up beats top-down for Datalog. In Proc. of the Eighth ACM SIGACT-SIGMOD-SIGART Symposium on Principles of Database Systems, PODS ’89, pp. 140–149. ACM. DOI: 10.1145/73721.73736. 61
J. D. Ullman and A. Van Gelder. Nov. 1988. Parallel complexity of logical query programs. Algorithmica, 3(1-4):5–42. DOI: 10.1007/BF01762108. 77
J. Vaghani, K. Ramamohanarao, D. B. Kemp, Z. Somogyi, P. J. Stuckey, T. S. Leask, and J. Harland. Apr. 1994. The Aditi deductive database system. The VLDB Journal, 3(2):245–288. DOI: 10.1007/BF01228882. 72
G. van Emde Boas and P. van Emde Boas. Jan. 1986. Storing and evaluating horn-clause rules in a relational database. IBM Journal of Research and Development, 30(1):80–92. DOI: 10.1147/rd.301.0080. 63
M. H. Van Emden and R. A. Kowalski. Oct. 1976. The semantics of predicate logic as a programming language. J. ACM, 23(4):733–742. DOI: 10.1145/321978.321991. 9, 48
A. Van Gelder. 1989. Negation as failure using tight derivations for general logic programs. Journal of Logic Programming, 6(1):109–133. DOI: 10.1016/0743-1066(89)90032-0. 19
A. Van Gelder, K. A. Ross, and J. S. Schlipf. July 1991. The well-founded semantics for general logic programs. Journal of the ACM, 38(3):619–649. DOI: 10.1145/116825.116838. 20, 22
M. Y. Vardi. 1982. The complexity of relational query languages (extended abstract). In Proc. of the Fourteenth Annual ACM Symposium on Theory of Computing, STOC ’82, pp. 137–146. ACM. DOI: 10.1145/800070.802186. 77
M. Y. Vardi. 2016. A theory of regular queries. In T. Milo and W. Tan, editors, Proc. of the 35th ACM SIGMOD-SIGACT-SIGAI Symposium on Principles of Database Systems, PODS, pp. 1–9. ACM. DOI: 10.1145/2902251.2902305. 64
J. Vennekens, M. Denecker, and M. Bruynooghe. 2010. FO(ID) as an extension of DL with rules. Ann. Math. Artif. Intell., 58(1-2):85–115. 22
L. Vieille. 1986. Recursive axioms in deductive databases: The Query/Subquery approach. In Expert Database Conference, pp. 253–267. 60
L. Vieille. 1987. A database-complete proof procedure based on SLD-resolution. In Proc. of the Fourth International Conference on Logic Programming, pp. 74–103. 60
L. Vieille. 1998. From data independence to knowledge independence: An on-going story. In Proc. of the 24rd International Conference on Very Large Data Bases, VLDB ’98, pp. 650–654. Morgan Kaufmann Publishers Inc., San Francisco, CA. 70
L. Vieille, P. Bayer, V. Küchenhoff, A. Lefebvre, and R. Manthey. 1992. The EKS-V1 system. In Proc. of the International Conference on Logic Programming and Automated Reasoning, LPAR’92, pp. 504–506. DOI: 10.1007/BFb0013102. 69
H. Wan, B. Grosof, M. Kifer, P. Fodor, and S. Liang. July 2009. Logic programming with defaults and argumentation theories. In International Conference on Logic Programming. DOI: 10.1007/978-3-642-02846-5_35. 36
J. Wang, M. Balazinska, and D. Halperin. Aug. 2015. Asynchronous and fault-tolerant recursive datalog evaluation in shared-nothing engines. Proc. of the VLDB Endowment, 8(12):1542–1553. DOI: 10.14778/2824032.2824052. 82
K. Wang and L. Yuan. 1992. Preservation of integrity constraints in definite DATALOG programs. Information Processing Letters, 44(4):185–193. DOI: 10.1016/0020-0190(92)90083-8. 31
D. H. D. Warren. 1981. Efficient processing of interactive relational data base queries expressed in logic. In Proc. of the Seventh International Conference on Very Large Data Bases, VLDB ’81, pp. 272–281. VLDB Endowment. 12
D. H. D. Warren. 1982a. Higher-order extensions to Prolog: Are they needed? In J. E. Hayes, D. Michie, and Y.-H. Pao, editors, Machine Intelligence, vol. 10, pp. 441–454. Halsted Press. 37
D. H. D. Warren. 1982b. A view of the Fifth Generation and its impact. AI Magazine, 3(4):34. 12
D. H. D. Warren and F. C. N. Pereira. July 1982. An efficient easily adaptable system for interpreting natural language queries. Computational Linguistics, 8(3-4):110–122. 12
D. S. Warren. Mar. 1992. Memoing for logic programs. Commun. ACM, 35(3):93–111. DOI: 10.1145/131295.131299. 54
D. S. Warren, T. Swift, and K. F. Sagonas. Mar. 2007. The XSB Programmer’s Manual, Version 2.7.1. Technical report, Department of Computer Science, State University of New York at Stony Brook, Stony Brook, NY. The XSB System is available from xsb.sourceforge.net, and the system and manual is continually updated. 59, 71
T. Winograd. 1975. Frame Representations and the Procedural–Declarative Controversy. In D. Bobrow and A. Collins, editors, Representation and Understanding: Studies in Cognitive Science, pp. 185–210. Academic Press. DOI: 10.1016/B978-0-12-108550-6.50012-4. 14
G. Yang, M. Kifer, and C. Zhao. Nov. 2003. FLORA-2: A rule-based knowledge representation and inference infrastructure for the Semantic Web. In International Conference on Ontologies, Databases and Applications of Semantics (ODBASE-2003), vol. 2888 of Lecture Notes in Computer Science, pp. 671–688. Springer. DOI: 10.1007/978-3-540-39964-3_43. 34, 38, 46, 91
M. Yang, A. Shkapsky, and C. Zaniolo. Apr. 2017. Scaling up the performance of more powerful Datalog systems on multicore machines. The VLDB Journal, 26(2):229–248. DOI: 10.1007/s00778-016-0448-z. 83
C. Zaniolo. 1986. Prolog: A database query language for all seasons. In Proc. from the First International Workshop on Expert Database Systems, pp. 219–232. Benjamin-Cummings Publishing Co., Inc., Redwood City, CA. 12
C. Zaniolo. 1988. Design and implementation of a logic based language for data intensive applications. In Proc. of the Fifth International Conference and Symposium on Logic Programming, pp. 1666–1687. 65
C. Zaniolo. 1993. A unified semantics for active and deductive databases. In Proc. of the Workshop on Rules in Database Systems, Workshops in Computing. Springer-Verlag. DOI: 10.1007/978-1-4471-3225-7_16. 41
C. Zaniolo. 2002. Key constraints and monotonic aggregates in deductive databases. In Computational Logic: Logic Programming and Beyond, Essays in Honour of Robert A. Kowalski, Part II, pp. 109–134. Springer-Verlag, London, UK. DOI: 10.1007/3-540-45632-5_5. 25
C. Zaniolo and H. Wang. 1999. Logic-based user-defined aggregates for the next generation of database systems. In The Logic Programming Paradigm: A 25-Year Perspective, pp. 401–426. Springer Berlin Heidelberg, Berlin, Heidelberg. DOI: 10.1007/978-3-642-60085-2_18. 25
C. Zaniolo, N. Arni, and K. Ong. Dec. 1993. Negation and aggregates in recursive rules: The LDL++ approach. In Proc. of the Third International Conference on Deductive and Object-Oriented Databases (DOOD), pp. 204–221. Springer-Verlag, Lecture Notes in Computer Science 760. 24
C. Zaniolo, S. Ceri, C. Faloutsos, R. T. Snodgrass, V. S. Subrahmanian, and R. Zicari. 1997. Advanced Database Systems. Morgan Kaufmann, San Francisco, CA. 42
C. Zaniolo, M. Yang, A. Das, A. Shkapsky, T. Condie, and M. Interlandi. 2017. Fixpoint semantics and optimization of recursive Datalog programs with aggregates. TPLP, 17(5-6):1048–1065. DOI: 10.1017/S1471068417000436. 83
N. Zhou, Y. Shen, L. Yuan, and J. You. 2001. Implementation of a linear tabling mechanism. Journal of Functional and Logic Programming, 2001(10). DOI: 10.1007/3-540-46584-7_8. 59
D. Zook, E. Pasalic, and B. Sarna-Starosta. 2009. Typed Datalog. In Proc. of the 11th International Symposium on Practical Aspects of Declarative Languages, PADL ’09, pp. 168–182. Springer-Verlag, Berlin, Heidelberg. 31
1. This example is inspired by the Mathematics Genealogy Project, http://genealogy.math.ndsu.nodak.edu/, which is also the source of most of the data used.
2. Another popular convention in Datalog systems is to prefix variables with the question mark, e.g., ?First, ?Area, ?Year.
3. We assume in this chapter a basic knowledge of relational database systems, such as relational algebra and the SQL query language. The necessary background would be included in any introductory database text, such as Garcia-Molina et al. [2009].
4. SQL:1999 introduced support for the comparatively limited form of linear recursion.
5. A Horn clause is a logical implication among positive literals with at most one literal in the consequent.
6. A list of these workshops can be found in http://dblp.uni-trier.de/db/conf/xp/index.html
7. The use of negation requires an additional syntactic condition to ensure safety, namely that every variable in a rule appear in at least one non-negated goal in the rule body. Thus, for example, a rule unrelated (P1, P2) :- not related (P1, P2) would not be safe.
8. Minimality in this context means there is no other satisfying truth assignment that makes a proper subset of the propositions true. Note that there can be multiple, incomparable such assignments.
9. The notation pred/N indicates that the predicate pred takes N arguments.
10. Beeri and Vardi [1981] viewed the above rules as constraints—or dependencies—and used a different, but equivalent, tableaux representation for them.
11. http://bitbucket.org/giorsi/nyaya
12. Another convention is to use a right-pointing arrow for rules that should be interpreted as integrity constraints [Aref et al. 2015].
14. F-logic frames can be viewed as a formalization of the concept of frames introduced by Minsky [1975].
15. In F-logic, classes are also objects and they can have information about themselves, which is not inherited by instances of these classes. In Java terms, this information corresponds to static methods.
16. LPS [Kowalski and Sadri 2012] is an exception, as it has some of the characteristics of Transaction Logic, described in the next subsection.
17. http://flora.sourceforge.net/tr-interpreter-suite.tar.gz
18. Syntactically, G subsumes F if F can be derived from G by substituting 0 or more variables with constants or other variables. So, for example, influenced(X, Y) subsumes influenced(dm, Y), influenced(X, X), influenced(X, Y), and influenced(dm, tjg).
19. Prolog pedagogues, when teaching data recursion, wisely choose graphs, for example, the advises relation, that can have no cycles.
20. http://docs.microsoft.com/en-us/sql/odbc/microsoft-open-database-connectivity-odbc
21. Another was WebLog [Lakshmanan et al. 1996], which deals with semi-structured data using a language very similar to F-logic.
22. http://www.w3.org/TR/2008/WD-owl2-profiles-20081008/#OWL_2_RL
23. http://ontotext.com/products/graphdb/
